Give us sociability (Kattu, Hyado, hotman) で組んで、出場しました。
最終結果は9完11位でした。
コンテスト
いつもの割り振りで、僕がAからHyadoが後ろから、hotman先生が真ん中から、それぞれ読み始める。
例年の反省から、すぐにA問題の読解が出来なかったり、WAが出たりしても焦らない！というのを事前に意識していたのだが、今回は両方ともハマって出遅れてしまった。
Aが通ったのが開始20分後(+1ペナ)。種類数なのに、採取可能回数の最大値(複数回同じ作物を収穫することがある)を求めるとしてサンプルが合い、勘違いしていた。
Bが構文解析ぽいということで投げられる。問題文をちゃんと読んでいないが、サンプルと制約を見る限り、かなり適当にやっても大丈夫そうに見える。
出遅れた不安で本当に適当にやって良いのか不安になるが、ACチーム数を見て大丈夫そうと判断した。AC(0:28)
序盤の立ち回りとしては、Hyadoが問題読解&共有に回り、hotman先生がIのデバックで苦戦していた。B終わった後、Hを考えて欲しいと投げられた。見てみるとSCCして終わりのように感じたので書く。AC(0:37)
I問題のサンプルが合わずに、Hyadoが消火しに行ってた記憶がある。
この時点でJ問題が頑張れば解けはする枠、G解法分かってないけど解かれている枠、のようになっていたので次にGを考える。
hotman先生がI問題から離れ、Gを一緒に考えることに。
I問題の遷移の見落としを発見したようで、サンプルが合う。WA(0:50)
初期化周りで怪しい部分を修正して貰って、再び出すと通った。AC(0:56)
Gを一緒に考えていると、最近これTwitterで話題になってた奴だ！と言われるので、解法を説明して貰うが、結局よく分からなかった。
説明の正当性が理解出来なかったし、実装も中々終わらなかったので不安視していた。が、結局通ったので良かった。AC(1:08)
単純にG問題に関しては邪魔にしかなっていなかった。解説を見た。よくある比較関数の導出の話になっており、こう書くと流石に理解できる。
hotman先生がJ、僕がCを考え始める。
Cは最小費用流だね、という気持ちになる。終了後に教えて貰ったが、1種類ずつ前から決定していき、 回フローを流すのが1番楽そうだなと感じた。
解説でも触れられていたが、変更によるハミング距離に関するコストと、Aでの出現順が早い方から重み付けをするコストの2つを合わせて考えると、複数種類一気に決定することができる。
これを1回でやろうとしてしまい、多倍長整数が必要になってマジ？と言っていた。
以前僕が整備していた多倍長整数ライブラリ(少なくとも割り算はバグってる)があったので、不安になりながらも実装を開始する。些細な実装のミスが幾つもあったものの、サンプルが合う。提出すると通った。AC(1:53)
JでTLEが出ている。TLE(1:52), (1:59)
デバックをしている間、僕はJのテストケースのジェネレーターを書いておいた。
どうやらDFSで無限ループを埋め込んだようだった。
修正して貰うと通って一安心。
大分出遅れていて、開始から一度もMSB(同じ早稲田のライバルチーム)の順位を上回ることが無かったと記憶している。
Kの英語が読めなかったので、ゾンビランドチバの話？とだけ言ってHyadoに読んで貰う。幾何問題だったようで、そのままHyadoが担当する。
Dの問題概要を把握したので、discordで共有した。
Jが終わったhotman先生がKに合流する。この辺りの記憶が曖昧だが、いつ間にかHyadoはKを完全にhotman先生に任せており、Dの考察に合流していた。
Dは始め平方分割を軸に考えていたが、Hyadoがクイズで登場する得点の種類数は高々 種類なので、これを座圧して区間加算をする方針で考えていた。
結論を言うと、これが当たり方針だった。
クイズに正解した本人の順位変動は、BITなどで各点数の人数を管理しておけば、 で求めることができる。
次に考えないといけないのは、正解した本人以外の順位変動。
ある人がクイズに正解し、 ポイントから
ポイントに変化したとする。
一旦、 の場合を考える(逆の場合もほぼ同様)。
そうすると、この時点で ポイントの参加者の順位が、丁度1変化する。
その加算した結果の配列を便宜上 とでもおくと、最後に正解した時の配列の値
をメモしておくことで、次正解した時に、その間に起こった順位変動の総和を
で求めることができる。
これで全ての場合を網羅出来ている。実装上の工夫として、最後に人 がポイント
の問題を1問ずつ正解する、というクエリを予め加えておくと、答えに影響せず、場合分け無しで解くことができる。
hotman先生がKの実装を引き続き、僕とHyadoの2並列でDを実装していた。
先に僕のDが書き終わり、無事通る。AC(3:43)
一分遅れでKも通る。AC(3:44)
凍結直前の開始4時間のタイミングで、ようやくトップ10に入ることが出来た。
4 時間時点（凍結済み） pic.twitter.com/mdahleBwbL
— りあん (@rian_tkb) 2022年3月6日
残り1時間は僕とHyadoでE2並列、hotman先生がFの実装をしていたのだが、途中でFを放棄したいと言って最終的にはE3並列になった。
しかし、まともな実装までは漕ぎ着けず、終了。
凍結解除で予想通り(？) Antitled に抜かれていて、最終順位11位。
10完以上しているの、納得の強い人達だなぁと感じつつ、よく見かけるチームも大体9完で、もっと早解きが必要だなぁと感じた。
反省会
弊チームは先行逃げ切りでしか勝てないと自負しているので、その初動が遅れたのが良くなった。
具体的には僕のAがいきなり遅かったんだけど、その僕が序盤3問書いているので、そこら辺の立ち回りは改善の余地があると感じる。
それ以外の改善点を挙げてもキリは無いが、各問題を1秒でも早く通す、という意気込みが当たり前ではあるんだけど、大事だなとは改めて。
焦らないのは大事なんだけど、それを免罪符にしてはいけないという、自戒。
後半の立ち回りは2人以上で協力して解く問題というのが多くあり、良かったと思う。
初動失敗した割には結果は悪く無いように感じている。後はチームで解ける難易度の最大値を上げていくことが課題かな。
これは崖の一個先のupsolveをサボらない、ということを続けていくしかないね。
感謝
JAGの皆様コンテスト開催ありがとうございました。
忙しいであろう社会人の方々によって、暇な大学生(←暇なのはお前だけだろ)向けのコンテストを開催準備してくださり、本当に頭が上がらないです。
(暇なので、参加記は幾らでも書けます！←意気込み満点)
おまけ
生活習慣が崩壊しまくってて、徹夜で模擬地区→CFの強行スケジュールを決行したら、流石に途中で力尽きてレート-100をやらかした。
もう、徹夜は、こりごりだ〜〜〜(完)
