📝

MC Digital プログラミングコンテスト2023 (AHC019) 参加記

2023/04/03に公開

AtCoder

ahc019

idea

はじめに

こんにちは、through です。
この度 MC Digital プログラミングコンテスト2023(AHC019)にて、過去最高順位をとることが出来たので、記念に記事を書きたいと思います！

暫定テスト　　:　 24,477,348,341点 36位/787位
システムテスト:　972,132,803,958点 37位/786位

performance は 2315 で初黄perf でした！

問題概要

1×1×1の立方体が接合されて出来たブロックを作成し、正面・右から見た時のシルエットが入力のシルエットと一致するようにブロックを配置する問題。

正面・右から見た時の入力シルエットの組は2組用意されている。
知育玩具としての開発が目的の為、作成するブロックは大きい方がpointが高い。
各ブロックは両方のシルエットで使われる方がpointが高い。

https://atcoder.jp/contests/ahc019

解法概要

部分破壊 & 再構築を行う焼きなまし法です。

Blockインスタンスを作って近傍探索

まず Block class を作成して、メソッドにBlock拡張・Block縮小メソッドを導入します。
そうすることで簡単にブロックの管理が行えます。

ブロックに有り得る向きは24通り(サイコロの置き方と同じ)存在し、同じブロックをシルエット1とシルエット2の両方で用いる場合、向きが違う場合は伸ばす方向(dx,dy,dz)も異なります。
今回は各ブロックに向きを定義して、それに対応したdx,dy,dzを予め作成することで簡単に同型を保ったまま拡張出来ます。

各ブロック毎に基準のベクトルを決めてz方向に伸ばしたイメージ図

初期解生成

初期解は以下のように生成しました。

1×1×1ブロックを両方の空間のランダムな場所に1つずつ置く。
2つのブロックの向きを全探索して最大限まで拡張する。
一番拡張出来た方向を採用して反映する。
シルエットが完成するまで 1~3 を繰り返す。

試しに Seed = 0 を1ブロックだけやってみった結果
↑ をみて分かるようにランダムな場所に1×1×1ブロックを置いて拡張しただけですが、十分に拡張出来ています。今回はまだシルエットが完成していない空間に対してこの方法を繰り返すことで解を生成しました。

コンテスト序盤は『最小限の1×1×1ブロックでシルエットを満たす配置を決める → ブロック拡張・合成・削除』という方針を取っていました。しかしブロックの行先が他のブロックに邪魔されていることが多かったり、合成出来るようなブロックペアが中々存在しなかったりして遷移の進み具合が遅かったので却下しました。

行先のブロック削除を実装すれば解決するとも思いましたが、行先が両方のシルエットに使用されているブロックの場合、片方を変更するともう片方にも影響が出てシルエットを満たさなくなる場面を考慮する必要があって大変な為、今回の方針に落ち着きました。

橙方向に伸ばすとグレーブロックが縮んてシルエットが不適になるの図

部分破壊 & 再構築

これは過去のAHCの上位解法から着想を得ました。

ブロックが邪魔で拡張できないケースを出来るだけ少なくするべく、まとまった空間を用意したいと思った為、『ブロックを何個か完全に破壊して、それで出来た空間に対して再度解を構築する』という方針にしました。最終的にはブロックの破壊個数は 1 ~ 3 個の破壊のみに制限して、それぞれ予め自分で決めた確率で何個破壊するかを決めています。

この操作は具体的に、1ブロック破壊によって『ブロックの移動・変形』、2,3ブロック破壊によって『ブロックの合成・大きさの均一化』をすることを狙っています。

また複数ブロック破壊する時は、削除後の空間がより自由度の高いものになるように隣接ブロック同士を破壊しました。具体的には1つ削除するブロックを選んだ後に、素直なbfsを書いて近場のブロックを削除しています。両方の空間で隣接するブロックのペアがあればそれが最高ですが、なかなかそのケースは無い為ランダムでどちらかの空間を選んで隣接ブロックを破壊しました。

Seed = 19 の状態遷移の一部

コンテスト序盤は、ブロックが入り組んでいる場合は多くのブロックを破壊する必要があると思てそのような遷移も含ませていました。しかし、乱択性が強すぎてスコア上昇が局所的(上がる時は急上昇するが改善頻度が低い)だったり、シンプルに1回当たりの計算が重かったりしてスコアが良くなかったので却下しました。

更新が全然来なかったらブロック移動

一定回数以上スコア更新が見込めない場合に、ブロックを若干ずらす処理を加えました。
具体的には、ブロックのペアを1×1×1の状態にまで戻して一方のブロックを数ブロック分ずらした後に再度拡張する操作を複数回行う処理を入れました。

スコアをある程度保ちつつ新たな隙間を生成して次につなげたいという発想から実装に至りましたが、思ったよりスコアは上昇しませんでした。

その他の細々とした調整

提出前に拡張出来るか再確認。
行・列のブロックの有無を bit で管理して高速化。
シルエットのブロック数の差が超大きくて解構築が出来なかった激辛ケース用貪欲を用意。

提出の変遷

必要最低限の1×1×1ブロックのみで構成

まず、問題文を見て試してみたくなったことが、「最高効率で1×1×1ブロックを敷き詰める」。
ということで、1つ1つのブロックが最小である為スコアは振るわないと思うが、お試しとして提出。他の方々もやりたくなったようで、自分が提出した時は同じ点数が10人程いて面白かった。

暫定テスト：2,699,000,000,000点

Seed = 0 の visualizer
※Seed = 0 : 19,000,000,000点 , Seed = 19 : 110,000,000,000点

共通部分に着目

1つ目の提出の visualizer を見ると、自分の実装上斜めに点々に配置された形が多くある。ならばシルエットの組両方に出てくる、斜めの共通部分を繋げていけばコスト削減に繋がりそう。ということで実装。棒状に伸ばして管理するのも思いついたが、殆どスコア上昇が期待出来なかった為断念。
AHC開始初日はここで幕を閉じる。。

暫定テスト：1,711,913,901,787点

Seed = 0 (上), Seed = 19 (下) の visualizer
※Seed = 0 : 17,666,666,667点 , Seed = 19 : 53,421,800,422点

Blockインスタンス作成 & ブロックを最大限拡張

今回は最初の入力で全ての情報が揃う系の問題の為、山登り法や焼きなまし方が適用出来ないかを考える。山登りをするとしたら近傍が探索出来るようにしたい為、Blockの構造体を作成してBlock拡張メソッド、Block縮小メソッドを作りたくなる。
これが実装出来れば、自在にブロックの伸び縮みが操れて近傍が探索出来る為、山登り法や焼きなまし法に繋げていけそう。ということで実装。
この方針は当たりらしく、一気に点数上昇！

暫定テスト：351,312,313,381点

Seed = 0 (上), Seed = 19 (下) の visualizer
※Seed = 0 : 2,566,666,667点 , Seed = 19 : 3,611,258,097点

部分破壊 & 再構築をする山登り

3つ目の提出の visualizer を見て第一声は『青ブロック巨大過ぎる』。
巨大なブロック自体が良いのか悪いのかは、おそらく今後の方針の判断材料になりそう。巨大ブロック自体は多くの空間を超低コストで埋めてくれるというのは良い点だが、巨大ブロックを作ることに固執しすぎると、他のブロックがうまく拡張出来なくなることも多そうだなと感じた。
ここで、実際にブロックサイズが特定の大きさ以上になったら強制で打ち切る処理を入れたところ、スコアは落ちた。(サイズが大きくなる遷移を妨げてしまったっぽい。)

次に、3は無の状態から作成した解である為、無難に山登りをしたくなる。
完全ランダムの1回きりであそこまで伸びるのだから、数ブロック破壊して出来た空間に対して、再度ブロックを広げていくような処理を時間一杯すれば勿論上がるでしょう。
実装してみると案の定スコアは急上昇！さっきの5倍ほど良くなってる！

暫定テスト：72,975,925,496点

Seed = 0 (上), Seed = 19 (下) の visualizer
※Seed = 0 : 985,714,286点 , Seed = 19 : 749,633,211点

高速化 & archive作成

↑の後、無駄部分を排除したり高速化したりして、山登りのループ回数が1.5倍ほど上昇して、暫定テストが、59,087,373,731点まで上昇。

この後何をするか見通しが立っていなかった為、とりあえず時間を伸ばして様子見。
すると、確かに実行時間をのばすとスコアも伸びるが、その伸びがかなり小さくなってきている。(正確には伸びる時は一気に伸びるけど、伸びるタイミングが減っている) なので、スコア上昇時にarchiveを取っておいて、山登りで1000回以上連続でスコア更新が起きなかったら1つ前のベストスコア状態に戻す処理を書いた。

結果絶対スコアは先ほどの高速化後の点数より微増だったが、相対スコアは17B → 19.9B に上昇。そしてなんと暫定1ページ目に入る快挙！マジか！

当時(開始5日目)の順位表

暫定テスト：59,475,513,479点

Seed = 0 (上), Seed = 19 (下) の visualizer
※Seed = 0 : 670,634,921点 , Seed = 19 : 461,659,001点

焼きなまし法に移行

その後、またまた高速化をして、D = 5 で120,000回、D = 14 で10,000回ほど回るようになった。ここまでくると、D = 5 ではかなり良いスコアを取れるようになってきた。(時間を長くしてもほとんど更新されない状態まで来た。)
となると、ここから先はDが大きいケースとの闘いになる。

多様性確保を目的としてarchiveを作成して遡る処理を書いたが、温度を高めにした焼きなましでも同じく多様性が確保出来ると思った為実装。visualixerを見てみると、Dが大きいケースでの改善が多くみられたので提出したところスコアが上昇。
おそらくarchiveよりこまめに遷移が移ってより多様性が確保されたのだと思う。

暫定テスト：44,785,122,602点

Seed = 0 (上), Seed = 19 (下) の visualizer
※Seed = 0 : 500,000,000点 , Seed = 19 : 251,669,372点

近傍を1 ~ 3個に制限 & 隣接ブロックを削除 (最終提出)

今までは 1 ~ Block総数-1 個をランダムに破壊するという処理を書いていた。というのもブロックの位置はかなり密接で数個程度の破壊で更新出来るケースはあまりないと思っていた為。ただ数個破壊でも多少は更新されることから、数個破壊を沢山行えばそこから生まれる小さなブロックのずれが積もって、いつかは良い状態になるのではと思って実装したところスコアは大幅up。

またブロックを複数個破壊する時は少なくともどちらかの空間で隣接しているブロックを選んで破壊することで、よりまとまった空間を確保することが出来てそこでもスコアup。

これを実装した後に、ちょっとした高速化やハイパーパラメータの微調整を行って最終提出！

暫定テスト：24,052,095,102点

Seed = 0 (上), Seed = 19 (下) の visualizer
※Seed = 0 : 478,968,254点 , Seed = 19 : 115,788,663点

終了後

TLでの感想戦。上位の方の解法を見ていると、色々な場所で工夫が見受けられてまだまだ甘さを感じた。ざっと見て一番目についたのは、

ブロックを採用する際の評価値を大きさだけでなく、カバーするのが難しい場所(シルエット上で連結部分が少ない・繋がっている空間が少ない等)をカバーしていた場合に評価値を上げる。

…頭良すぎませんか。

今回は評価値をアレンジすることが全く出来なかった為、次回以降は現象の核を捉えた評価値を生成してみたいなと思った。

また今回の1位の方はビームサーチだとか。。異次元過ぎる堂々の1位で凄いと思った(小並感)。次回の長期コンに参加する時は、ハイパーパラメータも最適化したりクラウド上でテストが回したり出来るようにしたいと思った。

感想

今回は春休み期間ということでいつもより時間があった為、思いついた事は全てやりつくそうという意気でコンテストに参加しました。結果、終盤は失速してしまいましたが、自分の頭で描いていたものは全て実装して過去最高順位を取れたので非常に嬉しいです。

今回の問題自体かなり好きな部類だったのでとても楽しめました。
また今回人生初記事となりましたが、記事を書くことも思ったより楽しかったので、また良い順位が取れたり色変したりしたら記事を書いてみようと思います。

writer の wata さん、スポンサーの MC Digital さん、参加者の皆さん、ありがとうございました。
そして最後まで読んで頂きありがとうございました！