yukicoder No.5003 物理好きクリッカー 参加記

yukicoder

問題

No.5003 物理好きクリッカー - yukicoder

クッキークリッカーを少し複雑化させたようなルールのゲームにおいて、所定のターン終了後に手持ちのクッキーの数を最大化する問題です。

25日間のマラソンでした。最終的に1位で終えることができました。

考察1

第一感、この問題の本質は、買い物（施設の購入、施設の強化、クリックの強化）の順序を最適化する所にあります。

そして、テストケースごとに異なるのは、たまに（100～200ターンに1度）発生する特殊効果だけです。その他、総ターン数とか価格とかの条件は全く同じです。

ところで、特殊効果って、買い物の最適な順序にあまり影響しないのではないでしょうか？ ということは、買い物の順序は決め打ちでいいのではないでしょうか？

というわけで、ローカルでテストケースをいくつか生成して、合計点が高くなるように、買い物の順序を山登りで最適化しました（本当は焼き鈍しというのがしたかったのですが、お察しください）。

山登りで最適化した買い物の順序をコードに埋め込んで提出したのが、次の提出4回目です。

提出4回目

https://yukicoder.me/submissions/301436

C / 3,211 Bytes / 449 ms / スコア 312,529,669,165

上述のとおり、買い物の順序は完全固定です。決められた物を、決められた順序で、買っていくだけです。コード5行目の

char acts[]="AABBBBBDCBB ... ";

というのが買い物の順序のデータで、Aはクリックの強化、Bは設備 hand の購入、などと決めてあり、これを先頭から順に消化していきます。実行時に判断しているのは、

1. 次の買い物をするか、しないか。（次の買い物をすると元が取れなそうだと思ったら、それ以降は買い物を一切しない。）

2. 次の買い物をするとして、定価で買うか、セールまで待つか。（基本は単純な利得比較、ただし早く買うのを有利にするヒューリスティックを少し加味。）

の2点だけで、探索は全くしていません。

なんと、これだけで312e9点も取れてしまいます。

考察2

上記の提出では、買い物の順序を1通りに定めていますが、実行時間はたっぷり余っているので、何通りか試してもいいのではないでしょうか？

そこで、ローカルで50個のテストケースを作り、それぞれ山登りで買い物の順序を最適化してみたところ、意外にも、全部異なる結果になりました。思っていたより、特殊効果は買い物の最適な順序に影響していそうです。

提出7回目

https://yukicoder.me/submissions/302542

C++ / 14,405 Bytes / 150 ms / スコア 317,761,005,802

埋め込んだ50通りの順序を全部試して最も良いものを選ぶようにしました。それ以外は、先のコードとほとんど同じですが、スコアにかなりの改善が見られました。

実行時間がむしろ短くなりましたが、その理由については後述します。

考察3

50通りの順序を試すようにしましたが、まだまだ実行時間に余裕があります。そこで、これらの順序を包含する範囲のようなものを考えて、その中で探索をさせてみようと考えました。例えば、買い物を100回した時点では、ローカルのどのテストケースでも、設備 hand の購入は20回以上27回以下行われていますので、それを探索範囲とします。これを、全ての買い物回数について何を何回以上何回以下というテーブルを作って、コードに埋め込みます。

提出10回目

https://yukicoder.me/submissions/303306

C++ / 19,795 Bytes / 3,205 ms / スコア 329,229,387,323

実行時間と引き換えに、スコアがかなり改善しました。

探索方法は、幅優先探索です。ただし、複数の経路で買った物の数が同じになった場合は、最もスコアの良いものだけを残すようにしています。これにより、探索の状態数の上限は、上述の探索範囲によって規定され、テストケースに依存しないはずです。なお、スコアは、単純に、買い物を今後一切しないと仮定したときの最終クッキー数の大まかな見積りです。

考察4

提出用に範囲付きの探索を実装したので、ローカルで山登りの代わりにこの範囲付きの探索を利用して順序の精度を上げました。具体的には、範囲を少し広げて全ケースを再探索→結果を集約して範囲を更新、を何回か繰り返しました。

提出11回目

https://yukicoder.me/submissions/305186

C++ / 19,900 Bytes / 9,267 ms / スコア 330,658,005,177

ちょっとパラメータ調整をしただけのつもりなのに、実行時間が9秒を超えて、ひやっとしましたが、ともあれ少し改善しました。

これが最終提出となりました。

結論としては、「ローカルで山登り＋幅優先探索」＋「サーバで幅優先探索」ということになりました。

視覚化

f:id:saito_ta:20181225103338p:plain

視覚化

上の画面は、横軸に買い物の回数、縦軸（下向き）に個別の物（AとかBとか）を買った回数をプロットしたもので、縦の幅がその時点での探索範囲に相当します。どのテストケースでも大体同じような傾向になるという当初の予想が確認できました。

未考察の事項

買い物の順序はかなりちゃんと探索している一方で、セールを待つか否かの判断はぞんざいで、最初に変なヒューリスティックを導入したまま、最後まで改善できませんでした。

あと、買った物で売れる物を最後に全部売るようにしていますが、本当は全部売らないで一部残した方が良いはずです。というのも、売れるものは100個を超えます。100個の物を売るには100ターンかかりますが、終了100ターン前に何かを売るより、それを売らずに100ターン持っておいた方が良いからです。しかし、これは結果に与える影響が無視できるほど小さいのではという推測のもと、ちゃんと考察しませんでした。

余談：入出力と速度について

提出7回目 (150 ms) で実行時間が短くなったのは、ジャッジから特殊効果のデータを読み終えた時点で close(0) を呼んで標準入力を閉じ、それ以降のジャッジからのレスポンスを無視できるようにしたからです。その前の提出4回目 (449 ms) では、クエリを出力するたびにレスポンスを読み捨てていたのですが、これだと解答プロセスとジャッジプロセスが交互にしか動かないため、遅くなっていました。標準入力を閉じると、ジャッジ側に SIGPIPE が発生してしまうようにも思えますが、 yukicoder では「リアクティブ問題で出力を投げっぱなしでもAC」という仕様がアナウンスされていますので、入力を閉じてしまっても（入力を読まずにプロセスを終了するのと大差ないので）問題ないようになっているはずだと推測でき、実際そのとおりでした。