estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014） おつかれさま。
— titia (@titia_til) October 1, 2022
最後C++に書き直そうとしましたが、時間切れで終了。悲しい。
・新しい頂点のウェイト/周囲の長さ
を評価値に次の四角形を作る
・大きいウェイトの頂点に至る答えの列を元にやり直す
という感じでやりました。
estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014）
— titia (@titia_til) October 1, 2022
解説放送を見て、似た考察はしていたのだけど、うーん……、という感じでした。
解説と感想をだらだら書きます。
この感想ツイートが長くなったので、こっちにまとめておきます。
序盤は、「オセロっぽいな」と思い、オセロの評価値として「自分が置ける位置の個数」が有名なことにならい、「次に作れる長方形の個数」を評価値にしようとしました。が、これで長時間回してもあまり伸びない。なので、それに代えて、
・長方形の周囲の長さ
・次におく頂点のweight
・長方形を作ったとき、新たに作れるような長方形の個数
あたりを評価値に。
最終的には、
・次におく頂点のweight/（長方形の周囲の長さ^(1～4のランダムな数)）
にしました。（それをheapqに突っ込み、上位三つのうちからランダムに採用）
解説放送を見ると、weightは取り入れなくて良かったらしいので、それを消して回して実行してみたけど、うちの環境だと点数は伸びません……。（PyPyだし、実行回数が足りないのか？ と思い、10倍の時間回したので比較したら多少は伸びたが、50ケースで+100万もなさそう）
解説放送で言っていた「枠」という概念にはたどり着けなかったけど、まあそれっぽいことは考えていたとは思う。
「枠」は思いつけたとしても実装に反映できたか自信ないし、評価値については及第点かなぁ。
山登り・焼き鈍しについては、
・部分的に残して作り直す
としていました。答えの列のある長方形を見て、それを作るのに必要なものたちだけでやり直す、という山登りです。
・最終スコアが大きい答えの、ランダムな長方形一つ
を残すのに加えて、weightの大きい頂点までいったものを採用したいと思っていたので、
・（スコアは悪くても）weightの大きい頂点（長方形）
を残してやり直すことも実装しました。
解説放送では、部分的に壊してやり直すと言っていて、そっちかー、という感じに。
その方が自然な山登りだけど、大きいweightのものを残したいと思ったので、考えなかった。
どのくらい差があるのかは分からないけど、weightが大きい頂点を残したい、と思ったのは筋が悪かったのかな……。
感想書いたけど、何を反省すべきかよく分からない！
高速な言語（C++かRustで書くのは考えた）で書いていれば気付けたことはあったかもしれないけど、気軽に色々試すなら慣れているPythonの方が良い、と思ってPythonで書いているので。
最後、C++に書き換えようと思ったとき、書き換え時間の見積もりがまずくて終わらなかったのは良くないけど、そんなことを反省しても、という気がするので。
0 件のコメント:
コメントを投稿