【AHC参加記】AHC041、ルールベース初期解+山登りだけでもある程度戦える?
初めに
2025年1月19日(日)に開催されていた、短期プログラミングコンテストALGO ARTIS プログラミングコンテスト2025 冬(AtCoder Heuristic Contest 041)に参加しました。
今回は、「ルールベース初期解+山登り法」の方法で、過去最高順位の本番211位を取ることができました。
また延長戦にて、ルールベースをより正確にすることで延長戦94位に到達したため、それも合わせて記録に残してしていきたいと思います。
問題
頂点に点数の書かれた無向グラフが与えられるので、部分木に分割する。ただし、 出来るだけ根からの距離が遠い頂点に、高いスコアの頂点が来るようにしたい 。
... というような問題です。
本番
Sub 2 / DFS
まずは、高さ制限いっぱいまで深さ優先探索して木を作ることを考えます。DFSとBFSでは、より多くの頂点を葉の方に持っていけるDFSの方がスコアが高くなりそうです。
頂点数はN = 1000なので、頂点0 ... 頂点999を順番に選択し、その頂点を根とする木をDFSで作っていきます。すでに他の部分木に含まれている頂点は無視します。
例えば、H = 3の制約下で、以下のような無向グラフが与えられた場合を考えてみます。
DFSでの探索順は0 ⇒ 1 ⇒ 2 ⇒ 4 (H = 3に到達) ⇒ 6 (H = 3に到達) ⇒ 3 ⇒ 5 となり、以下のような部分木ができます。
これを提出した結果、67252287点になりました。まずはベースとして、そこそこ良い点数と言えそうです。
Sub 7 / 探索制限付きDFS
続いて、よりスコアを上げる方法を考えます。
今回の問題では、高い点数の頂点を、できるだけ葉の方に持っていく必要があります。
そこで、「浅い(根に近い)探索の時には、高い点数の頂点には入れないようにする」、「深い(葉に近い)探索の時には、低い点数の頂点に入れないようにする」ような 探索制限 をかけることで、スコアを伸ばせないかと考えました。
上記の例でこの考え方を適用すると、以下のような部分木ができます。点数の高い頂点が根に近くなりにくくなるため、スコアが向上しました。
これを提出したところ、本番環境でもスコアが改善しました。(69175495点)
Sub 11 / 探索制限付きDFS初期解+根の山登り ⇒ 本番211位
さらに、乱択を導入してみました。
Sub 7では根の探索順番を頂点の昇順にしていましたが、それをまず点数の小さい順にソートしました。さらに、その探索順番に確率で突然変異を加え、山登りを行いました。 (どちらかというと遺伝的アルゴリズムかも...?)
先ほどの例では、頂点5から探索を始めるような突然変異ができれば、一番高いスコアを得られます。
この考え方で再提出したところ、合計スコアは71543148点に向上しました。
本番結果
上記のSub 11が最終提出で、最終順位は211位/提出989人(登録1694人)でした。
ソースコードはこちら。
延長戦
当日夜に開催されていたAHCラジオを視聴できたので、せっかくなのでその内容を一つ実装してみました。
Sub 18 / 各頂点での探索順を最適化 ⇒ 延長戦94位
今回のルールベース初期解+山登りと相性が良さそうな改善方法として、「DFSの探索時に、点数が低い順に探索する」 という改善方法が挙げられていました。
そこで、その手法を実装して再提出してみたところ。。。
94位 (73471010点) ! スコアが大きく上がりました。
これは本番で気づきたかったですね。。。。。。。。
ソースコードはこちら。
最後に
今回、延長戦94位を出せたSub 18の解法は、(1) BFSではなくDFSを選択(Sub 2)、(2) 深さによる探索制限(Sub 7)、(3) 探索順の指定(Sub 18)、そして (4) 突然変異を入れて山登り(Sub 11)、の4つの工夫が組み合わさっています。
前回のAHC040 でも「ルールベース初期解+乱択山登り」は有効でしたが、一番初めのとっかかりとして汎用的なだけではなく、ルールベース初期解の精度を上げれば、100位相当までは十分に詰められることが分かりました。
焼きなまし法などのアルゴリズムもそろそろ学んでいきたいところですが、「ルールベース+山登りだけで本番100位を突破する」というのも、もう一つの目標にしてみても面白いかもしれないですね。
本記事は以上になります。ここまで読んでくださりありがとうございました。
Discussion