週記(23/03/19)：AHC019参加記(前半編)

今週のまとめ

• AHC019に参加。瞬間最大風速では5位に
• 会社主催の飲み会に初めて参加。会社の特徴が出て面白い

です。

「MC Digital プログラミングコンテスト2023（AHC019）」は最初の方針が当たりで5位まで行ったのですが、そのあとロマン？を求めすぎて時間を浪費していました。

3/18(Sat)

AHC019スタート。2つのシルエットが2組与えられて、それを同時に組めるブロックのセットを作る問題。

Ubuntuにdocker入れてJupyter notebook用の環境を作っているのですがJupyter notebookは開くもののアクセス権がない？とかで保存できない。

調べたらベースイメージを変えたときにユーザが変わったのが原因。ユーザの「jovyan」って誰？まさかイメージの作者？？と思ったら個人名ではなく「木星(Jupyter)の住民」的な意味らしい^[1]「jovyan って誰？」。知らなかった…

サンプルコードと同様に1x1x1セルで埋めてシルエット条件を満たすロジックを作成。

Visualizerがきれい。ここから「Front/Right両方ともすでにシルエット条件を満たしている合は追加しない」というのを入れると

だいぶんとスッキリした解になり平均スコア79.5Gでいったんこれをsubmit。

この問題の難しさはざっくり

• 同じ形のブロックを使う
• ただし回転はOK
• シルエットを満たす
• ブロックは個数が少なく、できるだけ均等な大きさが良い

の4つくらいあって最後のは後で何とか頑張るとして前半3つをどう満たしたものか…。

初期方針の立て方は

人間が手で頑張るならどうする？

が定石ですが今回は問題が難しすぎてどう頑張れば良いのか想像もつかないですね。

ブロックの形を決め打ってそれを置いていくか、立体1, 2で置ける同じ形のブロックを探して置いていくか…。うーん、後者かなぁ。

と考えてたら質問で「物理的に不可能な配置も解として認められる？」が出てて

回答は「子どもたちは超能力でブロックをワープさせることによりそのような配置を作ることが出来ます。」でOKらしい（笑）。それだけ能力あるなら子ども達にブロックも作らせた方がよくない？という気もしますが、まぁ頑張ってブロックを作りましょう。

この日はトヨタコン＆競プロer大宴会が開かれていたので強い人の半分くらいはまだ参加していない感じ。それでもtomerunさんが1位ですげーと思ったら次の瞬間にShun_PIさんが順位表を一気に圧縮(2位でも20Gくらい)してて強い人はやはり強い。

3/19(Sun)

いったん回転はせず同型なブロックを貪欲に置いていくロジックを書いてみます。

おおー、一気に必要なブロックが減ってスコアも1/6に。これをsubmitして平均スコア12.3Gで17位。

回転を考慮するとより自由度が上がって良くなるハズ。x, y, z軸の90度回転ができると全部で何通りの回転ができるのだろう？と考えるも良く分からず全列挙するか！で列挙するスクリプト書きました。

24通りあるらしい。24通りか…うーん、x, y, zを3軸のどこに置くかで3!通りあって、向きがそれぞれ2通りと考えると48通りなんだけどな。まぁプログラムを信じましょう。

ドキドキしながら回転も試して探すと

おおー、ちゃんとブロックを回転させて配置している！ちょっと感動。すでに自分が作れるとは思えないレベルの解を出してくれてます。

今までブロックを座標の小さい順に作っていたのをランダムに場所を選ぶように変更。これを複数回回すようにすると思った以上に効果があって平均スコアが7.08Gだったのが2.30Gまで改善。これをsubmitするとなんと5位！

この瞬間に終わって！と思いましたが、シンプルなロジックでここまで来ているので着手が早かっただけかなーというのが正直なところ。

夜に200K試行を回して今日は終了。

3/20(Mon)

200K試行だと平均スコアは1.18Gまで改善。時間をかければかけるほど改善します。

ちょっと不思議なのは良いスコアを出すには

• 少ないブロックで作る
• 各ブロックを均等な大きさにする

の両方が必要で今のロジックは貪欲にブロックを大きくするのでブロック数を少なくことしか考えていないです。今のレベルだと時間をかけた分、ブロックの少ない解が見つかっているのでしょうね。

今のロジックはブロックを貪欲に大きくするので終盤に小さいブロックしか置けなくなることがあるのでブロックサイズに制限をかけてみました。ちょっと改善したものの思ったほど効果出ず。

3/21(Tue)

この日は問題の「難しさ」をパターン化できないかと思って統計を作ってました。Visualizerで問題を見ていると特徴的なパターンがあって

長方形っぽいのが並ぶもの(ex. seed=8)や

ギザギザのものが並ぶもの(ex. seed=2028)があって、必要なブロック数が違うのでうまく特徴づけたいのがモチベーション。ブロック数が分かればブロックのサイズもおおよそ決めてよいはず。

• シルエット制約を満たす立体の最大/最小の大きさ
• シルエット制約の空白制約の多さ
• シルエット制約の各点の隣接数

あたりを出してみて確かに特徴を捉えられそうというのに満足してこの日は終了。

3/22(Wed)

ひょっとしたら1個のブロックで2組のシルエットを満たせることがある！？と夢想して探してみたものの見つからず、この方針は空振り。

3/23(Thr)

Dが小さければギリギリ厳密解が出せるんじゃないの？と思いはじめ、厳密解が出せなくても難しさが分かればそれを緩和したヒューリスティックを構成するのが王道だろうという気がしてきて厳密解法を書いてみることに。

厳密解法を調べる過程で「Pythonによる図形詰込みアルゴリズム入門」を見ていたら詰める順序^[2]DBL順序といって座標軸の優先度を決めて3次元の点間の順序を導入する。を決めて詰めていく方法が書かれていてこれは使えそう。

この考えも取り込んで厳密解法を書いて実行してみたもののなぜか既知の解より悪かったりでデバッグに苦労。

ブロックのZobrist hashの作り方がまずくて衝突していたのが原因。この手のバグは本当にデバッグがしんどい(Hash checkを外すと計算時間が爆発して再現しない)。

ようやく夜中に動いてseed=77で250秒かけて厳密解を算出。今までの解より良い解が見つかってさすが全探索。

ただ、計算時間的に6秒に収まりそうにないのでどこまでこだわるか悩ましい。

3/24(Fri)

この日は送別会で初めて会社主催の飲み会に参加。今の会社はデザイナさんがいて、イベント時もうまくアレンジされていてて華やかでした。

退任される方は転職時に面接、オファーしてくれた方で、入社後の最初の仕事もご一緒してくれて最後何とか形になったのもその方のおかげなので感謝しかありません。

この日はだいぶんとアルコールが入ったのでAHCはお休み。

3/25(Sat)

厳密解法で解けない問題があるのが気になってデバッグ。なかなかうまくいかず途中で次女とケーキを食べに行って気分転換。

昨日からお酒にケーキと文字通り自分に甘い生活になってしまってますね…。

この日もかなりの時間をかけて厳密解法の改善、高速化をしていました。D=5の200問中147問は厳密解が出るところまできたものの9並列で1時間半近くかかってて、「模範解答」としては使えるものの提出ロジックに含めるのは厳しそう。

あまり本筋で進捗が出ていなくてそろそろ厳密解法を切り上げてヒューリスティック解法に切り替えないと…と頭では分かってても厳密解法が気になって集中力が分散する状態で折り返し地点を迎えました。

（後半編に続きます）

関連記事

• 前週の週記: 「体調が…」
• 翌週の週記: 「週記(23/03/26)：AHC019参加記(後半編)」