チーム
Speed Star (noimi, SSRS, ynymxiaolongbao)
どうしてこうなっているかというと、学内のAtCoder四~五段くらいの勢力(伝われ)が決まった3人組でICPCに出がちであるためです。
コンテスト前
コンテスト一週間くらい前に何か「自分が勉強しておくと良いものはあるか?」と聞いたらnoimiさんに「マトロイドとか?」と言われたので、マトロイドを勉強する。twitterで検索するとICPC作問陣にもいるYYさんやoptさんがマトロイドや劣モジュラ系を推していることが分かり、ますますやらないといけないなとなる。(実際にJ問題はYYさん原案のマトロイドだった。本番ではnoimiさんが「凸だから貪欲ができて」と言って解いていた。自分はマトロイドであることに気付いていなくて、解説を聞いて、その後の懇親会でYYさんに直接質問してやっとマトロイドであることを理解した。)
コンテスト結果
結果:全完(11完)4時間0分 ペナルティ無し
コンテスト中
・すべて時系列に書いていて、太字はその時刻にACした問題と実装者、問題概要です。
・すべてsegtree視点で書かれています。また、SSRS/noimiが何をやっていたかは微妙に違う可能性もあります。
初動
segtree: PCを触る(ログイン,エディタ立ち上げ,コンパイルコマンド設定など)
noimi: segtreeが準備してる間にA,Bを読んで解いておき、終わったら書き始める
SSRS: C以降のすべての問題を読む(←10分でできるらしい)
PCを触り終わって、すべての問題を眺める。
A(0:08) 実装noimi YOKOHAMAを作れ
すべての問題を読み終わったSSRSにどうするか聞くと、FとDが簡単で、「FをやるのでDを読んでください」「区間DP」と言われる
noimiがBの読解で詰まったので、SSRSがFを書き始める。
F(0:12) 実装SSRS グリッドで市松になるやつ
Dの問題を理解して、解けたので、疑似コードを書く。
noimiとSSRSが相談してBが解決した。実装はSSRSがやるらしい。
noimiがHを解いて、実装に移る前のSSRSに説明している。
B(0:25) 実装SSRS(?) 列を分割するやつ
Dを書き始める。10分くらいで書き終わって、サンプルを試すと、変な答えが出てきた(具体的には、正解が "3(ab)5(a)" の所で、"a"と出て来た)。こんなの直らない訳がないんですよね~(笑)と思っていたら、SSRSに「大丈夫!?!??」と聞かれたので、「大丈夫じゃないです」と言い、コードを印刷してPCを渡す。
多分このタイミングでSSRSがG、noimiがEを解いていた。
noimiがHの実装を始める。自分は印刷したコードを見て間違いを探す。Hの式とかを詰めるのにたまにPCが開くので、そこで直していく(直したら今度は答えがinfになってしまった。悲しい。)。そういうことを何回かやると、サンプルが合った(本質的なミスは、区間DPをrep(r,n)rep(l,r)にしていたこと)。申し訳ない。
D(0:53) 実装segtree 区間DP
進捗表(各問題の所感、解けたか、ACしたかなどを管理している表)を見ると、この時点で
・ACした:A B D F
・解けた:E G H
・解けてない:C I J K
になっていた。
分野としてCに998、IとKに幾何と書いてあって、それはnoimi/SSRS担当なので、Jを見ることにする。
Hの実装が終わったらしい。
H(0:57) 実装noimi 燃やす埋める
Jを考える。DP高速化とか貪欲(想定解のではなく、山登り的なもの)とかを考えていた。
E(1:10) 実装noimi O(2^n*m)
Kが初めて台湾のチームに解かれた。noimiに「Jは知識の可能性があるからK見てくんない?」と言われたので、Kに移る。
G(1:14) 実装SSRS カードの枚数が5/6倍になる998
ここで実装キューが空になった。7完していて、順位表を見ると2位は5完だった。
暫くの間、SSRSは多分C、noimiは多分Jを主に見ていた。
noimiに「Kはどう?」と聞かれ、そこから3人でKについて話す。
色々話しているうちに、SSRSが「1ずらすと算数でできる」と言って、それで解けた(線分が聞けることを使わず直線のみで解いた)。
SSRSがKの実装を始める。
noimi/segtreeでJを考える。暫くするとnoimiが解けて、解法を聞いた(HLDを使う貪欲の方)。合ってそう。
この時点で進捗は
・ACした:A B D E F G H
・解けた:J K
・解けてない:C I
になっていた。
CとIはどちらもこの時点ではどこにも解かれていなかった。いつもの"難問"しか残ってない状況になってしまった。
Cは998のn=3e6でFPS感があり、not for meなので、Iを見る。
K(1:47) 実装SSRS 円の場所と半径を当てる
Jを実装するにあたって、ei133333's libraryのHLDの変数の命名規則がnoimiと微妙に違って書きにくいらしく、SSRSが空でHLDを書き、noimiがその他を書くことになった。
Iを考える。noimiがベクトルで幾何的に考えていたので、自分は濃度の方針で考えることにした。二人が実装している間に解法が分かった。証明はしっかりはしていなくて、書き下せないが可能そうという感じだった。
J(2:13) 実装SSRS+noimi 木でコストが個数の二乗の最適化
二人にIの解法を説明する。SSRSはいつも通り「本当に!?」と言ってきて安心した。noimiが「実装そんなにかからなそうだしとりあえず書いてみよう」と言って、noimiが書き、残りの二人がそれを後ろから眺めて指摘を入れる体制になった。サンプルが合って、提出すると、通った。嬉しい。
I(2:34) 実装noimi 液体を混ぜるやつ
この時点で進捗は
・ACした:A B D E F G H I J K
・解けた:
・解けてない:C
になっていた。
Cは、ポリアの数え上げ定理で周期ごとにした後、周期2なら(縮約後)回文であることまで考察が進んでいた。すぐに、周期任意でも回文であることが示された。
その後は、カタラン数の母関数が~という話になってよく分からなくなったので、modintのライブラリを写経し、サンプルで遊んだりしていた。
二乗logが分かったらしく、noimiかSSRSが書き始める。それを眺める。サンプルが合った。
オーダーを落とすための議論が始まったので、眺める。
移項とか変数変換をすると畳み込みの形になってオーダーが落ちたらしい(?)
二乗logのコードをnoimiやSSRSが一箇所ずつ書き換え、その度にサンプルが合い続けているか確認する。オーダーが落ちている。
最後の確認になって、懐に温めていたn k=1 1を言うと落ちて、k=1の例外処理が追加された。
C(4:00) 実装noimi+SSRS 括弧列的なのの数え上げ
noimiが「凍結間に合わなかった~」と言っていた。
場所が出口近くだったので、弁当を食べるとトイレに来たチームに全完したとバレるかもと心配したりもしたが、お腹がすいていたので食べた。
全問題の復習と反省をした。
segtreeがDに時間がかかったので、代わりにnoimiがどれくらいで書けるのか試したりしていた。noimiがそれを提出しようとしたが、resubmissionで変なことになったら怖いということでやめた。
あとは順位表を見たりしていた。
振り返り
二人が爆速であるとはいえ、自分が一番早く考え始める問題というのは必ずあって、それが早く解けてれば結構タイムが縮まるし(失敗例 K、成功例 I など)より難しいセットなら完数にも寄与するはずなので、自分は変な高難度に特化しようとするより普通に実力を上げるのが良さそう。