JOI2022 2次予選 参加記
参加記(やっていた、考えてたことのメモ)です
7:00 (-6:00)
2次予選0問目 "起床" AC—
12:57 (-0:03)
コードエディタを開くのを忘れており慌てて開く
準備はちゃんと、しようね！
(ここから競技開始後の経過時間)
0:01 A 問題 AC (100点)
去年の A 問題のようなのを予想して身構えていたので少し拍子抜け
キュー使うと楽になるいつもの ABC-C
0:06 B 問題 AC (200点)
皆大好き BFS
こっちも 去年のパンケーキとは違って ABC-C によくありそうな問題でびっくり
~0:10 C 問題
今度こそ激ヤバ問題が来るかと思って開く
制約が微妙な数字だった上にパッとそれっぽいコードが思いつかなかったのでスキップ
0:25 D 問題 WA
問題見る→実家 DP じゃん！→二次元セグ木を持ち出す(？？？)→サンプル合わせる→WA&TLE
軽率にデータ構造で殴ろうとする悪い癖が出た
0:38 D 問題 AC (300点)
二次元セグ木なんて使わなくても適当にメモしてあげれば大丈夫だということに気付く
遷移が若干ややこしいけど diff 1400 くらいな印象
0:59 C 問題 AC (400点)
揃えたい和と縦の分割方法が定まれば横は一意に定まることに気付く
作れる和は A_i,j の和 /2 ~ /(H*W) の範囲に収まりそうだったのでその範囲で累積和を使って判定 + OK だった範囲の左端から右端に辺を張って、全体の左端から右端への道順を足せば答えだろう
という解を書くがサンプルが合わない
横の分割方法が異なるものが存在していることに気付いたので分割した場所を 2 進数で記録→同じものだけを辿ると AC
1:19 E 問題 部分点 (416点)
ひとまず自明部分点を取りに行く
小課題 1 は愚直
小課題 2 は S[u] != S[v] である辺を記録して一致するものがあるか見る
2:04 E 問題 WA
クエリ先読みして繋ぐ地域が同じものを一括で処理する方針で実装
Undo 可能 Union-Find があればできると考え持っていた Union-Find を改造する(？？？)
サンプルは合ったが提出したらボロボロ
2:22 E 問題 AC (500点)
Undo 可能 UF が無くても適宜座圧 BFS をすればいいことに気付く
実装して提出すると 3765ms (？？) で AC
結果
満点です！！やった！！
