ACM-ICPC OB/OGの会主催の夏合宿に参加しました（初オンサイトイベント！！）。
Aobayama_dropout(kotatsugame, Yukly)として参加したので、チームでのコンテスト中の動きと個人的な感想を記します。
書くのすっかり忘れてたとか言えない
1日目
前日にこたつがめと新幹線で行くことを約束していたので、8時半に仙台駅に集まることに。
寝坊するなよと釘をさしていた自分が遅刻する失態をかました後、さっさと新幹線に乗る。
そういえば世間は3連休なのか、と約40連休中である自分たちが気づく。
11:30に到着。御茶ノ水でおいしい豚丼を食べた後、千葉からきたゆきのんと合流。オリンピックセンターに向かう。
軽い雨にあたりつつ会場につくと、TIkeさんとolpheさんが早速あいさつに来てくれた。作っておいた名刺を渡す。
自己紹介フェーズ。オンサイトイベントは初めてだったので、ここでTLのプロたちのIDと顔が一致する。名前を言うだけで笑いをとれるチームメイト
コンテスト。3時間なので気楽にスタート。
ぼくがテンプレートを写経している間にこたつがめとゆきのんの2人でAとBを考察してもらう。こたつがめがAをサクッと通し、ゆきのんがだるだる場合分けゲーをやっている間にCを考察。見た感じ、最大いくつの範囲が重なりますか、という感じの問題なので、いもす法をやる。範囲がバカでかいので座圧をやって、（こたつがめに見てもらいながら）AC。
こたつがDの考察を終えていたっぽいので、残りの問題の中で一番とっつきやすそうだったFを見る。与えられた関数 \(f(a, b, M) \mod 10^9+7\) の値を1万回くらい計算するやつ。ゆきのんが関数を見て組み合わせのアレっぽいことをつぶやく。とりあえず実験すれば良さそうなので、手計算の鬼になる。
M=2で計算したら虚無しか生まれなかったが、なんとなくフラクタルな図形が生まれそう。ゆきのんがM=5の計算をして、一定周期で組み合わせの値になることが判明。とりあえず逆元をこたつがめに実装させながら、もうちょっと多めに手計算して表をぐっと睨むと、どうやら周期Mで、第(i, j)周期では(組み合わせの値)*((i,j)における組み合わせの値) っぽくなることに気づく(冴えてた)。再帰的に計算させて一発AC。この時点で全体1位。喜びの舞を踊る。
今日のハイライトです pic.twitter.com/jdyS6nXtfB
— 碧黴(あおかび) (@AokabiC) September 15, 2018
Eをやる。円周上にある多角形の辺長が与えられるので、その面積を計算してください的な問題。問題概要を理解したころに、半径のにぶたんだろうという話が浮上。角度を足し合わせて2πになるまでやってみる。WA。残り15分ちょいで辺が円の片側に偏るコーナー(多角形が円の中心を内包しない場合)にゆきのんが気づいたものの、検証する方法が思いつかずそのまま終了。かなしいね
その後、おいしい食事をとったり風呂廃炉をしたりして、AGCに出る。Wifiの確保に成功したのが開始6秒前でアレだった。結果、配点から漂っていた嫌な予感は的中し1完。破滅。談話室から参加したのですが、始まった途端に静寂が訪れたり、終わった瞬間に考察の共有が始まるのはなかなか新鮮でした。
2日目
起床。朝ごはんに白米があることにパンを取ってから気づく。
初の5時間コンテスト。豪華なwriter陣の問題を解く。
昨日と同じムーブでテンプレを書いている間にAとBの考察をしてもらう。10分くらいで2問ともAC。Cは正N角形の頂点からいくつか選んで内角が等しい図形はいくつ作れますか、という問題。長方形以外は正多角形しかないやろ！ｗと約数の個数＋できる長方形の個数を出力すると圧倒的に足りない。ﾊｧ
いろいろ図を書きまくっていると、どうやら辺の長さが(a,a,a,…) か(a,b,a,b,…) の2パターンになりそうなことに気づく。そりゃそうだよなと思いつつ通す(タイプミスでWAを生やし、たぴゃ～)。
Eの概要をこたつがめから聞く。ある数列から、等差数列ないし2数とその和からなる部分数列を取り出すときの最大要素数を求める問題。2数とその和からなる部分数列が構成可能かの検証に\(O(N^2)\) から落ちなくて困惑。bit的な演算でどうにかならないかなあと考えていると、こたつがbitset高速化を提案。制約3000msだしどうにかなるんちゃう？と書いてもらう。通った。ヤバ。
当然これは嘘解法だったらしいのですが、オンサイトFAなのでまあ良しとしましょう(あとから聞いた話だと、bitsetを使っても通らなかったチームもあったらしい。運が良かった)。本来はFFTを使って頑張るらしいけど、知らなかったのでやっぱりダメ。
EよりもHが解かれているらしい。文字列Sと同じ長さで、Sのどの接頭辞もどの接尾辞とも一致しない文字列を数え上げる問題。条件を満たさない方を数え上げたほうがいいのでは、という話になりSuffixArrayやローリングハッシュを使ってどうにかやろうとしたけどわからず終了。椅子だけあたたまる。
解説を聞くと、KMP法、Z algorithmというものがあることを知る。KMP法は『文字列 S が与えられたときに、各 i について「文字列S[0,i-1]の接頭辞と接尾辞が最大何文字一致しているか」を記録した配列を O(|S|)で構築するアルゴリズム』で、Z algorithmは『文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列を O(|S|) で構築するアルゴリズム』ということらしい(文字列の頭良い感じの線形アルゴリズムたち より)。一応SAやロリハでゴリ押すこともできたらしいけど、こういうやつは幾何と同じで知らないとつらそうだなぁ。
夜はボドゲを見ながらKMP法とかの復習。初の5時間コンテストで疲れたり、ごちうさの3期が決まったりして感激した結果、9時にオフトンinして翌3時に起きる偉業を達成。
3日目
二度寝に成功したものの、さすがに人間なので9時間睡眠で起床。朝食は昨日の反省を踏まえ白米を食べる。荷物をまとめて会場へ。
コンテスト最終日。最初は同じムーブを取る。Cはナップサック問題をちょっと捻った感じ。dpの添字が大きくなるなあ、と思っていたらこたつがめが次元を落とすやつを教えてくれた。AC。
IとJが解かれまくっているらしい。Iを読んでいたらこたつがめが式変形を終えていた。はやい。Jは素数は奇数だねって感じで拡張dijkstraをやる話になる。
Fの実験をゆきのんが進めていて、xorが1になるよう取るといいっぽいことがわかる。じっくり実験をしてもらったおかげで初期状態でxorが0のコーナーにハマらなかった。素敵。
お昼を食べてからはGの考察を一生していました。ヤバ構文解析っぽそうな感じだったが、いろいろ試しても糸口はつかめず。dpが頭をよぎって結局わからなかったけど、想定解はdpらしい。ﾁｰﾝ。
終わってからは解説を聞いて解散。同じ階にいたへのkさんとの再会を誓い、会場をあとにする。その後は昔からFFだったぽうえっとくんとエンカをキメてラーメンを食べたりオタクショップはしごをしたりして帰った。
総評
文字列と幾何とかの知識が弱そうなことには国内予選のときから薄々感づいてはいたものの、それが露呈した。あと3ヶ月くらいでどうにかしよう。