AHC016（HTTF2023予選）敗戦記 〜傷まみれの青春〜
はじめに
AHC016 （HACK TO THE FUTURE 2023予選）お疲れ様でした。AtCoderアルゴ茶永遠停滞 & ヒューリスティック緑の冴えない競プロer 藤川です。
本記事をご覧になられる方は大体コンテストに参加されていると思うので、問題の説明は省略しますが、今回も大変面白い問題でしたね。
お陰さまで10日間とても楽しく苦しめましたが、結果は342位（パフォ1458）とイマイチで非常に悔しいです。完全に"""負け"""だと思っています。
本記事はそんな敗北者による敗北の記録です。解法は非常に単純でわざわざ記事を書くほどのものではないのですが、誤った思考による敗北の一例としてご笑覧いただければ幸いです。
なお本記事は解説記事ではなく、あくまで参加記です。解法についての説明は最小限でほとんどただの日記であることを予めご理解ください。
さて本編に入る前に、まずは本記事のテーマソングである長渕剛「傷まみれの青春」を聴いて頂きます。
OK、聴き終わりましたでしょうか？現在の私の心境がなんとなくお分かり頂けたと思います。それでは本編に入っていきましょう。
初日 絶望
問題が難しすぎてひっくり返っていました。
大半のテストケースにおいて辺の有無が結構な確率で反転する上に、頂点の順番がシャッフルされちゃうだと！？しかもそんな状況でなるべく少ない頂点でグラフを表現しなきゃいけないだって！？オマケに相対評価方式だからε小さめで簡単なケースで多少稼いだところで無に帰しちゃうっぽい！？！？
こんなんどうやっても無理では？？？ふええ........
絶望感と高橋くんへの若干の怒りを抑えながら、とりあえずサンプルのPythonコードを私の愛用言語であるCrystalで書き直して正の得点を得てから寝ました。
2日目 まじ無理
まずはサンプルコードをちょっとだけいじって、0〜M - 1までのグラフ番号と同じ数の辺を1にしたグラフを作るだけの単純なコードを書きました。この時点での絶対スコアは約1.1億点。
その後はひたすら問題文と睨めっこしながらウンウン唸っていました。いやマジでムズすぎ。
3日目 くわがたかっこいー！！
虫オタク仲間の集まりがあったのでデカいクワガタをたくさん見れました。くわがたかっこいーーーー！！！！！！！！！！！ぼくタランドゥスオオツヤクワガタだいすき！！！！！！！！！！！！！！！！（AHC？何の成果も得られませんでした）
4日目 実験
考察以前にまずグラフを01文字列で表すことへの理解を深めようと思い、色々なグラフを01文字列化してみては各頂点ごとに分割したりシャッフルと01反転のシミュレーションをしたりしていました。
5日目 スタートライン
この日はド平日。いつものように山の中で泥にまみれながら超単純な肉体労働をこなしていました。
あまりにも単調な仕事なので脳内は暇で暇で仕方ありません。退屈しのぎに問題のことを考えていると、ようやく有望な策が浮かんできました。
「例えば辺の数が100でεが0.1のグラフのうち20本の辺が1で80本が0の場合、エラー発生後の1の数は20 × 0.9 + 80 × 0.1 = 26本前後になるよな！？んでこの推定値って多少のズレはあっても他のグラフとあんまり被らないよな！？使えるじゃん！！！！」
- まずは各εに対して十分な数の「1の塊」のサイズを決めます（とりあえず雑にε × 1000にしておく）。ここではカタマリと呼ぶことにします。
- グラフ番号 × カタマリの数だけ1、残りは0のグラフをM個用意します。
- 辺が反転された後の1の本数の期待値（って言葉選び間違ってないよね？）を求め、H（変化後のグラフ）の1の本数との差を見ます。差が最も小さいグラフが答えである可能性が高いです。
εもMも大きいケースではNを100にしても十分なサイズのカタマリを作れず前後4つくらいのグラフと期待値からの変異幅が被ったりしちゃいそうですが、とりえあずMが小さいケースならなんとかなりそうです。
ワクワクしながら帰宅してサクッと実装して提出してみたところ、さっきまで1.1億点程度だった絶対スコアが一気に3.5億点まで跳ね上がり、暫定380位から一気に194位まで上がりました！！！！うおおおおおお！！！！！！！！！！
手元で回した100ケースでは、Mが小さくεに対して十分なサイズのカタマリを作れたケースでは大体エラー数が1ケタまで落ちていました。やったね！！！！！！！！！
めちゃくちゃ喜んでしまいましたが、こんなごく単純なことに皆が気付かないワケがありません。これで私はようやくスタートラインに立てただけです。走り続けなければあっという間に全人類に抜かされるでしょう。走り続けなければ........。
6〜9日目 停滞
走り続けなければ...........。そう思いながらも、なかなか追加のアイデアが浮かんできません。見る度に落ちていく順位表、焦りが募っていきます。
今後の大まかな方針として2つの案があります。もちろんどちらも出来た方が強いですが、私の能力では残りの日数でできるのはどちらかのみだと思われるので、片方に集中するしかなさそうです。
- εが小さいケースでは少ない頂点数で十分に固有なグラフを作れるはずなので、事前に必勝パターンを用意しておきスコアを荒稼ぎする
- εが大きいケースでのエラー率を丁寧に下げていく
直接的にスコアに結びつきそうなのは1の案です。εが大きいケースでNを100近くにして現状の解法をベースに小細工して多少エラー率を下げたところでまあ焼け石に水でしょう。難易度的にも1の方が遥かに楽そうです。
しかしここで1つの不安が頭をよぎります。そう、相対評価システムです。みんなが高得点取れるケースでスコア稼いだところで1位の人にバシーーン！！と割られてしまいます。それならいっそのことイチかバチかεが大きいケースをゴニョゴニョと頑張ってみた方が希望があるのでは..........。難しそうだけどやってみるか........................。
そして私は愚かにも地獄の扉を開けてしまったのでした。
山中の肉体労働現場で昼休みにパソコンを開き、皆がお昼寝する中で一人HHKBを叩いても答えは出ず......。
海を眺めながらウンウン唸っても答えは出ず...........。
がむしゃらに走って汗を流しても答えは出ず.............。
完全に煮詰まってしまいましたね...。
6日目〜9日目の四日間、皆がどんどんスコアを上げていく中で私はひとり停滞、いや後退し続けていたのでした...........................。
10日目 狐の最後っ屁
一時は194位まで上がっていた順位もすっかり落ちてしまい、気付けば380位...。期待値作戦による順位爆上げ以前のところまで戻ってきてしまいました...。
少ない残り時間、浮かばない打開策。
追い詰められた私は終了2時間前になってようやく自分でもできそうな簡単な改善策を思いつきました。
理屈は非常にシンプルです。
- εに対して十分なカタマリを作れないケースの場合、カタマリのサイズを2倍にする
- 同じカタマリサイズのグラフを交互に作り、片方は先頭から1を詰め、片方は全体に1を分散させる
- 先頭から1を詰めたグラフ = より多くの辺を持つ頂点では、01反転 & 頂点シャッフル後も当然ながら1が連続しやすいことを利用する
- 事前にシャッフルと01反転のランダムシミュレーションを各グラフに対して同じ回数ぶん回し、各シミュレーション結果における1の最大連続数を配列に格納していく
- まずは1の数の期待値で2択に絞り、変化後のグラフにおける1の最大連続数が最も多く含まれる配列を有しているグラフの方を答えとする
- カタマリサイズが辺の数の半分を超えたら0と1の役割を逆転し、0を前から詰める（保有する辺が少ない後半の頂点に跨って1を配置してしまうことでシャッフルの影響を受けやすくしてしまうことを防ぐため）
実装してみたところ、それまでエラーが70〜90台程度あったεの大きいケースの大半で40以下まで落とすことができました。Mが小さければ20以下や1ケタにまで落ちるケースもありましたね。例えばcase76（M = 13, ε = 0.39）ではエラーを15まで落とせています。
ちゃんと効果はあったようですが、Nが大体100近くあるのでスコア的には焼け石に水です。ローカルテスト100ケースではそれまで8.1億点だったのが8.4億点になった程度...。劇的な改善にはならなさそうですが、もう時間も無いですし解法の改善はこれでおしまいにして、いったん提出してTLE等が起きないか確認してからパラメータ調整に入りましょう。
コンテスト終了50分前に提出してみたところ、案の定TLEが起きてしまいました。実行時間ベースではなく回数ベースでのシミュレーションだと調整が少々難しいですね。
もう時間が無いのでシミュレーション回数を無難な回数まで減らした上でお気持ちパラメータ調整を施し、終了10分前に最後の提出を済ませました。今度は全ケース無事ACですね。
この改善の結果、380位から342位まで上がりました。地味ですがやはり多少なりとも効果はあったようです。いや、地味ですが...。
こうして10日間におよんだ戦いは何とも地味な終わり方をしたのでした..........。
悲しみの感想戦
さてコンテストが終われば恒例のTwitter感想戦タイムです。
薄々勘付いてはいましたが、やはり皆さんεが小さいケースでは必勝グラフを用意していましたね。確かに相対評価時の減点幅がデカいとはいえ、そもそも楽なケースでNを減らして荒稼ぎするのは最低限必要なラインだったようです。私はスタートラインにすら立てていなかったのか........！！！！！！
その上で皆さんクリーク（なにそれ食べれゆの！？）と補グラフ（なにそれ食べれゆの！？）を活用してεやや大きめ〜大きめのグラフに対処していたようですね。もうね、比較になりませんよ、私のよゎよゎ解法。
AHC013や014では私と良い勝負をしていた方々が今回は私より圧倒的に上の順位にいて悲しみが深まります。うっうっうっ.........................。
システス
コンテスト終了後のシステスで興味深い現象が見られました。相対評価が反映される前に一時的に絶対スコアが表示されていたのですが、絶対スコアでソートしてみるとプレテストの相対評価順位との乖離がかなり大きかったんですよね。私は同順位帯の中では絶対スコアがやや低い方だったようです。εが大きなケースの対策にリソースを割いていたので当然といえば当然ですが、これ相対評価じゃなかったらヤバかったな...と肝を冷やしました。
コンテスト終了から二日経ち、システスにも相対評価が反映され順位が確定しました。プレテストと変わらず342位。うーーーーん、340位の賞金ニアミス！くやしい〜〜〜〜〜！！！！！
パフォーマンスは1458で一応水パフォ後半、レーティングは1046から1147に増えました。
水パフォといっても、参加登録だけしてサンプルすら提出していない事実上の不参加勢も含めての比率で算出されたパフォなので、1回以上提出している真の参加者内（1100人程度）でのパフォは実質茶パフォ後半程度と思われます。
これは完全に"""負け"""でしょう.....。負けた........。俺は...負けた................。
反省
さて今回の敗因をまとめると以下の通りです。
- εが小さいケースでN減らしを頑張ったところでどうせトップの提出で割られて無意味だと早々に決めつけてしまった
- エラー率を下げることに躍起になりすぎてNを下げることを軽視してしまった
- 相対評価システムを過度に警戒し、ε大きめケースの対処という自分の能力を超えた方針を無理に選んで時間を無駄にしてしまった
- ゆーてみんなε小さめケースのハックそんなに本気出さんやろwとナメてかかっていた
大体が誤解と思い込みによるものですね...。方針を固める前にまずは簡素な改善を複数パターン実験的に提出し相対評価の動きを見て判断すれば良かったものを......。
私の頭の中には今、「傷まみれの青春」が流れています。
泣けて泣けて泣けるんだよ どうしようもないから
誤解・偏見・独断の あんちきしょう 傷まみれの青春（コンテスト）
（長渕剛, 1996）
