すみませんかなり雑に書いています。

noshi さんと Hemimor さんと 3 人で tonosama として出ました。国内予選の参加記はこちらから。

day1

家を出てから会場まで 1 時間弱で着くため 12 時に家を出れば受付開始時刻に着くから早く起きる必要はないが、明日のために 8 時くらいに起きてご飯を食べてから家を出る。

会場が混むんじゃないかと思って駅集合にした。

リハーサルやチーム紹介が終わった後は同じく東工大の AMATSUKAZE と合流して 6 人で横浜中華街へ。人混みやばかったので、少しハズレの道にある空いてそうな店探して入った。7 時くらいに解散して家帰って ABC に出る。 Div1 もあったが出ずにダラダラして 1時前に寝る

day2

6 時起床。駅に 8 時半集合にしていたが、30 分以上前についてしまった。

コンテストスタート

コンテストのことあんまり覚えていないので適当書いてるかもしれません。
時間とか書いてないので、時間とかはこの順位表見て確認してください。

A He,B no
起動を自分がする

CLion が起動できない。
焦りでダブルクリックが全然できなかった。
モタモタしてる間に A がとけたという報告を受けたのでテンプレートもあんまりかかずに渡す。

後ろから見る。
K は幾何と判断して飛ばす。
J を見る。木の最適化おもしろそーとか思っていると A が通る。
noshi さんから C の概要を聞いた後 C もおもしろそうですねぇとか言って考えて、Hemimor さんに EF 辺読んでくださいと言う。
C を考えている間に B のAC が出る。

その後 Hemimor さんが EF どっちも簡単という話を聞く。
F は確かに簡単だった。E は bitDP で解けそうみたいなを聞く。
E の計算量がよくわからなかったので F の実装をしてもらい、E を詰める。
bit DP パートは普通にやれば $O(N{2}^N)$ になる。通れない状態をどうやって列挙するかが適当にやると $O(N^2{2}^N)$ になりそうなのでこれを考える。これはゼータ変換になりそうだが少し工夫が必要。
逆に工夫すれば $O(N{2}^N)$ になるし実装も簡単。 F が詰まってたので E を始める。

すぐに F の修正が思いついたらしいので交代して AC してもらいその後 E を始めるが、工夫の部分が間違っていたためサンプルが合わない。noshi さんが D を解けたっぽいので交代してもらい、自分はバグを探す。
バグはなさそうで、通れない状態を列挙するパートが間違っていそうだったので考えると全然違かった。修正を思いついたので 実装を変わってもらい E を FA する。

H を読んで、ソートして dp の形だけど dp は不可能すぎるとか考えるていると G が解けそうと Hemimor さんから言われる。確かに状態数が落ちそうですねみたいに言っていると D が通るので、特に実装するものがないので G をやってもらう。

I を聞いたり C,J を考えると順位表で Speed Star が H を FA していてびっくり。 noshi さんに問題概要を伝える、しかし特に何も思いつかない。しばらくして自分が燃やす埋める説みたいなことを言うと、 noshi さんに確かにそれで解けますと言われる。自分はあんまりどうしていいかわからなかったが適当に辺を張れば通るだろうと思って、詰まっていた G と変わり番子に maxflow の写経を始める。

写経が終わるが辺のはり方が全然わからなかった。自分はいつも燃やす埋めるを解くときは自分の競プロ用のノートを見ながら実装しているがそのノートを持ってくるのを忘れたため何もわからなくなった。

半分パニック状態みたいになっていると、noshi さんから K が解けたと報告を受ける。また、G も変わってほしいと言われたので、Hemimor さんに G を修正してもらいながら、辺のはり方について noshi さんに聞くが焦りで何も頭に入ってこなくなってしまったので、 noshi さんに実装もお願いしてもらうことにし自分は写経が間違っていないか確認することにした。

G が AC されその後 H も AC される。続けて noshi さんに K を実装してもらう。

K を実装してもらっている間、C,J を考えたり I の考察を Hemimor さんから聞いたりした。その時の考察はまずベクトルの問題に帰着した後、偏角ソートして貪欲にとるというものだった。それだと小数誤差がエグいことになるのでどうなんだろうと思いながら考えたりした。

ここの1時間もあんまり頭が回ってなくてやばかった。ご飯食べたりしながら色々考察するが、あんまりわからない。

K の実装が終わって提出されたが WA が出る。自分は K の内容を全く知らなかったため、 noshi さんから問題と実装内容を聞く。色々考え、コードを確認している間に noshi さんが間違っている箇所がわかっていたため修正して AC が出る。

みんなで I を考える。ベクトルをつなげていって、できたら削るみたいなことを最後にまとめてできないかということを考えると、想定解と同じ解放が生えてきた。でもこんなのどうなんだろうと思って提案すると noshi さんがそれで良さそうと言ってくれたので実装してもらう。取り急ぎで実装していたので Hemimor さんに途中で変わっていた。自分はありそうなコーナーケースを生やして実装してもらったものに対して試していたが、問題なく通ったので提出して AC が出る。

noshi さんに C を詰めてもらったり、 J は貪欲でいけるみたいな話を聞いて考察してみたりした。C は多項式の inv でできるんじゃないかということになったので、 畳み込みを Hemimor さんに写経してもらい自分はまだ J を考える。考察を重ねた結果 HLD をして、区間加算区間 min の構造体(と priority_queue)があればいいとなる。こんなの誰がどう考えても遅延 segment tree を使う場面だが、 普通の segtree で解けますと言って、 C の実装が詰まっている間に Hemimor さんに segtree の写経をしてもらう。HLD に関しては根っこまでのパスしか考えなくて良いのでライブラリは使わずにオレオレ実装でやる。

その間に C の実装が終わり提出するが RE 。J の実装を進めたり C を修正して提出したりを交互に行う。C はずっと TLE に苦しまされていて、 J は実装が一旦終わったが、無理して segtree を使ったり、HLD の部分でバグが大量発生していてそれの修正を探してちまちま修正する。Speed Star が全完してたらそもそも負けが確定なので、全完していないことを前提として何度も C に提出するが TLE が出続ける。何とか J のサンプルを合わせ提出するが全然結果が帰ってこない。2 分後に AC が帰ってきてガッツポーズ。

その後 noshi さんが C と戦ってくれたが TLE が取れず終了

懇親会は noya2 君と一緒にいた。他大学の人とも何人か話したが、主に東工大の人と話したりしていた。最後の方にはバイトで来ていた人たちも含め東工大関係者で写真を撮った。

終わりに

Speed Star に大差つけられちゃいました。また、予選と同じ 2 位だったが、予選の時とは違ってかなりギリギリだった。優勝争いしたかったができませんでした。

応援してくれた方々ありがとうございました。

2 位だし他の東工大チームが他の regional に行くこともないらしいのでプレイオフの進出は確定っぽい。予定がブッキングしないといいな。