はじめに
こんにちは、KoiKoiです。Atcoderのアルゴとヒュの両方をやっていて、どちらも今回のコンテストの参加前は青色でした。
先月の2024-07-21に行われたALGO ARTIS プログラミングコンテスト2024 夏（AtCoder Heuristic Contest 035）に参加し、4位を取れた(とてもすごい)ので嬉しくなって参加記を書くことにしました。かなりダラダラ書いてあるのできをつけてください。
問題
AtCoder Inc.
問題概要
15個の評価項目を持った種が36個与えられるので、グリッドに植えて交配を繰り返して最強の種を作ろう！交配をするとそれぞれの評価項目を親からランダムに受け継いだ新しい種ができるよ！
↓交配の様子
コンテスト前
Shun_PIさんの短期AHCで勝つためのテクニックのスライドを読んで戦意を高めてました。
自分がahcに参加し始めたのが去年の2月ごろで、自分が参加した(ratedの)短期ahcでは1回もインタラクティブ問題が出なかったので、インタラクティブ問題が出たら大変だな〜(笑)と思ってました。
コンテスト序盤(15:00~17:00)
問題を読みます。インタラクティブ問題で軽く絶望します。まぁ多分モンテカルロ法が強いんだろうな〜と考えつつ、とりあえず価値(評価項目ベクトルの総和)が高い順に左上から植える貪欲を書いて提出します。(中央に植えた方が他の種と隣接する回数が増えるので本当は中央から植えた方が良いがどうせあとで変えるのでとりあえずこれで書きます。)
最初の提出(15:14):209385054点で本番774位相当(提出時8位)
https://atcoder.jp/contests/ahc035/submissions/55838626
注意:これらの提出の冒頭にコメントで方針を書いていますが、前のコードをコピペしたものが残っている岳だったりしてあまり当てになりません。(このせいでそこそこ苦しめられました。)
ここから迷走します。とりあえずランダムに植えて何回か交配をシミュレートして期待値(のようなもの)が最も高い植え方を採用するモンテカルロ法を試してみましたが、実行時間が3秒くらいかかった上にむしろ最初の貪欲よりスコアが悪化してしまいました。
ここで、そもそもどんな２つを隣り合わせるのが強いのかを考えます。当然評価項目の数値が大きいものを隣り合わせるのが強いですが、例えば(100,100,0,0)と(100,100,0,0)を隣合わせて前半の2つの100を確実に残すべきか、それとも(100,100,0,0)と(0,0,100,100)を隣合わせて,(0,0,0,0)ができてしまうかもしれないが(100,100,100,100)が運良く発生する上振れを狙うべきかで悩みました。(これは結構多くの参加者を悩ませたみたいです。)
ここで重要な気づきを得ます。それは、「端っこ以外に配置した種はどんな植え方をしても期待値2倍に新しい種に評価項目ベクトルの値が引き継がれる」 ということです。なので、(100,100,0,0)と(0,0,100,100)を隣合わせて(100,100,100,100)を狙いつつ、強いパラメータを増やしていくのが強いと考えました。
そこで次の関数を評価関数として、これを最大化するものを中央から順に貪欲に植えるコードを書いて提出しました。(実装上では最初全ての評価項目が100である最強の種が植えてあるとして順位に実際の種と置き換えていきました。)
(ちなみに植える順番は渦巻き型にしてる人が多かったですが、自分は左上から順番に植えていました。どっちが良いのかは良くわかりません。)
\[ \sum_{全ての隣接してる種のペア(i,j)}\sum_{k=0}^{M-1}max(x_{i,k},x_{j,k}) \]2つめの提出(16:06):236981110点で本番774位相当(提出時61位)
https://atcoder.jp/contests/ahc035/submissions/55838626
ここでまた悩みます。上の評価関数に基づいて山登りや焼きなましを書いてみましたが、山登りは全く遷移せず、焼きなましを行うとスコアが悪化すると散々な結果になりました。(順位表を見ると同じ東工大生が1,2ページにいてすご！！！と感じてました。)
先ほどの解法の欠点として、最初に植えるものは(最強の種のせいで)どんなものを植えても評価関数が一緒になってしまうので、適当なものが選ばれてしまうというのがありました。そこで、植える候補を「良い種」に絞ることで適当な種が植えられるのを防ごうと考えました。
先ほどの「上振れを狙う」という考えから、「良い種」を「種の各評価項目について、種の中で上位である評価項目を持っているか種」として、「良い種」から36~46個ほどを候補として先ほどの評価関数で貪欲に植えるという解法を提出します。
4つめの提出(16:58):259527552点で本番114位相当(提出時29位)(!?)
https://atcoder.jp/contests/ahc035/submissions/55844808
いきなりかなり良い点が取れてやった〜〜〜〜〜〜〜となってましたが、ahc典型として残り1時間で強強勢が一気に追い上げてくるというのがあるのでそこまで喜ぶべきではないと気を引き締めてました。(それでも嬉しい)
コンテスト中盤(17:00~18:00)
ここら辺で何をしたかあまり覚えてませんが、先ほどの「良い種」を「種の各評価項目について、種の中で上位である評価項目を持っているか種」としていたのを、「種の各評価項目について、種の中で上位である評価項目の個数が多い種」にして、植える候補は全ての種として評価関数を「先ほどの評価関数 + 植える種の良さ * hoge」にして色々試してみた結果、スコアを改善することができました。
7つめの提出(17:40):267744895点で本番28位相当(提出時7位)(!?!?!?!?!?)
https://atcoder.jp/contests/ahc035/submissions/55847668
この後「良い種」を上位k位までにするなど色々試しましたがあまり改善しませんでした...
コンテスト終盤(18:00~19:00)
残り1時間を切り、自分がまだ上位にいた事もあって新たな方針を思いつく&実装するが不可能だと考え細かい評価関数などをずっといじいじすることにしました。
短期ahcでは、コンテスト時間中に得た最高得点で最終順位が決定されることが多く、今回もそうだったのでとにかく提出しまくりました。
5分に1回しか提出できないのでスマホで5分おきにタイマーがなるようにセットして、5分間で「評価関数を少しいじったものを3つ作る→手元で試して一番良いものを提出」を繰り返して少しでもスコアを上げようとしました。
それで(直感と適当さに任せた)改善を繰り返した結果、最終的に次の評価関数に基づいて貪欲に植える解法が最も良いスコアを取れました。なんで良いのかはもうよく分かりません。
Sを種の個数2N(N-1)として、 \[ \sum_{全ての隣接してる種のペア(i,j)}\sum_{k=0}^{M-1}max(x_{i,k},x_{j,k}) + \sum_{0\leq i\leq S}15(10 - 既に操作を行った回数)\sum_{0 \leq j\leq M-1}f(i,j) \]\[ \text{ただし、}f(i,j) = \left\{ \begin{array}{ll} 1+2/(x_{k,j} = \underset{0 \leq l \leq S - 1}\max x_{l,j}なるkの個数) & (x_{i,j} = \underset{0 \leq l \leq S - 1}\max x_{l,j}の場合)\\ 0 & (otherwise) \end{array} \right. \]18個めの提出(18:50):272105002点で✨✨✨本番4位相当(提出時4位)✨✨✨
https://atcoder.jp/contests/ahc035/submissions/55852967
↓読みやすくしたもの↓
AtCoder Inc.この順位のままコンテストが終了し4位を取ることができました！！！！
感想
やったああああああああああああああああああああああああああああああああああ
今回もすごい難しくて面白い問題でした！
今回の自分の勝因は自分が苦手なビームサーチや焼きなましがあまり強くなく、運よく良い評価関数を見つけれたことと高速な貪欲解法で改善(悪あがき)を繰り返せたことだと思います。
ahc最高！ALGO ARTISさんAtcoderさんありがとう！！！
おまけ
このブログを書いてる時に気になって、種を植える順番を渦巻き型にしたら本番2位相当まで上がりました...
273070525点で本番2位相当
AtCoder Inc.