オブジェクティブ氏に改善を求めてみた
燃え尽きた。先日のアレに人単価のクイックソートと、杜撰な深掘り機能を付けた。
csny/enjou at version2 · GitHub
コードはこれ。
enjou/main.m at version2 · csny/enjou · GitHub
まぁそれでもn値が50くらいになると、ご覧の通り30秒を超えてしまう。
単価の安い順にソートしているので、「のっけから1のビット立てまくってガンガン掘り進めようぜ!」というかなり蛮勇な作戦なのです。会社間の単価が似たり寄ったりで且つ会社によって人数に開きがあるとかなーり精度が悪くなる。一方、全探索だと40件くらいから、一服してコンビニ行って風呂入っても探索が終わってないんだw
メモ化まで付ければもうちょい早くなるのかもね。まぁいいや。
入力データと答え、お借りしました。大変勉強になりました。
paiza オンラインハッカソン Lite を大きなデータで試す - y_uti のブログ