MC Digital プログラミングコンテスト2023（AHC019）に参加して、 535,142,906,156点の 84位/786人 でした。
解法や所感について書いていきます。
解法
以下のような、２段階の乱択を行いました。
- 「各シルエット組から座標をランダムに1つずつ選び、BFSで同型を保ったまま出来るだけ大きく膨らませる(回転24パターン全て試す)、という操作を影を埋め切るまで繰り返す。」という乱択を5.0秒実施。
1.のベスト解に対して、後半1~7手を壊して1.と同様の乱択で再構築する作業を0.7秒実施。
それぞれのパートについて、もう少し詳しく説明していきます。
1.の乱択生成パートの詳細
両シルエット組について、正面・右側両方の影に含まれる座標（以降、「正当な座標」と呼びます。）の内、新規に１つ以上影を作れるものの中からランダムに座標を１つずつ選ぶ*1。
選んだ座標を種に、隣接6方向を遷移候補とするBFSを行い、シルエット組両方が正当かつ未使用*2である場合のみ遷移を許す形で、できるだけ大きく膨らませる。この操作を24回転全パターンについて試し、最も体積が大きかったものをブロックとして採用する。
この操作を、シルエットが埋まるまで繰り返すことでブロックのセットを生成する。
上記の処理を5.0秒経過するまで繰り返し実行し、スコアが最善だったものを 2 の処理に引き渡します。
また、ここに多少ヒューリスティックな工夫を加えていて、
1x1で突起していて、かつ影を作る上で必須である点は先んじて潰すようにしています。
具体的には、
- 正面・右側いずれかの影で、同一 z 座標上に自身以外の点がない*3。
- 隣接6マスの正当な座標が 0~1個
を満たす点を乱択の最初に優先して選ぶようにしています。
扱いにくい点(のはず)なので、それ同士で潰し合わせるなり、膨らませる起点に使うことで、後半に余らせないようにしたほうが良さそうだな、という判断の元で実施した手でした。
スコア的には、これで提出絶対スコアが 87G から 84G へと伸びています。
2.の後半手を壊して乱択再生成するパートの詳細
1.で生成したベスト解の最後から1~7手分を壊して*4、1.と同様の手法で乱択再構築する。
この処理を0.7秒実行し、スコアが最善のものを解答として選びます。
1. だけで時間一杯回しても、後半はほぼ更新されなくなってしまっていたので、その分をベスト解の改善に注力する意図でこれをしました。
序盤の置き方を変えると、影響が大きすぎて部分破壊の体を成さないのでは無いかなと思って、後半手を壊す形にしましたが、それで良かったのかどうかはあんまり分かっていないです。
スコア的には、これを入れたことで提出絶対スコアが 110G から 87G へと伸びています。
テストケース0001のビジュアライズ結果
提出コードはこちらです。 Submission #40299991 - MC Digital Programming Contest 2023（AtCoder Heuristic Contest 019）
解法に対する課題感
- ループ回数不足
- 大きいケースだと千回も回っていなかった。
- ローカルサーチ化したかったけどできなかった。近傍が思い付かず。
- ブロックの総体積と個数が一緒なら、大きさは均等にした方が有利なのだから、膨らませるだけ膨らませる はあまり上手くなかったかもしれない。
- コンテスト後TLで、置く場所を先に決め切って、それから全体的にバランス良く膨らませる、みたいな手法を見て良さそうだなと思った。
- 体積だけで無く、置く難易度も評価に組み入れるべきだった気がする。
- 隅を埋めたら高評価、みたいな工夫をしたかった。
- 解法手順の
2.で表現したかった気持ちは、MCTSが近かったかもなとコンテスト後のTLを見て思った*5。
コンテスト終了後の雑感
- 実装がとにかく重かった。今回もコンテスト期間が足りなかったなという気持ちに*6。
- 解法の
1.の手法ができたのが最終日前日の半ばとかだったので、そこから伸ばすための試行錯誤の時間がほとんど確保できなかったのが辛かった*7。
- 解法の
- 公式配布ツール内の、
is_same関数をメチャクチャ参考にした。というか３次元座標の扱い周りの知識が元々ほぼほぼなかったので、これがなかったらほとんど何もできなかった気すらする。 - 中盤くらいまで、最終形がどうなってるのかが想像つかなすぎて、何を優先して用意するべきかが分からず動きづらかった。
終わりに
最初問題を開いた時の印象は、「うっ３Dか、嫌だな」だったんですが、
やってみると思っていたよりずっと扱いやすく作られていて、終始のめり込んで楽しんで取り組めていました。
AHCラジオ内で、３Dビジュアライザは最近できた 的な話があった気がする*8ので、これから３D問題がぼちぼち出てくる感じになるんですかね。
私事ですが、今回で黄色への昇格を達成することができました！とても嬉しい！
これからも精進していこうと思います。次は総合順位100位以内を目標にしようかなと思っています。頑張るぞい。
