【アルゴリズム】新人女子の書いたコードを直すだけの簡単なお仕事をやってみた
数日前から一部で話題*1になっていた、
新人女子の書いたコードを直すだけの簡単なお仕事をちょっとやってみました。
結果は一応ランクS。
この一件でCTOに昇進できたらしく、どうやら無事新人女子とのフラグも立ったようです。
野田さんprpr。
sakuramochi702さんの採点結果[100点 CTOに昇進しました！]｜paizaオンラインハッカソンVol.1
で、ふとpaizaの利用規約を見ると、
スキルチェックサービスにおける利用者等の解答内容における著作権は、利用者等に帰属するものとします。
と書いてあったので、せっかくだから僕の回答についてちょっと書いておきます。
といってもケース3では1秒以上かかってるし、
自分でもまだまだ速くできそうな箇所はいっぱいあるので大したものではないですが・・・。
ナップサック問題？
こういう、「条件を満たす中で最大のものを求めよ」みたいな問題のことを、ナップサック問題と言うそうですね。
ナップサック問題 - Wikipedia
プログラミングコンテストでの動的計画法
まぁ今回の問題では組み合わせは必ず2つだし、もっと簡単ですが。
ちなみに、自分は情報学の出身でないので、この辺とても疎いです。
しかも仕事ではこういうものをキャッチアップする機会もあまりないので、
こういった仕事と関係ない外部の問題とかの機会に意識的にキャッチアップしないとですね。
アルゴリズム
最初は、「これって1行読み込むたびに都度商品の組み合わせ金額を計算しておけばOKじゃん」と思って、
1.セット金額としてあり得るものを全てリストに保持
2.キャンペーン価格を読み込みながら、それを超えない最大値をリストから引っ張ってくる
というアルゴリズムで書いていたのですが、よく見ると商品って20万点もあるのね。
商品を読み込みながら都度計算していたら、なんと20万×20万/2=200おく！
ものループが回ることになります。そりゃRuntimeErrorも起こりますわ。
図1.クソコードに軽蔑の目を向ける野田さん
で、これは駄目だと思いなおし、必要な分だけループを回すように修正しました。
具体的には、
1.最初はとりあえず商品価格のリストを素直に作る
2.キャンペーン価格を読み込みながら、それを超えない最大値を探す
結局2.で二重ループ自体は行うのですが、
キャンペーン価格ごとに必要な分だけ回すのでそんなに馬鹿みたいな数にはならない。
具体的なキーポイントとしては、
・商品価格を大きい順（降順）に並び替えてループ回す
ということ。
こうしておけば二重ループ(i, j)内でキャンペーン価格を超えない金額を探す際、
最初に見つかるのがそのループでの最大値になるので、即breakして次のi++に行くことができます。
jの方のループ回数を減らせるのが（たぶん）ポイント。
ちなみにListを逆順にソートするのは以下のようにやりました。
Collections.sort(priceList); Collections.reverse(priceList);
もちろん逆順ソートせずにループ自体を逆から回してもOKです。読みにくいですが。
ループする場所を考える
最初の案は、確かに全ての商品数分の組み合わせを求めるためループ回数は膨大ですが、
処理中に同じ計算を2回行うことはありません。
しかし、修正した方のアルゴリズムでは、キャンペーン価格ごとにリストの大きい方からループするので、
実は同じ計算を何度も行います。
一見すると後者の方が無駄なようですが、実際には後者の方が圧倒的に速い。
理由は単純で、前者で行う計算のうち、大半は要らないものだからです。
上記から分かるとおり、ループする際は、
どこでループするのか（≒期待値として何回ループするのか）をちゃんと考える必要があります。
今回の場合、商品数は最大20万、キャンペーン日数は最大75なので、
キャンペーン日数でのループ1回あたりにかかる時間が多少長くなってでも、
商品数でのループ1回にかかる時間を短くした方が、結果としては圧倒的に速くなるのです。
改善点
とはいえ、キャンペーン価格ごとのループにも無駄が多いので、
まだまだ改善の余地ありです。
例えばそれぞれの i について、どこの j までループしたのかを保持しておくなどすると、
無駄がなくなってもっと速くなりそうですね。
今度暇だったら試してみましょうか*2。
図2.良いコードに諸手をあげて喜ぶ野田さん
終わり。
