ICPC模擬国内予選2021 参加記

昨年同様チームUHISHIRO(suta, kiyoshi0205, shiro53)で参加しました。

コンテスト前

日曜日なのでご飯どころがだいたい閉まっていて詰んだ。結局コンビニ飯に
icpcフォルダを開くのが去年のアジア大会ぶりなので、コードが残っていてエモくなる。最近過去のものを見てはエモくなってる気がするんだけど、もう老人ですか？

コンテスト

そんなことをしているとあっという間に14時になってコンテストが始まる。
いつも通りA : shiro, B : suta, C : kiyoshiで進めることにした。

Bを読む。問題文の本質が下数行だけで優しいな～という気持ちになる。解法もシグマの変数分離をすれば終わり。
もう国内Bはこんな難易度が続くのかな。某国内の「折り紙」みたいな†実装†がBに来るのもそれはそれで楽しい(?)んだけど。
最初の提出ということもあって過剰にビビりながら出す。AC(0:06:47)

Aで問題文の解釈が微妙な箇所があったらしいがサンプルと照らし合わせてなんとかなったらしく、そのままAも通る。(0:10:40)

Dを読むと文字列を半分で分けてよしなにDPをすれば通りそうな感じがしてくる。

ここらへんでCが通って(0:15:00)暫定5位くらいになっていた気がする。kiyoshiいつもCでハイパフォーマンス出してる気がしていてすごい。

Dは本当に愚直実装するとO(|S|^3)なので、少し考えることにする。二人がかりでやる問題でもないと判断し、二人にはEに行ってもらって一人で詰めることにした。
DP自体は二乗ででき、あとはreverseすることで文字列が一致するかの判定だけできればよいというところに行きついた。
これは全体reverse後の文字列との一致判定をロリハで行うことでO(1)にできるので二乗解が完成。
二乗になったら書くことを決めていたのでここで書き始める。少し添え字が煩雑だがそこまで大きな詰まりはなく書きあがった。

データセットを実行するとセグフォした。10000*10000のbool配列は手元ではきついらしい。仕方なく陽に構築することをやめてその場で判定してDP遷移を行うことにする。
セグフォが消えて1秒ほどで実行が終わった。これ二乗想定では？そのままAC。(0:41:13)

ここでEの概要となんとなくの(途中までの)解法を聞く。
まずLISをとるかどうかがそもそも怪しいという話だったが、とりあえずとってみて考えることに。
その間shiroが愚直を書いて解法の正当性を確かめるという流れになっていた。
LISをとったあとの操作は一意に定まりそうだが、実装が面倒そうだねという話になり、僕が実装することになる。
AOJ-ICPCのこの問題をなんとなく連想しながら書いていた。 細かいところで唸りながら書いていたら、kiyoshiが

「これ転倒数じゃない？」
「転倒数 + N - LISじゃない？」
「あ、これ下界でしかも必ず構成できることが示せました」

と次々に口走る。爆笑　天才問題やめてください
これは実装が無なのでそのままAC(1:12:45)

Fの概要を聞く。なんかよく分からないなあと思っていたが、kiyoshiからDP解法が伝えられる。
なんかあっていそうで、オーダーも五乗には収まっていそう。実装が大変なので少し考えてから全員で書こうということになる。
dp[文字列の長さ][1の個数] = pair(転倒数のmin, それを達成する辞書順最小の文字列)を組んでいたが、その中でdpの状態から文字列を復元したり、文字列を追加してからよしなに最適な移動をさせる実装が少し大変だった。

20分くらい(?)頑張ると書きあがった。しかしバグだらけで、修正にも20分くらいかかった。
やっとのことでサンプルが合ったので、投げる。WA　そんな......

しばらく考え込んでやっとおかしい箇所が見つかる。修正しようとしていると、kiyoshiが四乗解を書き終えたらしい。
実行結果を送ってもらい、自分のWA出力と照らし合わせる。IMPOSSIBLEの箇所は一致、そのほかが割と違うという感じだったので良さそうじゃない？という気持ちになる。

そのまま提出してもらうとAC。(2:25:12)俺実装担当やめてお茶くみ担当になります...

残り30分くらいでGを読むがヤバそうなケースが次々でてきて無理そうな雰囲気が漂う。
フローできない？というとkiyoshiが(負辺あり)最小費用流に帰着した。
フロー　負辺除去とかで検索するとbeetさんのライブラリを発見。実装するとサンプルが合って笑った。

がデータセットを実行しても全然終わらない。よく見ると負辺のコストの総和だけ計算量がかかるらしく、計算量大爆発。悲しい。
木という性質もクッキー2枚以下という条件も使っていないので通らないのは、そう...

無理じゃんとなりコンテストが終了。

結果

6完 全体19位

同学3チーム圏内の20位以内に入れたのでまずまず。MSBに負けたのは悔しい...
前回の模擬国内はボロボロだったので挽回ができてよかった。
チームとしてのパフォーマンスも悪くなかったと思う。しいて言えばFがもう少し早くACできるともっと良かったかな(誰のせいでしょうね？)。
give us、ほぼかっつ君一人で6完していて震撼

コンテスト後

UHISHIROメンバー、感想戦に大学に来たかっつ君、serpent君、たまかけ君とラーメンを食べに行った。[ここにラーメンの写真]
最近(他学年の)競プロerで集まって飯に行くことがなかったのでなんか新鮮だった。
(趣味が共通している)人と話すのはやっぱり楽しいね。オンサイト行きたすぎ

その後研究室に戻って研究div2に出た。コンテスト中の21時に強制退去を命じられてkiyoshiと近くの公園でコーディングしていた。結局F2とGは解けなかった。

感想

久しぶりのICPC国内形式で楽しかった。
最近ICPCの問題純粋に楽しい問題が増えていて、楽しい。(語彙力)
Eに天才を置くかわりに凸多角形柱工業都市とか置いてもいいんですよ！(小声)
国内予選で勝ちたい一心でAOJ-ICPCに励んでいたらいつのまにかAOJ-ICPC中毒者になってしまった。人はなぜ...
国内予選本番までにもう少し実装を早くできるようにしたい。残り1週間全力で練習していきます。

最後に、JAGの方々ありがとうございました。