はじめに
↑赤色が怖い/いよわ feat. v_flower
ICPC2023国内予選にRed Phobia(naniwazu, TKO, yuma220284)として参加しました。
コンテスト前
naniwazuさんがチーム登録周りのことを全てやって下さり、TKOさんがライブラリ作成と環境構築を全てやって下さった。どっちも出来ないので本当にありがたい。
戦略
A:TKOさん(環境構築をするため)
B:僕
C:naniwazuさん
を固定し、あとは解ける人から解くという感じでいくことに。
黄×3なので、全体25位かつ学内3位での通過を目標にペース配分をしていました。
コンテスト中
A
TKOさんが実装してくれているので、印刷されたB以降の問題が配布されるのを待ちながらラムネを食べていました。
B
実装やるだけなのでやる。サンプルが正しかったので提出したがWA。よく見たらサンプルの時点で間違えていました(最悪)
いつも通り添え字をバグらせていると思っていたら、配列の名前を間違えていた。引退を決意。
そんなことをしている間にCとDの考察がかなり進んでいました。ごめんなさい
40分1ペナで通る。
E
Bを解き終わったときにTKOさんとnaniwazuさんがCとDの考察をかなり進めてくれていたので僕がEを解くことに。まずDP[i][(Y,X)]=min{上からi番目まで見て、i番目を(Y,X)に編集した時の編集回数の最小値}を考えるが状態数と遷移が多すぎる。数分考えると、単調性があってDP[i][(Y,X)]の取りうる値は高々2Nなので主客転倒で良いと気付く。Dが解けたっぽいので紙で実装準備をすることにした。
D
Cよりも先に考察が終わったのでDを通すことに。TKOさんが一瞬で実装していた気がする。
60分くらいに通る。
E
実装をする。微妙にバグったので実装権を他の問題に譲ってプリントデバッグをすることにしました。
C
構築問題らしい?面倒な場合分けが生えているらしく大変そうでした。
Cの実装の途中にEのバグを発見したので1bitだけ修正させてもらいました。80分くらいにAC。
その後90分くらいにCも通った。この時点で5完5位とかだったので通過を確信。
F
幾何。TKOさんがすぐ必要十分条件を見つけて下さった。幾何はライブラリを持っているTKOさんに丸投げすることに(申し訳なさすぎる)
G
確率の問題。今年の確率論基礎の単位やばいな~とか考えていたらnaniwazuさんが爆速で式変形を完了させていた。それをみたらすぐにDPテーブルを思いついたので、それをnaniwazuさんに伝えたら一瞬でDP遷移がかかれた紙が返ってきた。チームプレー楽しい。
計算量が微妙に重そうなので僕がC++で書くことに。150分くらいに通る。
この時7位とかだったと思います。今まで競プロをやってきて一番嬉しかった瞬間。デカめの声を出していた気がする。
F
残りの時間は全員でFのデバッグをすることに。しかし、必要十分条件も正しく、ライブラリのコピペミスもなかったため、答えだけが間違っているという結論に至って終了。惜しくも通せず。
結果
最終的に6完で全体8位/学内1位という満足すぎる結果に。
10位以内に入れたことも、ギリギリで学内1位をとれていたこともめちゃくちゃ嬉しかったです。コンテスト後は打ち上げをしました。最高
感想
チーム戦楽しすぎるという気持ちに。問題配分が完全に噛み合っていて、全員が等しく強みを発揮できていたと思います。久々に競プロの楽しさを思い出せて最高でした。
あと横浜めちゃくちゃ楽しみです(いったことないので)
布教
聴いてくれると嬉しいです。