暫定: 27,428,379,227点、26位
システムテスト: 1,128,435,184,437点、24位。
- 各ブロックのそれぞれのオブジェクト内の始点と方向を入力とし、シルエット外に出ないように、ブロックを広げていく処理を作る
- 1個のブロックを広げるだけ広げてから次のブロックに行くのではなく、順番に1個ずつ広げていく
- スコア計算的に、少数の大きなブロクがあるよりも、最小のブロックが大きいほうが良いので
- 各ブロックでも深さ優先ではなく幅優先的に広げていく
- 線上ではなく球状にするイメージ
- 深さ優先ではないほうを試したわけではないが、このほうが良いだろう、たぶん
- 両方のオブジェクトで別々に向きを指定する意味は無い（左側で90度回転したいなら右側で回転すれば良い）と思うかもしれないが、両方で指定している
- ブロックを広げていく方向は固定なので、向きを変わればちょっと結果が変わりそう
- 広げられるブロックが無くなってもシルエットが埋まっていなかったら1x1x1のブロックで埋める
- でも最終結果にこの片方にしかないブロックが出てくることはほどんどない
- 1個のブロックを広げるだけ広げてから次のブロックに行くのではなく、順番に1個ずつ広げていく
- この処理に渡す、始点と方向のリストを焼きなまし
seed=0とseed=1の結果は次のようになった。
以降はコンテスト中に考えたことを適当に書き連ねる。
seed=0について
Silhouette Block Puzzle Creationのseed=0で476,190,476点を獲得!!!https://t.co/iwyI8sqJKt
— kusanoさん@がんばらない (@kusano_k) 2023年3月31日
(画像は自動で挿入されません。各自ダウンロードして添付し、この文章は消してね) #AHC019 #visualizer pic.twitter.com/UAdPlItGYO
体積7, 9, 9, 9のブロックで作るこれが、たぶん最適解。
取り組み始めたのが遅かったけど、共有される画像は見ていた。スコアの良い画像だと、こんな感じにブロックが層状になっている。これを見て「これは……焼きなましなどではなく、何らかの方針に沿ってブロックを作るゲームかな？」と思っていた。焼きなましで良い感じのスコアになったら、seed=0だけはこんな感じなったわ。共有画像を信じると危険。特にseed=0が特殊な入力の場合。
三面図なら簡単なので……
1個のオブジェクトの三面図が目的のシルエットになる問題なら、シルエットの無い部分を切り抜くだけである。でもこの問題は4面ある。うち2面を平面のブロックの組み替えで作れるようにして……。ということをプログラムを書く前は考えていた。上述の共有されていたseed=0の画像がそんな感じだったし。この方針はいけるのだろうか？
高速化
始点と方向を受け取って立体を作る処理は、6秒の間に10万回～200万回くらい実行できている。最初に書いた方法でブロックを広げていくとき、シルエット外だったりすでに他のブロックがあったりで広げられなかった場所は二度と広げられない。各ブロックのどのマスまで、また6方向のうちどの方向までをチェックしたかを覚えておくと速くなった。
近傍の選択確率
とはいえ、焼ききれておらず、実行時間を伸ばせば伸ばすだけ結果が良くなる。ということは、どの近傍を選ぶのかが重要なはず。
どの近傍をどの確率で選ぶかはOptunaで探索した。後述するように、たぶんちゃんと探索できていないけど。
固定の確率にしているけど、Dや入力生成方法のp、温度（進行状況）で最適な値は変わると思うんだよな。その種類の近傍を何回選んでスコアが何回向上したかを記録しておいて、向上する確率に応じて選ぶようにしてみたけど、結果は返って悪くなったのでボツ。近傍をどういう確率で選ぶべきかという話題をあまり見ない気がする。何か定番の良い方法は無いのだろうか。
スコアのブレ
この問題、ちょっとした運でスコアが大きく変わる。たまたま1x1x1のブロックができてしまったら、スコアが109も増えてしまう。
そんなに時間も無いので、手作業で確認するときは20ケース、Optunaで探索するときは100ケースで動かしていたけど、全然足りない感がある。良くなった……ような……気がする！ ちょっと悪くなったけど……これは誤差かなぁ……とかやっていた。こんな状態でまともに改善できるわけがない。クラウドでテストを回すことを考えるべきかもしれない。
