2023年6月: 短期AHCチャレンジは…

今月のまとめ

TOYOTA Programming Contest 2023 Summerが決勝200名でのオンサイト開催でひょっとしたら出られるかも！？と思い準備にささげた1か月でした。

結果的には

• リハーサルも兼ねて出たAHC020: 448位
• 予選(AHC021): 651位

と完敗でしたが、準備したことと今後の課題をまとめておきます。

短期AHCに向けた準備

上位200名での決勝オンサイト開催が発表され当時の国内順位が202位

だったのでこれは可能性があるかもと思い予選(AHC021)に出ることにしました。

ただ、参加したことがあるのはすべて長期コンで4時間の短期コンは初めてだったのでちゃんと準備しないと難しいだろうなと思っていました。

準備の流れ

• Thunderさん本で探索手法の基本を復習＆テンプレート整備
• AHC015バチャ
• AHC020参加
• AHC020復習

という流れで進めました。

Thunderさん本で探索手法の基本を復習＆テンプレート整備

ちょうど6月に入ったタイミングからThunderさん本こと「ゲームで学ぶ探索アルゴリズム実践入門」を読みコードを書いて動かしていました。

ゲームで学ぶ探索アルゴリズム実践入門～木探索とメタヒューリスティクス

今まで我流でやっていてBeam/Chokudai searchの実装はこの本で初めて知りました。大体1週間で5章のThunder searchまで読みました。

Thunderさん本を読んで基本となる探索手法を押さえつつコンテスト中に一から書くと時間がかかるので

• 貪欲法、Beam search、Chokudai search
• 山登り法、焼きなまし法

は自前のテンプレートとして用意しました。

AHC015バチャ

短期(4時間)コンがどういうものかまったくわからなかったのでAHC020の前にAHC015のバチャをしました。

3種類のキャンディの登場順が与えられますが、それがどの位置に置かれるかは不明という状態で箱を傾けてできるだけ大きな連結成分を作る問題です。

やってみた感想は

全然時間が足りない！

で正の得点を得るのに1時間、スコア計算があって手元でバッチ実行できるまで1時間で簡単な貪欲と種類決め打ちで大きくする方針を試すもうまくいかずUCTを実装しようとしているうちに終了でした。

実際にやってみて

• 業務的に正しい設計、実装にこだわり過ぎた
• 長期コンの資材を使いまわそうとして時間がかかった
• 問題固有の考察に時間を使えなかった
• 新規に重実装して間に合わなかった

と反省点だらけでいやー、思っていたより大変だぞ…というのが率直な感想でした。

AHC020参加

バチャでの教訓を頭にいれつつ「ALGO ARTIS プログラミングコンテスト2023」に参加しました。

放送局、住民位置が与えられるのでコストが小さくなるようにどの放送局を使うかと出力強度を決める問題です。

ここでもやりたかったことの実装が間に合わずほろにがデビューになりました。短期コンむずいですねぇ。

提出解法は最小全域木を作り、出力はルールベースで「住民から見た最寄りの放送局が最も遠い住民をカバー」にしました。

本当はそこから

• 放送局の使う/使わないの調整
• 出力を足し引きして調整
• 不要な経路を削除

としたかったのですが、オブジェクトのコピーがうまくいかないバグにはまって時間を溶かして終了…。

今思うと不要な経路の削除だけでもスコアが改善できたのと指定したノードを含む木を求める問題は「最小シュタイナー木」問題でAHC018でも現れた問題でした。

AHC020の反省は

• 長期コンの資材を使いまわそうとして時間がかかった
• 問題固有の考察/実装以外のところでバグらせない、事前につぶしておく
• 部分的に有名問題が現れるので対応を押さえておく

で1つ目はAHC015と同じで2つ目は自作テンプレートをベースに高速化しようとしてバグらせました。経験を積むしかないですが一度ハマったところは再発しないようにメモなりコメントなりに残しておくことにします。

3つ目は今回の問題も冷静に見ると「集合被覆問題」＋「最小シュタイナー木問題」になっています。テンプレート整備を兼ねて有名問題を解いても良いかもしれませんね。

AHC020復習

本当はAHC021に向けてAHC020はササっと復習終わらせようと思いましたがどっぷり2週間近く楽しめました。

主な改善は

• 先に出力強度を決め出力 > 0の放送局のみ最短路でつないでいく
• 出力強度を焼きなまし法で改善

でアイディアを試す⇒改善が続いて楽しかったのですがここからピタッと改善が止まり

• 出力強度の調整を集合被覆問題として解く
• シュタイナー木も焼きなます

を入れましたが計算時間の増加に見合う成果がでず結果的に長期コン並みにどっぷり取り組むことになりました。最終的に

• 高速化をかなり頑張る
• 出力強度の調整とシュタイナー木問題を分ける
• 出力強度の調整時には経路コストはざっくり仮のコストで求める

として何とか504.5M(本番2位相当)までスコアがを伸ばせました^[1]最初の解と比べて重複が少なく無駄のない配置/出力になってますね。ビジュアライザで改善を分かりやすく実感できるのも楽しいですね。！

AHC020は解説動画や記事で作問者のterryさんが問題を作るうえで意識したことや解法を説明されていてて、特に問題を作るうえで意識されたことは「なるほど！」と思える話ばかりで後日談含めて楽しめました。

ALGO ARTISさん, terryさん, AtCoderの皆様ありがとうございました^[2]転職するのがあと1年遅ければALGO ARTISさんも受けていたのでは…と思いました。。

さて、復習が終わったのが6月23日で2日後にAHC021が控えていたので長期コン用の資材を手直し少なく流用できるように改修しているうちにAHC021を迎えました。

AHC021

ついにトヨタコン予選のAHC021が開始。

三角形状に並べられたボールに数字が書かれており移動させることで「上のボールの数字 [math] < [/math] 下のボールの数字」にする問題です。

まずボールの位置、数字を受け取って指定した場所に移動させるロジックを書きます。自明なのは上から順に数字が[math]1, 2, 3, \dots[/math]と置く方法でとりあえず提出。

ここから最終的な配置を改善する方針を取りましたが良くなかったです。というのも

• 数字の大小関係を満たす初期配置が自明解以外に見つけられなかった
• 数字の大小関係を満たす配置が近傍に少なく改善解が見つけられなかった

という構図になってて鳴かず飛ばずでした。

終わった後にTwitterで知りましたが

数字の小さい順に親の位置の数字が大きければSwap

という貪欲法で全体として「上のボールの数字 [math] < [/math] 下のボールの数字」を保証でき、手数も抑えられる解法がありこれに気づく必要がありました。 実は途中で

• 小さい順に場所を決定
• 確定済みの数字の下の2マスが移動先の候補

としていたのですが

上の図のように全然ダメで捨てたのですが、実は勘違いで

• 未確定の場所のうち上の2マスの数字が置こうとしている数値より小さい場所

が移動先として正しかったです。これなら

という配置を得られて本番112位相当だったので惜しいといえば惜しいですが、気づけなかったのは実力なので仕方ないですね。

バチャを含め3回短期コンをやった感想は(自分の実力では)上位に行くには「運」も必要で長期コン^[3]寝不足になることはあっても時間が足りないということは少ないやアルゴ^[4]あと1問解けそうで間に合わなかった…はありますが、間に合ったとしてもパフォーマンスは1色分くらいしか違わないことが多いとは違う難しさ、適応能力がいるなーと感じました。

オンサイトのチャンスがある…といったお祭りならまた出たいと思いますが、基本は長期コンをメインにしようと思います。

終わった後は1か月ヒューリスティックメインにやったこともあって

「しばらくヒューリスティックはいいかなー」

という感じなって、この記事も8割近く書いたまま放置していたのですが8/11から長期コンがある、しかもオンサイト表彰もあり！ということで再びやる気が出てきました。

短期コンの借りは長期コンで返す！わけではないですが悔いが残らないようにAHC022に取り組もうと思います。

• 前回分: 「週記(23/05/28)：Sushi」
• 次月分: 「2023年7月: 典型90」