【AHC022】 AHC初参加記 〜入茶しました
みなさんこんにちは。LiKafです。
今回は、2023年8月11日から2023年8月20日まで行われた、RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022）に参加してみたので、参加記録と、（私なりの）簡単な解説を書こうと思います。
参加しようと思った理由
特に大きな理由はありません。
強いていうなら、リクルートさんがスポンサーであるというのと、夏休みで何か刺激が欲しかったからです。
そもそも、いままでAtCoderをやってきて、アルゴリズムの方はほぼ毎週出ていたのですが、AHCのことは正直一度もやってみようと思いませんでした。
一番大きな理由としては、ABCは『答えを出す』ということを目的にしてるが、AHCは『精度を競う』という、明確な違いがあると考えていたからです。
これまでABCで学んできたことが役に立たないのもあまり嬉しくはなかったし、ABCは好きだけど、その†違い†のせいでAHCが面白いかどうかわからないから、あえてそれに取り組まなくてもいいかなと思っていました。
参加記録
ダラダラ書いても仕方ないので、早速どのようにAHCに取り組んだのかを書いていきます。
（私の最終的な解法の解説はこの次の『簡単な解説』にあるので、解説だけ見たい人はスキップしてください）
結果的には、私の初参加のAHCであったAHC022は、
こんな感じでした。
実際の提出者は1000人ちょっとだったので、3382人中241位というわけではないのですが、まあ初めてにしては頑張った方だと思います。（そうだよね？そうだと信じてる）
8月11日（初日）
軽く問題文を読んでみました。
正直一回読むだけでは何もわからず、まぁまだ10日もあるからいいやと思って、とりあえずサンプルコードを提出するだけして、放置しました。
Web版ビジュアライザ・入力ジェネレータ？何これ。
8月12日 ~ 8月18日
みてもらうとわかると思うのですが、8/11から8/19日まで、何もしていませんでした。
何をしていたのでしょうか。本当に後悔しかありません。
問題文が予想以上に難解で、実家に帰っていたことも相まってYouTubeを見るだけの生活をしていました。マジで勿体無いです。大反省。
8月19日、20日（ラスト2日）
一緒にAHCをやろうと話していた研究室同期から催促の連絡が来て、流石にやるかと思って再開しました。
問題文を読み直して、意味不明すぎて絶望しました。
諦めずに何度か読み返したり、図に書いたりしてやっと理解できました。
問題としては、以下の感じです。（厳密にはコンテストページを確認してください。雰囲気だけです。）
我々の世界の他に、別の空間（Another Space）を発見した。
ここで、我々の世界（空間）をOur Spaceとする。
Our Spaceと、Another SpaceはN個のワームホールで繋がっている。
ただし、それぞれのワームホールについて、Our Space内にある入り口（1 ~ N）からAnother Space内にある出口セルは対応付けられていない。しかし、出口セルの座標は与えられる。
ここで、我々の目的は、どの入り口がどの出口セルに繋がっているかを解明することである。
ただし、その手法としては以下の3つのステップからなる。（計測と推測は同時に行える）
[配置]
Another Space（L✖️L）の任意のセルに、0度から1000度までの任意の温度を割り振る
すべての上下左右に隣り合うセルについて、指定した温度の差の2乗の和だけ、配置時コストがかかる。
[計測]
入り口からAnother Space内に入り（どの出口セルに出るかはわかっていない）、任意の座標移動し、そのセルで温度を測定する。
ただし、標準入力で与えられる標準偏差Sに応じた誤差が生じる。
合計10000回まで測定できる。
1回の計測によって 100∗(10+∣x∣+∣y∣)100∗(10+∣y∣+∣x∣)の計測コストがかかる。
[推測]
上記の計測を行いながら、入り口（1 ~ N）が、どの出口セルに対応しているかを推測する。
ただし、スコアとしては、正解率だけでなく、配置時と計測時にかかるコストの影響を受ける。
正確には、
⌈(10^14)*(0.8^W)/(配置時コスト+計測時コスト+10^5)⌉で与えられる。
Wは間違えた予測の数。
（より詳細には、他の参加者の最高スコアも影響する。）
さあ！問題文も理解し、僕の考えた最強のコード！を提出しました。
11,291。
サンプルスコアよりも300分の1になって大泣きしました。
ダメだ。次こそは。
WA。
もうどうしようもありません。
サンプルコードを忠実に再現し、微調整だけしてとりあえず出してみました。
3,476,702。
サンプル +9,079か、はぁ。むず。
サンプルコードが何をしたいかほとんど読んでなかったので、一度読み直すことにしました。
なるほど、
出口セルの座標の場所に、10, 20, 30, ….と温度を配置し、それ以外の場所を0度にする。
これにより、例として、
入り口2からAnother Spaceに侵入して、移動をせずにその出口セルで温度を測定した時に、51度なら、5番目の出口セルに対応していることがわかる。
これを全ての入り口に対して行うことで予測している。
のか。うん、もうそれでいいじゃん。
でも、スコアの出し方的に、測定コストは最小限で済んでるけど、配置コストがまずそう。
最大Nは100だから、温度としては1000度になる場所があって、その周りは0度になる可能性がある。
その周囲だけで、4*10^6のコストがかかってしまうということで、
今0度にしてる出口セル以外の場所を、出口セルの最高温度と最低温度の真ん中の値にすればいいと思いつきました。
そうすることで、最高温度が1000度の時でも、周りの温度は500度だから、その周囲だけで、10^6で済みます。（その分0度の時もコスト10^6かかるけど、それ加味してもコストが半分に抑えられる）
出してみよ
13,435,512❗️
スコアが4倍になった！！あ！！AHC楽しい！！！
セルを見分けるための温度差をサンプルのまま10度にしてたけど、これが最適かはわからないから、これを色々いじったり色々してみたりして、これまた楽しい！
配置コスト下げるのが正義だということで、温度差を少しでも下げる方法を考えました。
今は出口セルと、それ以外の場所の温度が急に変わってるけど、ここをもっと滑らかにすればよさそう。
やってみました
131,275,372❗️
ああああ！！！！桁が！増えた！！！AHC楽しい！！！
AHCをまともに始めてから4時間が経ちました。
もうこれ以上改善案が思い浮かばなくなったので、今まで放置してたWeb版ビジュアライザ・入力ジェネレータ・ローカルテスタを使ってみることにしました。
ローカルテスタはサンプルの100個をいちいち実行して比較していたらやってられれなかったので、まとめて実行して結果を出すシェルスクリプトを書いたりしました。
ビジュアライザは神です。
頭の中でしか考えていなかったものを、視覚的に考えれるのはとても重要でした。
提供されているツールは全部使ったほうがいいです。確実に。
ビジュアライザを見ると、（本来測定の様子を動画で見れます）
142度に設定しているところを642度と測ったりしていました。
標準偏差Sは実は0~900まで取りうるので、数度の差なんて一瞬で計測誤差として消え去り無意味な情報になります。そりゃうまくいかないわけです。
はてどうしたものか、
Sが大きくて、誤差がえぐいぐらい生じても、この温度ならこの座標だ！と明確にわかるような温度設定にしないといけません。
そこで、一点だけ1000度にして、そこを探すことで、その一点から出口の相対的な位置」を特定し、どの出口セルかを推測できる
と考えました。
具体的には以下の手順です。Sがある程度大きい時、
各出口セルと基準の一点（0, 0）の相対位置vi（iは1~N）を全て求めます。
基準の一点（0, 0）を1000度にし、他を0度にします。
ある入り口セルからAnotherSpaceに侵入し、そこから、可能性のある相対位置viだけ逆方向に移動し、そこで二回計測します。
その平均が最も高い i が答えと判断します。
viを消します。
これをすることで、多少大きな誤差があっても、設定した温度に差があるのと、二回計測できて均すことができ、正答率が高くなります。
ただしこれだと、O(N^2)回計測（＋移動つき）しているので、計測コストがかなり大きくなります。でも、スコアの計測方法として、0.8に対して、不正解の答えの数だけ累乗されるのは洒落にならないので、正確さを優先しました。
だしちゃお
237,214,343❗️
最高だあああ！！！！！！だのしいいい！！！
でもこの工夫をしても、Sが500を超えてくると誤差によってうまくいきませんでした。（スコアが1になってしまう）
必死で誤差が大きい時の方法を考えたのですが、思いつかなかったので、
スコアの計測方法
⌈(10^14)*(0.8^W)/(配置時コスト+計測時コスト+10^5)⌉
から考えて、配置コストと計測コストを0にしました。
そうすることで、W=75だとしても、50程度スコアを稼げます。
当然計測コストは0、つまり計測はしていないので、ランダムに予測します
追加でハイパラメータを変えたり微修正を繰り返して、
391,525,797❗️❗️❗️
ヨシ！AHC楽しい！！！！！！！
以上になります。
簡単な解説
最終的な提出コードは以下です。
思いつくままに書いたゴミカス適当コードなので、読まないでください😉
上にも書いたのですが、もっと端的にいうと、
標準偏差が小さい時（Sが3以下）
個人的AHC022解説（250位）
— LiKaf (@LiKaf_) August 20, 2023
[i]標準偏差Sが小さい時
1. 各出口セルに対して差2ぐらいずつ温度を変えて温度を設定する
2. 移動なしで数回計測して、その平均に対して/2で特定する https://t.co/u9gZ1fKlKP
誤差が少ないのでサンプルコードを参考にして、
各出口セルに対して温度を2度ずつ変える＋温度を均す
数回温度を測定し、それっぽい平均が出た時点で場所を特定する。
例：
…
平均結果が8度だったら、その場所は5番目の出口セルに対応
平均結果が12度だったら、その場所は7番目の出口セルに対応
…
と予測する。
標準偏差がある程度の時（Sが4以上700未満）
[ii] 分散中ぐらい
— LiKaf (@LiKaf_) August 20, 2023
[i]の方法だと配置コストの問題＋誤差でうまくいかなかったので
1. 一箇所(0, 0)だけ温度を1000にする
2. 各出口に対して、起点(0, 0)からの相対位置を求めてそれを答えにする。 全ての出口セルの相対位置分逆に移動して、そこで何回か測定して最も測定温度が高くなるところが答え pic.twitter.com/lfwu57jq6e
誤差が大きいことが予測されるので、一箇所だけ高温にして、その場所を探すように測定を行うことで、自分の場所を特定する。
例：
…
出口セルを3だと想定して、基準点に向かって逆方向に移動し、測定を行う。結果が32度だとする。
出口セルを12だと仮定して、基準点に向かって逆方向に移動し、測定を行う。結果が983度だとする。
….
この中で、結果が最も高くなったセルが正しい出口セルであると予測する。
この二つの測定に基づくと、この出口セルは3である可能性よりも、12である可能性の方が高い。
標準偏差が大きい時（Sが700以上）
[iii] 標準偏差が大きい時
— LiKaf (@LiKaf_) August 20, 2023
[ii]の方法だと、動画からもわかるけどO(N*N)だから、同じ場所を何度も計測して誤差を均すことが難しくなって、標準偏差400ぐらいから使い物にならなくなったので
1. 諦めて温度も全部一定、計測も0回、で予測もランダムにしてスコアを100ぐらいだけでも稼ぐようにした
もはや計測しても意味を持たないので、設置コストと計測コストを0にしてランダムに予測し、50程度のスコアをもぎ取る。
結果
やったあ！！入茶だ！楽しかった！
感想
えげつないほど楽しかったです。
最初の１週間何もしてなかったのが本当に悔やまれます。
あと、今回AHCに初めて出てみて一番強く思ったのは、冒頭に書いた
一番大きな理由としては、ABCは『答えを出す』ということを目的にしてるが、AHCは『精度を競う』という、明確な違いがあると考えていたからです。
これは、半分ほんとで半分嘘です。
問題を考えるという点で根本は一緒だし、温度を滑らかに配置する時にも私はBFSを使ったし、オーダーの考え方も使うし、解法によっては二分探索を使う人もいました。
他にもアルゴリズムや、アルゴリズム的な思考は沢山活かせると思います。
あと、コンテスト後に他の人の解説を見るのも楽しいです。
ABCと違って、本当に答えがないので、こういう考えでうまくいくんだと理解したり、面白い解法が転がってたりしてすごく良かったです。
次参加するときは、もっと統計の知識をフルで活用してやってみたいと思います。ハイパーパラメータとかも自動で調整できると思うので。
たった二日間でしたが、コンビニに行く時も何してる時もずっと頭の中がAnotherSpaceのことでいっぱいで困るレベルでハマりました。
ここまで熱中したのは久しぶりです。おかげでABCで大敗してしまいました。AHC許しません。
以上が私のAHC022の初参加記録です。
長々とありがとうございました！！
また来月なんか書くので読んでください！！