tatyam’s blog

(ﾉ) - ω - (ヾ)ﾓﾁﾓﾁ

ICPC2021 国内予選 参加記

殴り書き

A : tatyam 100 までだからシミュレーションすればいいね〜 (2分くらい)
B : baton しばらくかかって AC
C : noshi めちゃくちゃ手こずってた C と D 交換した方がよかったかも
D : tatyam 置いた位置 mod 3 が 0, 1, 2 のやつを 1 個ずつ取るんだなあ (嘘)
3 つ均等に分けて総和の最小値の最大化
dp[1 つ目のグループの size][1 つ目のグループの総和][2 つ目のグループの size][2 つ目のグループの総和] = max 3 つ目のグループの総和 で 6 乗でやってみるか → WA
noshi : bool DP で良くない？ たしかに 出力に diff がないけど心配なので出してみる → WA
放棄して F へ　noshi が通した
E : baton めちゃくちゃがんばってた　これ得意なやつだったかも
F : tatyam 完全マッチングを 1-1, 2-2, 3-3, … とすると、s -> t 辺を s -> t に張ったグラフで全ての辺がいずれかのサイクルに含まれていればいい
強連結成分分解して、sink と source を 1 つずつペアにするといけそう
実装する → うまくペアを組まないといけない場合がある　どうすればいい？
(しばらく進捗なし)
次数が少ないやつから優先すればいい？
noshi : 逆向きに到達できない辺から張れば強連結成分が増えないのでうまくいく　確かに
途中までの実装があるのでがんばる (WA) ワーシャルフルイドが ijk になってる…… あれ diff がない これ 1 度辺を張った sink と source が残り続けてるな (AC)

なんとか戦犯じゃないレベルに　OK
G : noshi が O((3/2)n poly) (よく覚えてない) にできたっぽい　時間は足りない
H : これはなんですか？

感想

3 並列だけあって全体的に高難易度でしたね〜　ただ解かれてないのが 2 問もあって、もうちょっと簡単でもよかったかもね〜
東工大からは 3 チーム　めでたい
SPJ😿 (東大に行かなかった理由の 1 つはこれ)

前半の動きをもっと洗練する必要がありそう　アジアで完差つけないといけない状況はあまりやりたくないですよね
のしのしをどう活用するか　たぶん私たちが実装担当になった方がいいと思う
そういえば最近 Open Cup で問題文 (英語) の見た目から簡単な問題を選ぶことができることに気づきました

まだまだ知らない技術がいっぱいあるなあ (DM 分解, 反転)
精進をしたいところだがその時間があるかどうか……