AHC 019 のおもいで (MC Digital プログラミングコンテスト2023)
AHC 019 Silhouette Block Puzzle Creation
2023/3/18-4/2
概要
ブロック積み木をデザインしたい。指定した2セットの影の形を作れるような積み木セットを提案してください。子ども用なので、少数の大きいブロックだけで、無駄なブロックがでないように作ってくれると嬉しい。
（説明が難しいので詳しくは問題を参照）
取り掛かり
第一印象
・ビジュアライザがすごい。まわる！拡大縮小も無限！作った人すごい。
・説明文が丁寧。
（「ブロックは全て使い切らなくて良い。（が、全て使い切る方が良いスコアが得られる）」、「評価値は低ければ低いほど良い。」）
・評価式がわかりやすい。
・制限時間６秒でちょっと長め。
・最大でも14**3= 2744 で少なくともO(全ブロック数**2)まではいける。
ぱっと見では最適解がすぐ出そう？と思ったが、よく考えてみるとすごく難しい。
ある一つのブロックの形を仮に確定させたとして、それをどこに配置するのかでまったくその後が変わってくる。
二つの図形をランダムに分解して共通する立体を選んでいく方法もありそうだが、回転させた二つの立体が相似であることをどのように検出するのか？
前回(AHC018 - Excavation)のようにグラフに帰着させてみる…？立体で？
…これは無理。実装はできない。誰もできていないんじゃないかと、スコア表をみるとちゃんと有効な点数をとっている方々がちらほら。天才か。
そしておそらくテストプログラムをお試し提出した横並び点数がずらり。多くの方が苦労している感じはうかがえる。
とりあえず力ずくでやる。
なんとなく、トップの人の解法を想像すると、ブロックをちょっと消してまた増やして、とやっていそうな気がする。きっと最適な方法は適当に作った後の焼きなましなのだろう。
しかし、それにつながるような実装の方法が、取り掛かりすらわからない。AGCとかの1000点問題くらいわからない。
3日間ほど、1行も書かずに悩み続けたあと、なにもしないよりは、とランダムで運任せの解答をまずやってみる。
評価式からわかるのは、
・ブロック数は少ない方が良い。
・同じブロック数なら、一つ一つは大きいほうがいい。
・同じブロック数で合計の大きさが同じなら、一つ一つは大きさのムラがない方が良い(例：1/19 + 1/1 > 1/10 +1/10)。
・片方でしか使わないブロックはないほうが良い（大事）。
・片方でしか使わないブロックがある場合は、合計サイズのみが問題で、ひとつひとつの大きさは関係ない。
これをできるだけ満たすように…。
-流れ-
①f1,r1(と、f2,r2)両方に投影される位置は、それぞれのブロック組みでの"必要かも"Setとして、その(x,y,z)座標のtupleとして、連想配列で持っておく。これは、同時に"あっても良い位置"Setとしても別に持っておく。
②第1シルエット組で"必要かも"とされる位置と、第2シルエット組で"あっても良い"とされる位置を、ランダムに対応させて、ブロックを置くと決める。
③このブロックについて、第１シルエット組と第２シルエット組での対応させる回転方向を決める。24通りあるので、全部試して一番広がりそうな方向を決める。
④広さ優先探索で、第１シルエット組と第２シルエット組の両方で"あっても良い位置"Setに含まれる隣接区画がある限り、ブロックの大きさを広げていく。広がらなくなったら、そのブロックには番号を与えて確定。
⑤使ってしまった位置は"あっても良い位置"Setから外す。ブロックを置いたことにより、ブロックを必ずしも置かなくても良くなった位置は"必要かも"Setから外す。
⑥第１シルエット組、第２シルエット組の両方から"必要かも"の位置がなくなるまで繰り返す。途中でどちらかの"あっても良い"位置が枯渇した場合、残りの"必要かも"位置には、必要最低限の数の大きさ１の積み木を敷き詰める。
⑦出来上がった答えを採点して、点数が改善していれば採用。②からまた繰り返す。規定の時間が来たらループから抜けて、点数が一番良い答えを出力する。
--
色々とバグも出しつつ半日ほど掛かってpypyで書き終える（今回はnumpyは使わなかった）。
得点：5411億点
順位：51位 /提出450人くらい
まさかの２ケタ台！おもわず順位表をスクリーンショットしてしまう。
まさかこれでいいのか…。。
数日の考察と超高速化。
AHC解説放送はすごく参考になる。
「手元で時間をかけて回してみた結果がこちらです。一本に繋がる道を一緒にやってしまった方がいいのがよくわかります」(AHC017-Road Repair 解説放送)
…ということで、とりあえずできたプログラムを、手元で10分くらいじっくり回してみる。
わかったことは、
・ランダム方式も時間をかけまくれば結構いい感じになる。
・しっかり時間をかけていいパターンを掘り当てれば、片方の組でしか使わないブロックはほぼ発生しない。
しかも、数秒間から10分間くらいまでの間なら、計算時間をかければかけるほど、いい結果がでることがわかった。
理論的なアプローチが思いつかない以上、やることは高速化しかない。
AHC018の解説放送で「今回は久しぶりにpythonでも優勝できる可能性があった回でした」
と聞いてからこの数週間、０からRustを学んでいた成果を発揮するときが来た。
入門書を引きながら、所有権でエラーを出しまくりながら、トレイトも構造体も全く使わず（使えず）に、４日間かけて、「pypyのコードと全く同じことをするだけ」のRustコードを完成させる。
得点：1252億点
順位：102位→42位 /提出500人くらい
得点は1/4以下まで改善。Rustすごい。
n = 14で一番計算量の多そうなseed19が5秒間で何回トライできているか確認してみると、
pypy：19回
Rust：787回
書き方にもよるのだろうが、もはや勝負にならない…！！
細かくいじる。
ビジュアライザをみると、他のブロックに隠れてしまってもはや不要なのではないかというブロックが散見される。試しにいくつか手動で消して試してみると、なんと、丸ごと消しても成立するブロックがある！
ブロックの個数は少ない方が評価は良くなるので、
「丸ごと消しても問題ないブロック塊を探して、その中から構成ブロック数が小さい方ものを優先的に消していってブロック番号を詰める（正確には出力時に参照するブロック番号変換表を一緒に返す）」関数を作って、各ループごとに、「ブロックセットをとりあえず組み上げる→不要なブロックを消す→採点して暫定採用するか決める」の流れにする。あまり得点に変化なし。
少しトライ回数が落ちているために効果が相殺されている様子。「ブロックセットをとりあえず組み上げる→（無駄ブロックがあるかもしれない状況で）採点→結果が良いときだけ不要ブロックを消す→採点して暫定採用するか決める」に変更。少し良くなった。
ビジュアライザ的には、n = 5 とかではもはや最適解に近そうなので、nが大きいところで改善が必要そう。
衝撃の発見。
手掛かりがないか問題文を眺めていて、衝撃の事実に気づく。
問題文にあるseed 0 のf1,r1,f2,r2の画像をよくみると…
M C 2 3 ！！！
うーん、おしゃれ。
そういえばMC Digitalのロゴがすでにシルエットぽいし。
気づいてやる気が出たが、点数は伸びなかった。
完全運任せから、ちょっと運任せに。
ここまで、あるブロックを生成するときは、第1シルエット組みでの位置と第2シルエット組での位置を対応させるときに、ペア選びはランダム一発決めで確定し、そのペアのうちで一番いい回転方向を探す流れだった。これを、ランダムで仮のペア選びを行ったあと、24方向回転で対応させてみて、上下左右前後の6方向に伸ばせる方向数が一番多い回転方向をキープしておき、（シルエット1側は固定しておいて、シルエット２側の）ペア選びからやり直して何回か繰り返した後、一番都合の良いペアと回転方向で確定するように変更した。
（この流れで全てのブロックが組み上がったあとは、採点してまた０からブロックを組み始める、のを延々と繰り返す。）
スコアの比較には、相対スコアを使用する。
「合計スコアが変わらなくても、相対スコアが伸びるときがある」
「自分の過去のスコアに対して比較するのが良い」
(AHC解説)
ここまでの最良スコアを出したコードを2回回して、その平均を基準スコアとして相対スコアで評価していく。
nペアx24方向回転で、最適なnを探す。
速度とのトレードオフのようで、10〜20ペアの比較が最適な様子。
相対スコアは1.2倍前後になる。
得点：959億点 ※桁が一つ下がった！
順位：62位→61位
62位の人ごめん。
迷走してはまる。
上下左右前後の6方向が合うかどうかだけをみてペアを選んでスコアが改善するなら、周囲26マス(3*3*3-1)が合うかどうか見れば、スコアがすごく改善するのはないだろうか？
と、試してみるが、相対スコアは0.6倍に悪化。
どうも計算量が増えてしまっただけではないようだ...。
おそらく、斜め方向「だけ」一致していても良い一致だと判断されるのが、悪さをしているようだ。
上下左右前後の一致は「すごく良い一致(良さポイント10倍、的な)」としてみたが、相対スコアはさらに悪化して0.4倍。
ビジュアライザとにらめっこし続けて原因を考えたところ、最初の数ブロックが一致しすぎて巨大化して、最後に1マスだけ取り残されて、「大きさ1ブロック」ができやすい状況になってしまっている？ような気がする。
この26マス方式の実装は結構苦労したので捨てがたいが、どんどん深みにはまっていくので、この方針は原因不明のまま諦める。3日間分のロールバック。
速度を上げて運勝負。
回転の計算に使っていた行列は、コードの中で簡単な前計算をして算出してmutable vectorとして使っていた。
これはseed値によっても全く変わらない定数なので、constantなglobal配列として直接コード内に書き込んでみた。これで、関数に飛ぶたびに引数として渡さなくて良くなるし、僅かな前計算も要らなくなるし、immutableで置けるから事故もなくなるし、で良し。
また、vectorのiteratorで回していた処理の一部を、連想配列に変える。
そして、std::HashMapはクラッキング対策のために少し遅いアルゴリズムを使っているらしいので、rust_c::FxHashMapに変更してみる。
相対スコアは1.6倍に改善。
n=14のseed 19で何回試行できているかをカウントしてみると、
(pypy)19回→(rust実装直後)787回→(今回)1500回前後
不要ブロック消しや6方向一致確認作業など処理は増えているのに、計算速度はかなり良い感じ。
得点：795億点
順位：73位→53位/提出700人くらい
良いアルゴリズムがあるのかもしれないが、自分としては速度での殴り合いになってきた感じがある。
※↓あとから考えてみると一番高速化に効果があったような気がする回転パターンの前計算による連想配列化。前計算時間1.5msくらいで辞書型を作成できる。
ループを抜ける時間はどのくらいがいいのかな？
「システムテストでは実行時間が数％延びる」ので、TLEにならない程度でできるだけ十分な実行時間が欲しい。
以前のAHC(python3で提出)では、制限時間6秒に対して、whileループを４秒を超過した時点で抜けるように設定したのに、システムテストでの実行時間は5.2秒ほどで、危ない思いをした。
過去のコンテストでTLEになっている他の人のコードを見てみると、whileを抜けるのが500ms前でも全てTLEしている人もいれば、100ms前でも１個だけTLEして済んでいる人もいて、様々なようす。
結局は、どのくらいループ一回あたりが重いかで、変わってくるのだろう。
自分のコードをAtCoderサーバーでチェックしてみると、1ループあたりの必要時間は、ほとんどのケースで0.2ms〜5ms程度。時々、10〜30ms。非常にまれに、90ms。
出力には、最大で4msec。
今回、６秒の制限に対して、whileループをmain()の開始から5500 msec以上で抜けることにしている。
システムテストで「10%」のびるとすれば、実行時間予測は最悪でも
5500+(90+4)x(1.1) = 5603 ms
で、いけそう？
AHC017の1位の方(C++)は5930msで設定していて本番は5988msで全てACしている…のを真似していいのだろうか。
結局、5400 msにした。
すべて1割増しでも5940msで、安心感。
おわり。
最終の土日、nの値で調整かけてみようとしてちょっとだけいじって全く変わらず（むしろ悪化するのでやめた）、まあ良いかとのんびりしている間に50位くらいだったのがいつの間にか80位近くまで下がっている。みんなすごい。
結構難しくて理論的には攻められなかったけれど、高速化というところで学ぶところは多かった回でした。でもまさかの暫定100位以内！自分のような素人でもこんな位置が取れることもあるんだなとちょっと満足。
二週間一緒に走った皆様、お疲れ様でした。
↑最終提出で作ったseed 0。
システムテスト終わったら、TLEだったかどうか追記するかもしれません。
システムテスト後。
TLEしてませんでした。実行時間は、5406ms。
ちょっともったいなかったかな。この結果は次回に活かせそう。
wata-adminさんがRustで書いていたのでみてみると、注釈付きで実行時間の管理もコード内で解説されていた！ちょっと自分のスキルが足りなくて十分に解読できないけれどよく読んでみよう。
結果はまさかの100位以内。おどろきの黄パフォ！
他の参加者の解説を読むと上位の方はやっぱり"壊して足して"をやっているようす。
自分もやりたかったことだけど、２つの立体が連動していて、どう壊せばバグらないのかてんで見当がつかず、難しくて結局手がつけられなかった。解説読ませていただきます！
