AHC011 参加ログ

なんとなくブログを始めてみたいなと思っていたので、AHC011を機に試しに徒然なるまま参戦ログを書いてみる。完全に怪文書なので真剣な記事を読みたい人には非推奨です。。。
個人的なAHC011の感想は「スケジュールは重要。」です。

5/27以前

コンテストの日程がライブの遠征と丸被りしており悩んだが、なんとかなるかで参戦を決意。

5/28

コンテスト開始日、私は高松に降臨した。BiSHという推しのライブに参戦する予定があった為である。讃岐市野外音楽広場テアトロンとかいう辺境の地に行くバスが13時発だったので、それまでは普通に観光をした。

観光後うどんを食い、完全に香川県を漫喫している人になったところでライブ会場行のバスに乗り込み、AHC011の問題文に目を通す。

パズルをスライドさせて木構造にするという問題だった。さすがにバスの中ではコードは書けないのでひたすら脳内で考察した。ざっと次のような感じでまとまった。

[問題の特性]

  • 今回はAHC008ほど行動の制約に条件はないので、WAにならない解を構築することにはそんなに労力はかからない。
  • あるスライド操作方法の途中部分を雑に変えると後の行動に響いてしまうので、山登りとか焼きなましする時は、変化のさせ方は注意が必要。
  • パズルがT以内に完成する場合は評価式が変わるので、「完成する」という条件前後で根本的に問題が変わると考えてよさそうだが、そもそも完成させられる未来が見えないのでまずは完成に近づける方針で充分。

特に3つ目の部分から、そもそも完成図はどんな感じなんだという部分が気になり、暫定で次の方針で進めることに決定する。

  1. 完成図を先につくってしまう。(可能なら複数欲しい)
  2. 完成図に近づく操作方法を探索する。
  3. 2をある程度やったらスコアを最大化する方向で焼きなます。

あとは眠くなってしまったのでバスで入眠しライブ会場についた。

バッグが海で来た甲斐があったな～という感じ。(＊BiSHのライブは撮影可。)
この絶景を眺めながらライブが始まるまでは、忘れていた木構造周りのアルゴリズムをスマホでポチポチした。完全に変な人だったと思うが、外から見れば分からんのでよし。

さすがにライブ後はやる気出なかったので、ライブの余韻に浸りながらおいしいご飯を食べて終了。

 

5/29

この日は帰りながら完成図を構築する方法を模索した。

BFSで探索しつつ、木構造の管理はunion_findで実施した。

最初に配置するマスが1方向にしか伸びてない場合は、その方向側にばっかり伸びてしまって詰まるので

  • 最初は4方向か3方向のマスを使用し3方向の場合は中心部に向ける形で構築する
  • なるべく分岐できるマスは中心部に近い位置で優先的に使う。
  • 分岐先がふさがれている場合は他のブロックにする。

という感じにしたら大体 各テストケースで35万点くらいの図は作れるようになった。ただこのやり方だと最後に1方向のマス目が大量につながらずに残ってしまうのが難点だった。

関係ない話だが会社の福利厚生のパワーを使って空港のラウンジを初めて使ったのがあまりに快適で作業が捗った。次からAHCの際は空港に行った方がいいかもしれない。

5/30

この日は労働からの社の懇親会だったので進捗はゼロ。

5/31

各テストケースで35万点でも、順位表上の得点は17M程見込めるので一旦、5/29時点で構築した完成図を再現する部分を実装し始める。単純に完成図と現状の一致率を評価関数にして山登りしたが、これが思いのほか全然上手く動かない。。ここまで提出ゼロだったのに謎に焦り一旦雑に次のような形で実装して提出。

  1. 確率pで文字列をランダムに1文字伸ばす。確率1-pで文字列の末尾を1削る
  2. 1の文字列でスコアが伸びていれば採択する。スコアが伸びていなくても、epsiolon以下の確率で採用。(ただしepsiolonは現状の文字列の長さで可変にする。)

これで5.7M点。思ったよりスコアが出た。途中pythonのshallow copyとdeep copyで沼ってしまった。勉強が足りない。。

6/1

正の得点を得られてしまったせいで、完成図を構築してそれに寄せるのではなく、焼きなましで文字列構築する方に引っ張られてしまった。
昨日まで1文字ずつ加工していたが、1~2×Nまでのランダムな長さを加算する形に変更するだけで12Mを超えた。ただ今後の方針が途絶えた。

6/2

有給取ろうと思ってたが、なんかタスクが降ってきて急いだほうが良さそうだったのでやめた。(方針もなかったので。)

この日は仕事後はクライミングをしに行った。

只管クライミングしながらAHCを考察。恐らく自分の力量では完成図の構築は無理だと判断し、現状の焼きなましを改善して18M点くらいを目指すのが良いと思い、後述する3つをやってAHC011は終わりたいと思った。

18Mの根拠は、順位表を見たときに19M~25M帯にいる人が少なく見えたことに由来する。つまり恐らく18M以下に滞在している人と25M以上にいる人は根本的に進め方が違い、現状の自分の方針での得点の上界は18M程度であると推察した。というわけで3つほど今後の方針を立てた。

  • 現状ひたすら文字列を足すだけで、あとから文字列の中間部にテコ入れができていない。そこでAHC003と似た感じで中間部を改善しに行く。具体的にはある文字列のある区間 i~i+L (iは区間の開始位置、Lは区間の長さを示す)を「その区間での最初の空マスの位置と最後の空マスの位置を変えない」という制約条件を満たすように変化させる。
  • 評価関数が毎回文字列最初から最後まで使用して評価するため効率が悪かった。具体的には　ある文字列Tに文字列 t を追加して T'としたとき 従来はT'を1文字目から見ていた。その為、Tまでの操作の盤面を保持しておき、それに t 分の操作だけ追加で行う形に変更することで、評価関数の計算量をO(|T|)⇒O(|t|)にしたい。
  • 現状1つの解しか求めてないが、複数解求めて最良の解を選択する。

6/3

この日の夜は

高校の動機と飯⇒Wi－Fiとコンセントを確保してAHC⇒夜行バスに乗って大阪に出陣

の予定だったが「Wi-Fiとコンセントを確保してAHC」は丸の内界隈のお店が閉まるのが早すぎてできず、最後の「夜行バスに乗る」では並ぶ列を間違えてしまいバスに乗り損ねた。ここから全てが狂ってしまった。。泣く泣く家に帰る。しかも真の最寄りには終電の関係上辿り着けず、結構歩く羽目になった。。

6/4

本来この日は朝に大阪に着弾し、Liella!のライブが始まるまで6時間くらいAHCに使う想定だった。ところがどっこい、土曜の朝なのに夜行バスを逃したので自宅にいたのである。。(しかも寝坊した。)

大阪行きの新幹線を確保し、とりあえずAHCをやった。評価関数を改善して、関数単体ではいい感じに動いていたのに、焼きなましに入れた瞬間にバグだらけ。結局改善しきらず。。新幹線での進捗がゼロで「もうAHCは諦めた！！」となった。

高校同期と人生について話し、Liella!のライブに参戦し、オタクとたこ焼きをくって帰りの夜行バスに乗った。Liella!のライブのセトリ、天才だった。。。

6/5

早朝に東京へと舞い戻った。午後から友人とクライミング予定だったので、とりあえず1~2時間仮眠してAHCするかと思ってたが普通に寝坊した。
17時過ぎにクライミングを切り上げ、スタバを確保し、雑に6/2時点での1つ目の案だけ雑に実装。
30分死ぬほど集中してやって、12M⇒15Mと伸ばした。パラメーターチューニングは全て勘で設定してしまったので改善の余地があった気がする。
もう提出できないのでこれにてAHC011は終了。

今回のAHC011での学びは

  • 長期コンはスケジュールがかなり重要である。

皆さんは私のようにならないように注意してください。(友達にはそんな過密スケジュールでやるやつはいないと言われましたが。。。)