2023/3/18〜2023/4/2に開催されたMC Digital プログラミングコンテスト2023(AtCoder Heuristic Contest 019)に参加しました。
今回は２週間の長期コンテスト。いままで、この手のコンテストでは適当にプラスの得点を取れるだけの提出をするだけというのが多かったのですが、今回は期間フルに使って真面目に取り組んでみようという気持ちで臨みました。
AHC019参加します。
— devgenjin77 (@devgenjin77) 2023年3月18日
２週間の長期コンテストになりますが、なるべく期間をフル活用して取り組めればと。
MC Digital プログラミングコンテスト2023（AtCoder Heuristic Contest 019） - AtCoder https://t.co/RPs1UolRDd
今回の結果
確定185位でした。個人的には、なかなか良い結果が出たという印象です。
今回のパフォーマンスは、前回につづき青色に到達！レートをさらに伸ばすことに成功しましたとさ。
青パフォでした😂😂
— devgenjin77 (@devgenjin77) 2023年4月3日
devgenjin77さんのMC Digital プログラミングコンテスト2023（AtCoder Heuristic Contest 019）での成績：185位
パフォーマンス：1636相当
レーティング：1308→1384 (+76) :)
Highestを更新しました！#AtCoder #MCDigitalプログラミングコンテスト2023 https://t.co/5n0vzaw5Gs
振り返り
今回、初回提出が大分出遅れた割にはいい結果が出てくれました。
A問題
A - Silhouette Block Puzzle Creation
初日に問題を見てみるも、全然なんにもわからんというのが第一印象でした。とりあえず最初の数日間は考察めいたものをして見たものの、実装の方は全然進まずでした。。
結局、まともらしい提出ができたのが終了１日前の土曜日という有様でしたが、なんとか形は作れたかという結果になりました。
基本方針
シルエット１に対応するブロックの組み方をパズル１、シルエット２に対応するブロックの組み方をパズル２と呼ぶことにします。
評価値の計算方法から見て、良い得点を得るために必要なことは以下の３つになります。（ちなみに、ここの評価値の意味合いも、コンテスト終了数日前にやっと理解できたという状態でした。。）
パズル１、２の大きさを、できるだけ小さくすること。
パズル１、２で、共通しないブロックをできるだけ作らないこと。
パズル１、２で共通するブロックの体積を、できるだけ大きくすること。
とりあえず、大きな塊で共通するブロックを作るのが良いだろうなあ、という発想のもと、以下の要領で実装することにしました。
パズル１、２をそれぞれシルエット１、２を達成できる最大のサイズで作成し、全てサイズ１のブロックで初期化する。
パズル１とパズル２で共通するブロックの連結方法を探索する。パズル１、パズル２のブロックおよび６つの回転方向をそれぞれランダムで決定し、BFSで探索しながら可能な限り連結する。これを、連結できる候補がみつからなくなる（具体的には、100回程度ランダムで始点を決めた時に候補がみつからないとき）まで続ける。
パズル１、２について、サイズ１のブロックがある場合、シルエットに影響ない場合は削除し、残す必要がある場合は可能な限りもう一方のパズルにあるサイズ１のブロックと共通化させる。
上記を１セットとし、時間いっぱいまでこのセットを繰り返して評価の高いものを採用する。
こんな実装で、なんとかコンテスト最終日に、それなりの順位まで到達することができましたとさ。
５投目。とりあえず、やれることはやった感じ。#AHC019 pic.twitter.com/BQtVh1Zi6G
— devgenjin77 (@devgenjin77) 2023年4月1日
ちなみに、本当はブロックの回転方向は24通り（6面のうちどれを下にするか×向きの前後左右の4通り）で実装したかったのですが、なぜか動かしてみるとブロックの形が合わなくてエラーになったので、仕方なくエラーが出なかった６通りの実装で妥協することに。。
そのほか、探索の打ち切り方法なんかも色々工夫の余地はあるかなーというところでしたが、最早残り時間もなく。ここで打ち切りという感じです。
とりあえず、ここまで頑張りました。
— devgenjin77 (@devgenjin77) 2023年4月1日
Silhouette Block Puzzle Creationのseed=0で1,962,301,587点を獲得!!!https://t.co/Snp2Ia7EKK#AHC019 #visualizer pic.twitter.com/lfjvQ7f2BE
最終提出コード
https://atcoder.jp/contests/ahc019/submissions/40300326
振り返り
反省点としては、以下の通り。
パズル１、２ぞれぞれで、シルエットが達成できることが確定した時点で共有ブロックの探索を打ち切るべきだったかと。現時点では、余計にパズルのサイズを大きくしてしまっている模様。
ブロックの回転方法について、やはり他の解法だと24通り試すことができていた模様。どの辺がバグっていたか見直しが必要だなあ。
今回はコンテストが開始して１週間以上、何もできてない状態でした。実装の開始が遅すぎです。
これまでの実績
前回に続いて、大きくレートを伸ばすことに成功しました。ヒューリスティックは青色目指して頑張ります。
総括
今回は、実装が大分出遅れたのが一番の反省点。とりあえず時間がありそうだからと後回しにしてたツケが、後々になって時間不足という結果を招いてしまいました。
また、今回のように乱択で適当な解法では、スコアの方も頭打ちになってくるというのがよくわかりました。上位陣の解法等を参考にして、具体的にどのようにすればスコアが伸ばせたかを研究していこうと思います。
ということで、また次回も頑張ります。
