AHC019参加記
Updated: 2024-05-12
はじめに
こんにちは、through です。
この度 MC Digital プログラミングコンテスト 2023(AHC019)にて、過去最高順位をとることが出来たので、記念に記事を書きたいと思います！
暫定テスト : 24,477,348,341 点 36 位 / 787 位
システムテスト: 972,132,803,958 点 37 位 / 786 位
performance は 2315 で初黄 performance でした！ heuristic分野でここまで戦えたのは初めてのなので、記念に記事を残します！
問題概要
1×1×1 の立方体が接合されて出来たブロックを作成し、正面・右から見た時のシルエットが入力のシルエットと一致するようにブロックを配置する問題。
- 正面・右から見た時の入力シルエットの組は 2 組用意されている。
- 知育玩具としての開発が目的の為、作成するブロックは大きい方が point が高い。
- 各ブロックは両方のシルエットで使われる方が point が高い。
解法概要
部分破壊 & 再構築 を行う焼きなまし法です。
Block インスタンスを作って近傍探索
まず Block class を作成して、メソッドに Block 拡張・Block 縮小メソッドを導入します。 そうすることで簡単にブロックの管理が行えます。
ブロックに有り得る向きは 24 通り(サイコロの置き方と同じ)存在し、同じブロックをシルエット 1 とシルエット 2 の両方で用いる場合、向きが違う場合は伸ばす方向(dx,dy,dz)も異なります。
今回は各ブロックに向きを定義して、それに対応した dx,dy,dz を予め作成することで簡単に同型を保ったまま拡張出来ます。
初期解生成
初期解は以下のように生成しました。
- 1×1×1 ブロックを両方の空間のランダムな場所に 1 つずつ置く。
- 2 つのブロックの向きを全探索して最大限まで拡張する。
- 一番拡張出来た方向を採用して反映する。
- シルエットが完成するまで 1~3 を繰り返す。
コンテスト序盤は『最小限の 1×1×1 ブロックでシルエットを満たす配置を決める → ブロック拡張・合成・削除』という方針を取っていました。しかしブロックの行先が他のブロックに邪魔されていることが多かったり、合成出来るようなブロックペアが中々存在しなかったりして遷移の進み具合が遅かったので却下しました。
行先のブロック削除を実装すれば解決するとも思いましたが、行先が両方のシルエットに使用されているブロックの場合、片方を変更するともう片方にも影響が出てシルエットを満たさなくなる場面を考慮する必要があって大変な為、今回の方針に落ち着きました。
部分破壊 & 再構築
これは過去の AHC の上位解法から着想を得ました。
ブロックが邪魔で拡張できないケースを出来るだけ少なくするべく、まとまった空間を用意したいと思った為、『ブロックを何個か完全に破壊して、それで出来た空間に対して再度解を構築する』という方針にしました。最終的にはブロックの破壊個数は 1 ~ 3 個の破壊のみに制限して、それぞれ予め自分で決めた確率で何個破壊するかを決めています。
この操作は具体的に、1 ブロック破壊によって『ブロックの移動・変形』、2,3 ブロック破壊によって『ブロックの合成・大きさの均一化』をすることを狙っています。
また複数ブロック破壊する時は、削除後の空間がより自由度の高いものになるように隣接ブロック同士を破壊しました。具体的には 1 つ削除するブロックを選んだ後に、素直な bfs を書いて近場のブロックを削除しています。両方の空間で隣接するブロックのペアがあればそれが最高ですが、なかなかそのケースは無い為ランダムでどちらかの空間を選んで隣接ブロックを破壊しました。
コンテスト序盤は、ブロックが入り組んでいる場合は多くのブロックを破壊する必要があると思てそのような遷移も含ませていました。しかし、乱択性が強すぎてスコア上昇が局所的(上がる時は急上昇するが改善頻度が低い)だったり、シンプルに 1 回当たりの計算が重かったりしてスコアが良くなかったので却下しました。
更新が全然来なかったらブロック移動
一定回数以上スコア更新が見込めない場合に、ブロックを若干ずらす処理を加えました。 具体的には、ブロックのペアを 1×1×1 の状態にまで戻して一方のブロックを数ブロック分ずらした後に再度拡張する操作を複数回行う処理を入れました。
スコアをある程度保ちつつ新たな隙間を生成して次につなげたいという発想から実装に至りましたが、思ったよりスコアは上昇しませんでした。
その他の細々とした調整
- 提出前に拡張出来るか再確認。
- 行・列のブロックの有無を bit で管理して高速化。
- シルエットのブロック数の差が超大きくて解構築が出来なかった激辛ケース用貪欲を用意。
提出の変遷
必要最低限の 1×1×1 ブロックのみで構成
まず、問題文を見て試してみたくなったことが、「最高効率で 1×1×1 ブロックを敷き詰める」。 ということで、1 つ 1 つのブロックが最小である為スコアは振るわないと思うが、お試しとして提出。他の方々もやりたくなったようで、自分が提出した時は同じ点数が 10 人程いて面白かった。
暫定テスト：2,699,000,000,000 点
共通部分に着目
1 つ目の提出の visualizer を見ると、自分の実装上斜めに点々に配置された形が多くある。ならばシルエットの組両方に出てくる、斜めの共通部分を繋げていけばコスト削減に繋がりそう。ということで実装。棒状に伸ばして管理するのも思いついたが、殆どスコア上昇が期待出来なかった為断念。 AHC 開始初日はここで幕を閉じる。。
暫定テスト：1,711,913,901,787 点
Block インスタンス作成 & ブロックを最大限拡張
今回は最初の入力で全ての情報が揃う系の問題の為、山登り法や焼きなまし方が適用出来ないかを考える。山登りをするとしたら近傍が探索出来るようにしたい為、Block の構造体を作成して Block 拡張メソッド、Block 縮小メソッドを作りたくなる。 これが実装出来れば、自在にブロックの伸び縮みが操れて近傍が探索出来る為、山登り法や焼きなまし法に繋げていけそう。ということで実装。 この方針は当たりらしく、一気に点数上昇！
暫定テスト：351,312,313,381 点
部分破壊 & 再構築をする山登り
3 つ目の提出の visualizer を見て第一声は『青ブロック巨大過ぎる』。 巨大なブロック自体が良いのか悪いのかは、おそらく今後の方針の判断材料になりそう。巨大ブロック自体は多くの空間を超低コストで埋めてくれるというのは良い点だが、巨大ブロックを作ることに固執しすぎると、他のブロックがうまく拡張出来なくなることも多そうだなと感じた。 ここで、実際にブロックサイズが特定の大きさ以上になったら強制で打ち切る処理を入れたところ、スコアは落ちた。(サイズが大きくなる遷移を妨げてしまったっぽい。)
次に、3 は無の状態から作成した解である為、無難に山登りをしたくなる。 完全ランダムの 1 回きりであそこまで伸びるのだから、数ブロック破壊して出来た空間に対して、再度ブロックを広げていくような処理を時間一杯すれば勿論上がるでしょう。 実装してみると案の定スコアは急上昇！さっきの 5 倍ほど良くなってる！
暫定テスト：72,975,925,496 点
高速化 & archive 作成
↑ の後、無駄部分を排除したり高速化したりして、山登りのループ回数が 1.5 倍ほど上昇して、暫定テストが、59,087,373,731 点まで上昇。
この後何をするか見通しが立っていなかった為、とりあえず時間を伸ばして様子見。 すると、確かに実行時間をのばすとスコアも伸びるが、その伸びがかなり小さくなってきている。(正確には伸びる時は一気に伸びるけど、伸びるタイミングが減っている) なので、スコア上昇時に archive を取っておいて、山登りで 1000 回以上連続でスコア更新が起きなかったら 1 つ前のベストスコア状態に戻す処理を書いた。
結果絶対スコアは先ほどの高速化後の点数より微増だったが、相対スコアは 17B → 19.9B に上昇。そしてなんと暫定 1 ページ目に入る快挙！マジか！
暫定テスト：59,475,513,479 点
焼きなまし法に移行
その後、またまた高速化をして、D = 5 で 120,000 回、D = 14 で 10,000 回ほど回るようになった。ここまでくると、D = 5 ではかなり良いスコアを取れるようになってきた。(時間を長くしてもほとんど更新されない状態まで来た。) となると、ここから先は D が大きいケースとの闘いになる。
多様性確保を目的として archive を作成して遡る処理を書いたが、温度を高めにした焼きなましでも同じく多様性が確保出来ると思った為実装。visualixer を見てみると、D が大きいケースでの改善が多くみられたので提出したところスコアが上昇。 おそらく archive よりこまめに遷移が移ってより多様性が確保されたのだと思う。
暫定テスト：44,785,122,602 点
近傍を 1 ~ 3 個に制限 & 隣接ブロックを削除 (最終提出)
今までは 1 ~ Block 総数-1 個をランダムに破壊するという処理を書いていた。というのもブロックの位置はかなり密接で数個程度の破壊で更新出来るケースはあまりないと思っていた為。ただ数個破壊でも多少は更新されることから、数個破壊を沢山行えばそこから生まれる小さなブロックのずれが積もって、いつかは良い状態になるのではと思って実装したところスコアは大幅 up。
またブロックを複数個破壊する時は少なくともどちらかの空間で隣接しているブロックを選んで破壊することで、よりまとまった空間を確保することが出来てそこでもスコア up。
これを実装した後に、ちょっとした高速化やハイパーパラメータの微調整を行って最終提出！
暫定テスト：24,052,095,102 点
終了後
TL での感想戦。上位の方の解法を見ていると、色々な場所で工夫が見受けられてまだまだ甘さを感じた。ざっと見て一番目についたのは、
> ブロックを採用する際の評価値を大きさだけでなく、カバーするのが難しい場所(シルエット上で連結部分が少ない・繋がっている空間が少ない等)をカバーしていた場合に評価値を上げる。
…頭良すぎませんか。
今回は評価値をアレンジすることが全く出来なかった為、次回以降は現象の核を捉えた評価値を生成してみたいなと思った。
また今回の 1 位の方はビームサーチだとか。。異次元過ぎる堂々の 1 位で凄いと思った(小並感)。次回の長期コンに参加する時は、ハイパーパラメータも最適化したりクラウド上でテストが回したり出来るようにしたいと思った。
感想
今回は春休み期間ということでいつもより時間があった為、思いついた事は全てやりつくそうという意気でコンテストに参加しました。結果、終盤は失速してしまいましたが、自分の頭で描いていたものは全て実装して過去最高順位を取れたので非常に嬉しいです。
今回の問題自体かなり好きな部類だったのでとても楽しめました。 また今回人生初記事となりましたが、記事を書くことも思ったより楽しかったので、また良い順位が取れたり色変したりしたら記事を書いてみようと思います。
writer の wata さん、スポンサーの MC Digital さん、参加者の皆さん、ありがとうございました。 そして最後まで読んで頂きありがとうございました！