Shirotsume の日記

嘘Greedyを生やすな

ICPC 2023 Asia Yokohama Regional 参加記

早めに書かなかった結果、忘れた…

Shirotsume + MasKoaTS + fky = Uribo であったのが、MasKoaが体調不良により欠席することになったため Shirotsume + fky の 2 人チームでの参戦となった。

Day -1

Yokohama に向けて、特別な練習はほとんどしなかった。過去問セットもほとんど触れていない。Shirotsume が就活や学会発表準備など諸々で忙しかったということが主な理由。

一応 US 配列を触ったり仮想環境をいじってみる練習会は開催した。研究室のサーバーで好き勝手仮想マシンを立てられるので助かった。

Day 0 (11/24)

yukicoder の writer をやった

yukicoder.me

前日を狙うというよりかは空いているところに入れたら後で前日であることに気づいたという感じ。

懇親会などでも話のタネになってよかった

Day 1 (11/25)

朝は 7 時半くらいに起きて移動。割とぎりぎりの起床で終わったかと思った。朝 9:45 新大阪発の新幹線で移動。少し遅れていたが問題なし。

昼食は駅弁を買って車内で食べることに。私はひっぱりだこ飯を食べた。 fky は普通の幕の内みたいなやつを食べていた。

all.awajiya.co.jp

到着はほぼ時間通りで 12 時くらいに着。時間つぶそうかと思ったが、意外と新横浜から会場まで時間がかかる（40分くらい）ことに気づいたのでそのまま直行することに。

会場では俺たちは2人で出場するという旨を告げ入場。

リハーサル

とりあえず事前の取り決め通り最初はテンプレ（といっても bits や 575 など基本的なものだけ）を書いておく。

あとは適当に通す感じでやった。Bは fky 、それ以外は私が解いた。

A: はい

C: 頑張ってごちゃごちゃやれば通る。Pythonならオーバーフローをあまり気にしなくてよいので楽

D: 昔 ABC-Dでやられた記憶のある問題。最小を固定することでペアの全列挙が高速にできるやつ

あまり苦労せず完答できたので、残りの時間はWA,TLE,REなどのジャッジがどうなるか試したり、書いたプログラムを印刷してもらったりしていた。

B 問題についても時間があったので見ておいた。fkyは謎の方法で通していたが、1文字ずつ確定させるのが楽という話をし、実際にそれで通しておいた。

自己紹介

何も考えていないので適当にやった。MasKoaが休みなので2人だという話をした。自己紹介文もそうだけどまじめすぎたかもしれない（AAや作問を載せているチームを見ながら）

夜

夜はfky_と適当な中華屋に入ってチャーハンと小籠包を食べた。

ホテルはアパホテルだった。割高だったが、風呂がデカかったりファミマが中に2個あったりして面白かった。

この日はABCがあり、fky は出ないそうなので部屋の机を使って出た。青に落ちていたので戻したかったが、結果は-3だった（泣き）。ABC中に fky がデカい声で歌っていてカスがよ…って思った（言った）。

カウンター攻撃

Day 2 (11/25)

朝は普通に起きて準備をした。忘れたら死ぬ3点セット（ICPCシャツ、名札、学生証）を指差喚呼してから出発。

朝は fky_ とすき家で牛丼を食べた。朝定食も検討したが精をつけるという意味で牛丼にした。

時間通りに集合し、待機していた。

コンテスト本番

とりあえず序盤は fky に marunage ということで、A は見なかった。fky が A を通しているのを見つつ、Bを適当に読みながらわからんなぁと言っていた。

B は長さ C だけみればいいのでは？と言ってみるもののサンプル1で落ちていることに気づく。しばらく考えてみると累積和でえいえいやれば解けることに気づいたので書いた。通った。

B を通した後は、その時点でのAC数が多かった K を眺めていた。とりあえず 200 くらいの幅で当てていけば円内部を特定できるな～、そこからにぶたんすればいいな～など考えていたが確実に解ける感じではなかったのでかなりつらい気持ちになっていた。とりあえずコードを書いてみて出しても通らず、いったんほかの問題にすることに。

fky_に引き続きKを考えてもらいながらほかの問題に目を通す。Dがやるだけだったのでやる。とWAだった。aaaaaaaaaaが10(a)ではなく2(5(a)) だったので（このミス全人類やってない？）それを直してAC。

ほかの人は文字列アルゴリズムを組み合わせていそうだが、こちらは f(S) = （S を圧縮した結果の文字列）で再帰的に圧縮結果を求めることにした。無限ループを踏まないように気を付けて実装するとこちらの方が楽だと思う。

この辺時系列覚えていないが、Dを AC したあと fky_ が F の問題文を和訳してくれて、かなりフワフワした考察をして解くとサンプルがあったので投げると通った。

まだ K が通せていないが、自分の感覚的にこれが通せる未来が見えなかった（後から考えると、円の位置を特定する方法がわからなかったので結局通すのは無理だったと思う）ので、Kからは撤退することを提案。fky_ が引き続きやりたそうだったので、交代して問題を眺めることに。

可能性がありそうなのは E, G, H で、その中で一番可能っぽいのは G だった。指数関数的に個数が減っていくやつで状態数が抑えられる奴だろう、じゃあ再帰で高速にできるだろうと思って Python で提出するも、通らず。 fky に交代してC++へ写経をしてもらう。ここ自分でやろうか迷ったが、指も疲れていたのでまあ後退してよかったかな？

直したものを提出したもTLEだったが、最大ケースで 7秒くらいと、うまくやれば高速化できそうな気がしている。ここで、std::mapをstd::unordered_mapに変えると通った。

一通り unordered_map の講釈をしたのち、Kに戻る。しかし、手掛かりはつかめず5完で終了した。

残りの時間は E の O(N3 2N) を書いて落とされたり、K を考察しながらお弁当を食べたりしていた。

コンテスト終了後

解説などがあった。Hはまだ手が付きそうな感じで、こちらを見ておくべきだったかもしれない。

Yes/No は対象問題が1つしかなかったがYesされるのはうれしいのでよかった。

終了後の懇親会では、企業ブースを中心に回っていた。KLab の担当者さんになんでお一人なんですか？などのバッドコミュニケーションをしていた。

あとは目についたFFerに絡みに行っていた。本当すみません。鶏のトマト煮みたいなやつうますぎ

帰りの新幹線ではビールとつまみで盛り上がっていた。fky_ は寝ていた。

日付が変わる前に帰宅。いい時代になりました

Day3~

日常が始まる。いただいたメロンパンやミスドなどを食べつつ、大学のもろもろに向けた準備などをする。

感想

運営陣、スポンサーのみなさま、このような機会をいただけたのは本当にうれしいです。3人で出られればなおよかったのですが…

早生まれなので来年もこのメンバーのまま出られる予定です。ぜひ出たいですが、もしも野生のerが追加で生えてきたらコーチとして行くつもりです。出てこい！神戸er！