読者です 読者をやめる 読者になる 読者になる

新人女子プログラマの書いたコードを直すだけの簡単なお仕事をしてきた

ちょっと前にはてブとかで話題になっていた新人女子プログラマの書いたコードを直すだけの簡単なお仕事です!|paizaオンラインハッカソンVol.1をやってみました。

最初は言語の勉強を兼ねてJavaで書いていたのですが、どうにもテストケース3が通過できなかったので普段書いているPythonで再挑戦したらテストケース3まで通過することができました。

mia_0032さんの採点結果[100点 CTOに昇進しました!]|paizaオンラインハッカソンVol.1

最初書いていたJavaのコード(https://gist.github.com/mia-0032/7858706)はロジックとしては、最初にすべての価格の組み合わせからペア価格の一覧を出して、その後、キャンペーン価格ごとに近いペア価格を探索するというものでした。

ただ、これだと当然ながらアイテム数が増えると累乗で時間が増えてしまう感じでした。 なので、テストケース2までは1.6秒くらいで通過できたものの、テストケース3はタイムアウトで突破できないって状況でした。

その後Twitter眺めてたら部分探索でやってる人が結構いい数値を出していたので、自分も部分探索で実装するかー&ちょっと複雑になりそうなんで慣れてるPythonでって感じで書いたコードが↓。

https://paiza.jp/poh/ec-campaign でテストケース3つともクリアしたコード。http://paiza.jp/poh/ec-campaign/result/609c70c227bb4762a2d3728d461382eb

コードのロジックでポイントとなるところは以下のようなところでしょうか。

  1. 同じ価格のアイテムは3個以上あっても意味ない
  2. 同じ価格のアイテム2個でキャンペーン価格になるなら、それでOK
  3. 異なるアイテムでも足したときにキャンペーン価格になれば、それでOK
  4. 可能性を持つペアの最大値を求めなければならないのは、上記のパターン以外のときにしかない

1.について、価格の組み合わせを見ているだけなんで同じ価格が使えるかどうかの2個までは必要ですが、3個目以降は特に組み合わせが増えるわけではないので必要ありません。

2.について、例題を見る限りはわりと整った価格の商品が多かったので、ちょうど半分の価格のアイテムが2個あることが多そうと思い、ロジックにいれました。

3.については、キャンペーン価格以下の商品についてキャンペーン価格を超えない範囲の組み合わせを探していくときに、うまいこと見つかればOK。

4.については、あるアイテムに対するキャンペーン価格を下回る最大値をすべてのアイテムについて算出して、その最大値を求めます。

という感じのロジックで今回は組みました。 最速記録とか見ると自分の記録よりだいぶ速いので、もっと良いロジックがあるんだろうなーと思いつつ、クリアできたのでとりあえず満足です。

・12/14追記

もう少しコードを直して、二重forループになっていたところを一重ループに減らしました。 ちょっと高速化されました。

mia_0032さんの採点結果[100点 CTOに昇進しました!]|paizaオンラインハッカソンVol.1