こんにちは。競技プログラミングをしているssaattooと申します。MC Digital プログラミングコンテスト2023（AtCoder Heuristic Contest 019）に参加して 41位でした．
反省、または誰かの為になることを期待して参加記録を残します。
問題概要
正面、右側から見たシルエットを満たすような立体を複数のブロックを用いて作るパズルがある。立体パズルが２個与えられるので、同じブロックを使って２個の立体パズルを完成させたい。なお、ブロックは大きいほうが良い。
https://atcoder.jp/contests/ahc019/tasks/ahc019_a
解法
基本方針
- パズル（シルエット組）１とパズル２からランダムで座標と向きを決めて同時にブロックを操作することで同一なブロックを配置する。
- ブロックの短縮・削除・延長を組み合わせたものを近傍とする部分破壊焼きなましを行う。
- スコア計算はサイズ２以上のブロックをサイズで降順ソートし、順番にシルエットの完成に寄与するなら採用する。それでもシルエットが完成しなかった場合にサイズ１のブロックを追加する。最終的に採用しなかったブロックはすべて削除する。
ブロックの操作について
まず、無からサイズ２以上のブロックを生成するときは、パズル１とパズル２からランダムに座標を選択し始点とします（始点と言っても操作で始点が無くなることもあります）。次にブロックを伸長する際の向きを決定しますが、パズル１は向き０としてよく、パズル２の向きはあり得る24通りからランダムに選択しました。ブロックを伸長・短縮するときはこの向きに従い操作します（図２）。
ブロックの伸長は座標をランダムに選びbfsをして可能な限り大きくしました。ブロックを伸長する時にはブロックと新たに加えられるブロックに辺を張ることで、ブロックのサイズを計算できるようにしました。
ブロックの削除は、ブロックが木構造なので枝を切ります。正確には、座標をランダムに選択し、その座標に存在するある１辺を辿っていけるすべてのブロックを削除しました。他の方は始点を固定しているような気がするのですが、これで始点に縛られずにブロックの操作ができます（効果はなさそうです）。
焼きなましについて
近傍は３つ用意しました。
- （１サイズ分短縮）×複数＋（生成 or 伸長）×複数
- （枝を短縮）×複数＋（生成 or 伸長）×複数
- （１ブロック削除）×１＋（生成 or 伸長）×複数
温度は低めに設定しました。イテレーションは数十万回でした。
日記
自分の考察メモとして書いていたので、読み辛い可能性があります。
コンテスト１日目
忙しい．
コンテスト２日目
忙しい．
コンテスト３日目
問題を読んだ．難しすぎないか？
４つのシルエットのうち1つをZ軸に沿ってD個に分割．それらのZ±1のブロック間でブロックを受け渡しする．選んでいない方のシルエット組でこれらを配置できるか判定する？
コンテスト４日目
自由度が大きすぎて何も思いつかないよ．
サンプルプログラムはブロックを置くことができる最大の空間．一方のペアでつくった合法なブロックは，もう一方のペアでは合法となる場所が少なくて全探索できたりしないかな．
方針案
- サンプルプログラムのブロックをペア１とペア２でそれぞれ繋げる/破壊してペア間で類似度の仮のスコア計算する焼きなましorビームサーチ．
- ブロックを最初に何種類か作っておいてそれからいい組み合わせを探す．
- ペアとペアの空間を繋ぎ合わせてdfs/bfsでブロックを作る．
方針１をとりあえず実装してみようと思うけど，初手焼きなましは悪いパターンだね．この問題での貪欲って何だろう？
方針１を実装するにあたって必要なのは，ブロックが同一の形か判定する方法．Graphoreanでは次数列をソートしたもので判定していた．炭化水素の命名方法みたいに一意に決められないか？完全に一致していなくても似ているかどうかを判定できないと焼けない気がする．それとも同じ形のブロックを伸ばしたり縮めることで一致しない類似度は無視できるようにするか．
コンテスト５日目
忙しい．バグっている．
コンテスト６日目
バグが取れてようやく初提出で106位．ブロックを結合・分離する焼きなまし．
ブロック組を作った後にシルエットをつくるのに不要なものを除去していないからそれを除去したら倍の点くらいかな．焼きなましのスコア計算が除去前だからそこも直す必要がある．ブロックの個数が多すぎる（seed 0 で12個）からブロック数を制限する必要があるかも．焼きなまし時にシルエットが完成しているかどうかも判定しておいた方がいいかな？ブロックの破壊からのどこかを始点にして伸ばせるだけ伸ばす部分破壊焼きなましもよさそう．
２回目提出で8Bで36位．ブロック数の制限とスコア計算を改善した．最終20位は今の40Bくらいは必要だと思う．Dが小さいときは10^8台のスコアが出ているからせいぜい改善して２～３倍くらい．Dが大きいときの改善が重要だろう．
次はseed 0が50を下回ったら提出しよう．改善点としては，Dによってブロック数上限と温度を変更する．始点と向きを決めたらbfsで最大まで伸ばすのがこの問題の貪欲かな？部分破壊とこの貪欲をセットにした遷移も追加したい．結合と分離をセットにした遷移も．初期の動きが強く影響しそうだから多点スタートが必要かも．最終出力でブロックの選択を体積が大きい順にしているけど，0.1秒くらい焼けば少し改善しそう．
コンテスト７日目
1 add 1 remove, 1 add 2 remove, ブロックを消して貪欲に作り直す近傍を追加したけど全然伸びない．
best_scoreが一定時間更新しなかったら部分破壊するようにしたのを提出．11Bで35位．
初期温度を３から１にしたら絶対スコアは良くなったけど相対スコアは下がった．最後に調整する．
もし両方にサイズ１のブロックがあったら対応させる．→対応させた．
部分破壊の所がバグっていたので修正して提出．15Bで24位．seed 0 もたまに50を割った．
何度も使う関数内の配列はstaticにする．初期化不要の配列にするのも検討．100倍高速化したらもともとスコアが大きいものは２～３分の一くらいになるから高速化も重要かも．
良さそうな改善が尽きてきたので実行時間を延ばした解から学んでみる．図３の右が実行時間を100倍にしたものであり，点も６割ほどになっている．大きすぎるブロックが無くなり，ブロックサイズは大体均等になっていることが観察できた．大きさ制限は難しい気がする．なんとか上手い具合に均等にする方法はないものか．
D毎にブロック個数の制限を調べる．
ブロックを一つ破壊した後に，既存の使用済みブロックから伸ばせるだけ伸ばす近傍はどうか？ある空間に含まれるブロック関連のものをすべて消して再生産する近傍は．
実行ごとに２倍ほど点数にムラがあるのは何でだ．
コンテスト８日目
estieのやつに似ているからその時の解説を読みなおそう．合法手の計算がボトルネックになっていたらしい．点数が安定しないときは状態を複数持っておく．このときは１長方形の追加，削除は良い近傍ではなく，部分破壊貪欲が強かった．
ある(x, y, z)の方向dirの辺を使って到達可能なブロックを全削除する近傍．これはブロックが分断されないよね？ 使用済みのブロックから伸ばせるだけ伸ばす．
部分破壊した後の再構築は一つの始点から伸ばせるだけ伸ばしていたけど，そうすると一つのブロックばかり大きくなってしまうので，何回か一つ伸ばすのを繰り返す方が平均的に大きくなりそう．
提出153->1489で悪化．
コンテスト９日目
やはりブロックサイズに差があるもののスコアが悪い気がする．大きすぎるブロックのaddを禁止するか．最小サイズの５倍以上になるのを禁止とか？毎回bfsで大きさ計算するのは重そう．
どこを変えたか覚えていないほど些細な改善をして提出．17Bで29位．
キックをイテレーション回数から時間に変えた．18.4Bで28位．
コンテスト10日目
夢でブロックのedgeの向きを変更する方法を思いついたけど意味なさそう．
キック時に一つのブロックを全破壊していたのを，１～４ブロックの一部分を破壊するのに変更して提出．18.14B 30位→21.2Bで27位．
ブロックのサイズを保持できないかな．できればadd, removeはコピー・計算前にrejectできるんだけど．
サイズ２のブロックは向きとmappingを変更できる．
実行時間を10倍にしたら点数が半減するらしい．案が無くなってきたしそろそろ高速化の時間か．
コンテスト11日目
(x, y, z) は事前に合法なものを準備．ブロックは木構造なのでhoumon配列を用意せずにmae座標を持っておけばオーケー．addたくさんする近傍．
サイズを事前に計算していても，存在するブロック全てがスコア計算に使われているわけではないから事前にrejectできないことに気づいた．removeしてもスコアに影響しないものもあるのだ．
addでスコアが悪化している試行がある．厳密解ではなくサイズで降順sortして順番に足しているからそうなるのだろう．スコア計算を高速で正確にできるかな．addを問答不要で受理したらiterは伸びたけどスコアが下がった．スコア計算を見直す．まずソート配列を適当にスワップした点数を調べる．
コンテスト12日目
add, removeはいちいちコピーせずにシミュレーションすればよい。空間破壊。
近傍の割合をoptunaで何とかしたい。
一つ一つadd, removeする意味ってあるのか？スコア計算するときはもうaddできない状態でないといけないのでは。remove系をしてから追加できなくなるまでadd系をする近傍のみにした。19.14B31位から16.89B36位に下がった。ローカルでは上がったのに。時間経過とともに変化する部分を小さくするようなパラメータ調整が必要。あとラスト少しはいままでの近傍のほうがいいかも。
コンテスト13日目
takumiさんのを参考にしてoptuna。optunaで近傍の割合を調整しようとしてみたけど、100ケース100トライアルじゃお手製の割合に全く勝てなかった。14近傍の割合の和が100％になるようにしたいけど、下のコードみたいにしたらいい感じにサンプリングしてくれなさそう。
コンテスト14日目
Dが大きいときは7.cppが優れているので組み合わせたのを提出で18,3Bで36位。たぶん暫定テストはDが小さいのが多い。
optunaに温度を調整させてみたけどお手製のものと全く同じ値がでてきた。
近傍の割合を72ケース120トライアルで調整したら過学習？で悪化した。これを参考にした。
最後に使わないものをすべてremoveしてaddする。
計算に使わないブロックをすべて(確率でもいい)消す近傍。ブロック個数がDになるまで破壊する近傍。
計算に使わないブロックをすべて消す近傍（4%）を追加したらそこそこ伸びた。20.3Bで33位。
すべてのスコア計算時に不要なブロックを除去するようにした。そうすると１個ずつaddするのを繰り返す近傍の遷移確率が低くなったのでそれらを消した。21.3B 32位。
なんかDが大きいほうがスコアいいらしい。
コンテスト15日目
ブロックが既に置かれているときの厳密解が最小費用流で求まると考えたけど，コストが１流量あたりらしいので無理．そもそもブロック数が高々20個なのでbit全探索で行けるか．bit全探索だと一回のcalc_scoreで9msかかっている．
僅かに高速化して22.3Bで37位。最終日は配列を１次元にしたい。あとブロック個数の最大値調整。
コンテスト16日目
多次元配列を1次元にしたらイテレーションが1.5倍くらいになった。最終提出22.2B, 45位。
終わりに
良かった点
- 結果はともかく、立ち回りが理想に近かった。
- 役には立たなかったけど初めてoptunaを使えたり、並列実行の仕組みについてほんの少しわかったり技術的な成長があった。
悪かった点
- 焼きなましという初歩的な方針まではスムーズにいけたが、それからの考察や改善ができなかった。
- optunaを有効活用できなかった。
非常に自由度が高い問題で途方に暮れました。たまたま焼きなましという型にはめられたからましな順位になったけど実力不足を感じました。今回でレーティングが黄色になりましたが橙色になるためにもっと考察を頑張りたいです。
