ICPC2020 模擬地区 感想
-
コンテスト前
11時に起きて、昼食にカツカレーうどん(大盛)を食べました。おいしかったです。
13時からコンテストが始まるので、それに備えてログインを試みたり、競技ルールを読んだり、チョコレートに手が伸びそうになったり、水を飲むとみせかけて飲まなかったり、暖房を付けないとみせかけて付けたりしていました。
-
コンテスト中
難易度順不同の気持ちだったので、僕が前から、チームメイトが後ろから読みました。
(実際は去年と同じくABが簡単でそれ以外が順不同なので、ムーブとしては大間違い。)
以下、自分の関わった問題を時系列順にあげます。
-
A問題
シミュレーションする。うっかり一か所だけDとLを書き間違えて1WA。注意力3万。
-
B問題
中央値を見つけていけばよく、priority_queueを使ってO(N^2logN)で実装。定数倍軽いしTLEは大丈夫かなと思ったら大丈夫だった。
-
E問題
この前Div1で似たようなのあった気がする。各マスのとれる値の範囲をベルマンフォードを使って計算。負の時刻を操ることで2WAを生み出す(大反省)。
-
C問題
値が小さい順にまとめてDP。勘違いしまくってサンプルを合わせるまでに1年ぐらいかかり、サンプルが合ったので提出するとまさかのWA。そのあと
4
1 1 2 2
で落ちることを発見し、なんとか修正してAC。コンテスト中で一番悔しさの残る問題だった。ちなみに計算量はO(N^4)。
-
F問題
sortしてCHTしてくださいと書かれてあるので、見た目の割に結構実装重いなと感じつつも、一発AC。WAが出なくてよかった。
-
G問題
チームメイトが定数倍TLEで苦しんでいたので、「map<pair<int,ll>,ll>をやめてvector<map<ll,ll>>にするといいよ」と言ったらのちに通ってた。ナイス。
-
I問題
連立方程式を解いてくださいと問題文に書いているのでその通りにする。CFからコード引っ張ろうと思ったらタイミング悪くCFが落ちてて悲しかった。というか行列ライブラリ作ったはずなのに消えてるんだけど、誰か盗んだ？
「S自身はいつもSに到達可能」を読んでいなくて1WAしたが、そこ以外はすんなり。
-
次
チームメイト2人がそれぞれHとJを考えているらしいので、DとKを並列考察。
成果が得られず、その時点でQWE_QWEが通していたHを奪いに行くことに。
-
H問題
rの値が小さいので全探索すると、すんなり通ってよかった。
-
K問題
落ち着いて考えなおすと複素数になって、解けるようになった。
X=Y=0のケースで1WA。ひどいよ～
-
J問題
Dが解けそうになかったのでチームメイトが考えていたJを奪いに。
少し考えるとpath add zero countになったので、HLD+遅延セグ木でO(Q(logQ)^2)でAC。
見返したところ実装時間が24分で、思ったより早かったと自己満足。
-
コンテスト後
今日AGCあるってまじ？
-
まとめ
自分はもっと高難易度を攻めて、序中盤はもっとチームメイトに頼った方がいいなと反省しました。
今回の結果は大学別2位なのでおそらくWF進出圏内。本番でもこれぐらいのパフォーマンスが出したいところです。
-
おまけ
【こんなICPCの大会は嫌だ】KINGが1位の間コンテスト会場でKING
