Heuristic黄色になれたので今までのAHCを全て振り返ってみる
先日行われたHACK TO THE FUTURE 2024 (AtCoder Heuristic Contest 027)でHeristicレーティング黄色になりました！
…
Algo入青から2年半ぶりに新しい色に到達できたのでうれしいです。
ヒュの色変記事ってあんまり見たことないので書いてみようかなと思ったんですが、何書けばいいのかわからなかったので、今までのAHCを自分なりに振り返ってみようかなと思います。記憶とツイートが頼りなので嘘を書いてたらすみません。
注意！
以下、AHC過去問のネタバレが大量に含まれます
Introduction to Heuristics Contest - AtCoder Contest Scheduling
CodinGame SPRING CHALLENGE 2020に参加してみたら思いのほか楽しくて、アルゴ以外のジャンルにも挑戦してみようかなーというタイミングで開催されたような気がします。そもそも自分はヒューリスティック系の知識を一切持っていない状態だったので、解説記事を参考にスコア計算とビームサーチを実装してその日は満足したようです。
その後も、焼きなまし法の練習とかで何度か解き直しています。
解説PDFが非常に有用なので、AHCに興味を持った人にぜひ勧めたいです。
AHC001 - AtCoder Ad
順位:354 パフォーマンス:1391 レート:0→391
記念すべき第一回AHC。興味はあったものの、Algo入青直前でそちらの精進にかまけていたので途中までほとんど手つかずでした。
最終日の前日のABCで無事Algo青色になれたのでそこから1日だけ参加。
当然ほとんど知識がない状態だったので、少しずつ箱を大きくしたり動かしたりするだけの貪欲を書きました。
TERRYさんのビジュアライザ動画が本当に衝撃的で、今振り返ると自分のAHCの原体験はこれだった気がする。
AHC本当にお疲れ様でした。49,577,244,111点で暫定14位。
— TERRY (@terry_u16) 2021年3月14日
(1)ランダムな長方形を拡大・縮小・平行移動させる焼きなまし
(2)2つの隣り合う長方形をランダムに選んで破壊し、境界を嘘黄金分割探索で探しながら最大長方形問題を解く焼きなまし
を用意して、(1)→(2)→(1)の順で流しました。 #AHC001 pic.twitter.com/GIQsNxmiuR
AHC002 - Walking on Tiles
順位:491 パフォーマンス:1169 レート:391→662
第二回AHCは短期コンテスト。当時は19時-23時開催だったんですね、今とずいぶん違うね。
行き詰ったら途中からやり直すみたいなDFSを書いて、マップの半分程度しか埋められなくて途方に暮れていました。なんなら去年もう一度解いてみた時にも大した改善ができず……。（その時はビームサーチを試してたはず）
この時ちゃんと復習をして、経路を部分的に破壊して再構築する手法を勉強していたのが、AHC027の勝因だったと思います。
自分の師匠であるthunderさんがAHC027の2日前に解説記事を書いているので（エスパーか？？？）、興味のある方は是非この記事で勉強してみてください。
AHC典型解法シリーズ第2弾「焼きなまし法」 #AtCoder - Qiita
AHC003 - Shortest Path Queries
順位:817 パフォーマンス:658 レート:662→711
AHC初のインタラクティブ問題。
最近ようやく多腕バンディット問題という概念を勉強しましたが、当時は当然そういった体系的な知識があるわけもなく。
通った道の重みを適当に更新しながらダイクストラ法してた気がします。
yosssさんの解法スライドが非常に本格的。そろそろきちんと復習しなくちゃ……。
AHC004 - Alien's Genome Assembly
順位:- パフォーマンス:- レート:-
不参加でした。
AHC004からAHC010まではほとんどが短期コンでしたね。この時期から1年ほどは入籍や結婚式の準備で土日が潰れていることが多く、短期コンテストに参加し辛かったです。
AHC005 - Patrolling
順位:139 パフォーマンス:1703 レート:711→1039
シンプルで結構好きな問題。
ググって出てきた記事を読みながら2-OPTを実装しました。初めてちゃんと山を登った問題かも。
上位陣は使う頂点も焼いていて、「この人達なんでも焼くな……」と軽く引いたのを覚えています。実際にはもっととんでもない問題も平然と焼かれる魔境ですが。
とはいえ、問題設定はシンプルで初心者にもとっつきやすいので練習にオススメ。
HACK TO THE FUTURE 2022 予選 - Project Leader
順位:348 パフォーマンス:1277 レート:1039→1114
AHCではないですが、レート変動があったので記載。AHCの名を冠さないRatedのHeuristicコンテストはこれ含め今まで3つしか開催されてないんですね。
各社員の能力を推定したうえで適切に計画を組まなきゃいけないので、けっこう解きごたえがありそうな問題。自分は当時どちらもできておらず、なんならこの記事を書くまで問題の存在を忘れてました……。
AHC006 - Food Delivery
順位:- パフォーマンス:- レート:-
当日は不参加で、後日ちょっと解いてたかも。
TERRYさんの解説を読んで、強い貪欲を考える大事さを学びました。
Algoでは”全ての基本は全探索”ですが、同じくらいHeuristicでは"全ての基本は（嘘）貪欲"であることを意識したいです。
そのうち丁寧に解きなおしたい。
AHC007 - Online MST
順位:- パフォーマンス:- レート:-
不参加で、まだ解いてないです。
AHC008 - Territory
順位:- パフォーマンス:- レート:-
唯一NoSub撤退したコンテストです。とても苦い思い出。
やりたいこと自体はいくつもあったものの、複数キャラクター操作をどうやって管理すればいいのか全くわからず逃亡。
CodinGameでもそうなんですが、マルチエージェントの問題が露骨に苦手っぽい。
iwashiさんの解説記事がすごくよかったので、いつかリベンジしたい。
AHC009 - Robust Memory of Commuting Routes
順位:- パフォーマンス:- レート:-
当日は不参加で、1ヵ月後くらいに解いてみました。
とはいえ、上位陣のビジュアライザは見ていたのであくまで練習という感じ。
ビジュアライザが見ていてかなり楽しい問題。
AHC010 - Loop Lines
順位:194 パフォーマンス:1571 レート:1114→1229
結婚式の翌日でしたが、妻はTOEICに、自分はAHCに参加。ストイックすぎる。
めちゃくちゃ難しかった……今出てもやっぱり解けない気がする。
設定がまあまあ特殊。まずまともなサイズのループを作るのが難しくて、validな状態のまま次の状態を探すのも難しい。しかも2つ必要。
上位解法があまりに天才的でひっくり返ってしまった。重大すぎるネタバレなのでここには書きません、まだ解いていない方はぜひ一度自力で挑戦したうえでひっくり返ってみてください。
AHC011 - Sliding Tree Puzzle
順位:115 パフォーマンス:1871 レート:1229→1392
AHC初のパズル問題？ジャンル分けとして正しいのかは知りません。
最終的には100位を割ってしまったものの、初めて"戦えた”という実感を持てたのがこのコンテストでした。初日に徹夜した結果、朝方に木を完成させることができてめちゃくちゃ舞い上がっていたのを覚えています。この辺から長期コンへの取り組み方が沼ってきました。
maspyさんが異常なほど強かったのが印象的です。
AHC012 - AtCoder 10th Anniversary
順位:223 パフォーマンス:1550 レート:1392→1441
相変わらず短期コンは苦手気味です。
自分は直線の角度にも自由度を持たせちゃったのですが、水平・垂直方向の直線のみで構成すれば高速に計算できるというのはたしかにといった感じでした。
意図的に制約を設けることで探索空間を限定して高速化するのは典型テクとして忘れないようにしたいです。
ビジュアライザでえげつない形状のケーキがたくさん流れてきてかなり楽しかった。
AHC013 - Server Room
順位:225 パフォーマンス:1540 レート:1477
かなり迷走した回。
よい状態というものをあまり考えられないまま、とりあえずビームサーチをしていました。この頃はまだ焼きなましの近傍を考えるのが下手くそで、愚直な近傍でスコアが滑らかにならない問題はとりあえずビーム撃ってお茶を濁しがちでした。
AHC014 - RectJoin
順位:254 パフォーマンス:1438 レート:1477→1498
AHC013と同じく、かなり迷走しながらとりあえずビームを打っていました。
今振り返ると当時の自分はAHCへの取り組み方を間違えていて、"その問題が持つ固有の性質を考えずに、とりあえず典型的なヒューリスティック手法を適用して解決しようとしている"といった状態でした。反省。
問題自体はかなり面白いです。seed=0もオシャレ。
AHC015 - Halloween Candy
順位:470 パフォーマンス:1104 レート:1498→1501
実際にありそうなゲームが題材で面白かったですね。
18年連れ添った愛犬の葬式と被っていたので、1時間半だけ参加しました。
時間作ってちゃんと詰めてみたい問題のひとつ。ゲーム木探索のいい練習になりそう。
AHC016 - Graphorean
順位:69 パフォーマンス:2148 レート:1501→1651
問題設定が良すぎる。なんだグラフだけ送れるタイムマシンって。
AHCはストーリーがついていることが多いですが、ダントツで好きなのがこれです。実際の問題ともすごく嚙み合っていて、どうにかグラフを復元しようと四苦八苦する一週間でした。気分は高橋くん。
実際、この問題が一番好きだと言っている人は多い印象です。
開始直後に瞬間風速1位を取ったり初の2桁順位＆黄パフォで当時は大満足でしたが、小さいケースが弱かったりシステスで20位以上順位を落としたりと、今振り返ると詰めの甘さがあります。
AHC017 - Road Repair
順位:267 パフォーマンス:1550 レート:1651→1665
仲の良い競プロerとスキー旅行に行っていたため、後半のみ参加。
問題の性質を完全に間違ってとらえており、市中のあちこちで細切れに工事する激ヤバ計画を策定するハメに。
よさそうな方針が浮かばないときには、一度数十分とかかけてじっくり愚直に焼きなましてみて、良いスコアの解が持つ性質を掴むべきだという教訓を得ました。
AHC018 - Excavation
順位:73 パフォーマンス:2165 レート:1665→1772
コスト不明なグリッド上で最小全域木を求める問題。AHC003を彷彿とさせますね。
実際、ちゃんと推定できている人が勝てていた印象。ここらへんから、インタラクティブ問題で数学的裏付けのない適当な推定じゃ勝てないんだなというのを悟り始めた気がする。
2度目の黄色パフォ獲得で、レーティング黄色を意識し始めたのもこの頃です。
AHC019 - Silhouette Block Puzzle Creation
順位:136 パフォーマンス:1787 レート:1772→1798
問題文を読んだ瞬間にゲェ！と声が出たのを覚えています。見た瞬間に実装から逃げたくなる複雑さだなと。
血反吐を吐きながらよくわからない貪欲を書いた気がします。あんまり覚えていないです。
この問題でも上位陣が焼いているのを見て、焼きなましからは逃げられないんだなと覚悟を決めました。
このclar好き
他のブロックに引っかかって外せないなど物理的に不可能な配置であっても、正の体積の共通部分を持っていなければ有効な解であるとみなされます。子どもたちは超能力でブロックをワープさせることによりそのような配置を作ることが出来ます。
AHC020 - Broadcasting
順位:177 パフォーマンス:1787 レート:1798→1819
使う放送局を焼きなましして最小全域木作ってみたいなことをしようとしていたはず。
シンプルに実装がおせぇ！バグらせすぎ！
比較的シンプルな問題設定なだけに、自分のやりたかったことをやりきれなかったという不完全燃焼感に襲われるので、負けた短期コンはつらい。
もっとサクサク焼けるようになりたい。練習あるのみですね。
AHC021 - Pyramid Sorting
順位:543 パフォーマンス:1255 レート:1819→1819
完全にトラウマです。
短期コンに苦手意識はあれど、オンサイト全然狙えると思っていたのに大爆死しました。
何より最悪なのは、コンテスト後のTLで”天才貪欲”と呼ばれていた解法を開始30分くらいで書いていたにも関わらず、バグらせていたためにスコアが伸びず、よく検証しないままその方針を棄却していたこと。
2週間くらいは自己嫌悪に陥っていました。うう。
AHC022 - Exploring Another Space
順位:49 パフォーマンス:2281 レート:1819→1915
事前に構築した情報から推定を行うという部分からAHC016 - Graphoreanとなんとなく通ずるところがある問題。
このコンテストの前半は徳島旅行と被っていたためほとんどコードは書けなかったのですが、頭の中で標準分布の性質をどうやって使えばいいのかじっくり考えられたのがきちんと実装のときに活きたなと思います。
探索と活用だけではなく構築とのトレードオフを考えなくてはいけないのも難しかったです。ノイズに応じて離散的な点をいくつか配置する解法自体は悪くなかったものの、探索結果を用いて情報を更新していく処理が雑で、あと一歩詰め切れなかった。
上位入賞ということで、RECRUITさんのオフィスで行われる懇親会に参加しました。
初のオンサイトイベントで、Twtterで話したことあるAHCerとたくさん交流できてとても楽しかったです。トヨタコンオンサイトに行けなかった雪辱を果たしました。
AHC023 - Crops on Grid
順位:174 パフォーマンス:1738 レート:1915→1923
ほぼ土日のみの参加。
問題設定は長期コンテストにしては比較的シンプルでしたが、けっこう上位陣との差がはっきりつけられてしまった。
通路決め打ち＆貪欲で達成できる上界が低そうというのは見えていたのに、別の解法を考え直すことができなかったのは反省点。順位表情報はもっと活用しなければいけないですね。
AHC024 - Topological Map
順位:355 パフォーマンス:1283 レート:1923→1924
完全にバグにハマってしまい、初めてまともに動いたのが終了1時間前でした。局所探索の近傍を考えるところまで行けなかったので論外。
短期コンテストではバグらせにくさという軸にもっと重みを置くべき。
ただ、自分では思いつかなかった近傍や、連結判定の簡素化など、コンテスト後のTLから吸収できる知識が豊富でした。延長戦もけっこう盛り上がっていた印象。
いずれはIntoroduction To HeuristicやAHC005で基本的な焼きなまし法を練習した後のチャレンジ問題みたいな位置づけになるのかなと勝手に思ってます。
AHC025 - Balancing by Balance
順位:85 パフォーマンス:2087 レート:1924→1963
ハチャメチャにシンプルな設定なのに操作の自由度がとても高くて、どれだけ小さな改善を積み上げられたかがそのまま結果に反映される問題だったのかなあと思います。とはいえ、実際に重さを推定できている方もいたのはかなりビックリしました。
マージソートを自分で丁寧に実装するよい練習になりました。既に比較したことのある集合同士の大小関係情報の推定・伝播は詰め切れない部分もあり、要復習。
AHC026 - Stack of Boxes
順位:180 パフォーマンス:1750 レート:1963→1969
トヨタ関係のコンテストはなんかこういう問題多いですね、荷物積載計画みたいな部分に課題感があるとかなんでしょうか（適当）
シンプルな貪欲を書いたところまではよかったのですが、そこから特殊なケースを改善する方向に行ってしまったのが完全に失敗。最後まで貪欲した結果をスコアとするビームサーチに書き換えて全体的なスコアを向上させるべきでした。
一方で、一列ソート方針は全く思いついていなかった。思いつかんくないか？？？
AHC027 - Recurring Cleaning Route
順位:25 パフォーマンス:2450 レート:1969→2069
初の橙パフォで入黄！
でも、解法としてはあまり特殊なことはしなかったです。基本アイデアは部分破壊再構築と部分反転だけ。
初期解がスコアが悪化せず長さが短くなるように手を入れたり、スコア計算が少しでも軽くなるように計算順序を工夫したり、ひたすらパラメータ調整を繰り返したりと、0.5~1%の改善をひたすら積み上げました。
そういう意味では、TLで異常高速化回だと揶揄されていたのもあながち間違いではないなあと感じます。
まとめ
AHC大好き！これからも参加します！
