6完41:05 234位
G解けたと思って40分バグらせたのかなしすぎる
A Majority
もうforのあるAにも慣れてしまった、数えるだけ
(AC 2:16)
B Postal Card
下3桁しか見なくてよいので、あらかじめ余分なところを落としてしまいます
そしたらただ一致判定するだけ
(AC 5:03)
C Path Graph?
これこわい
とりあえず、N-1=Mでないといけないのはいいですが、変な形になっていないか確かめる必要があります
もっと楽なやり方ありそうだけど素直に
・次数が1のもの2つ残りは2
・全体が連結である
をそれぞれ判定しました
(AC 13:28)
D Match or Not
これもABC-D典型ですね
左右から挟んでいるので、左右それぞれの値を前計算しておけばいいです
累積和とかでもよくあるやつ
(AC 20:20)
E Karuta
なんでE?と思ったけど、想定解がむずかしかった
一番LCPが大きくなるのは辞書順で隣り合うものになります
よって、ソートして愚直に隣だけ比較すればよくて、それぞれの文字列の比較回数が2回ですむので、全体でO(NlogN)となります
(AC 26:02)
F Components
これです
そのまま貼るというわけにはいかないのですがほぼ同じで、「各頂点を選んだか？」という情報を持ちながらDPしてあげればいいと思います
制約もO(N^2)を許す制約をしている(ちょっとこわいけど)ので、ほぼほぼ二乗の木DPだろうとなります
遷移は過去問ほどややこしくなく、もし1つでも子とつなぐなら連結成分が増えない、そうでなくてその頂点を選ぶなら増えるということを実装してあげればよいです
それなりにわかりやすく書けたと思います(ぼくの提出)
(AC 41:05)
G Balance Update Query
まず変更がないとして、処理の仕方を考えます
これは割と自明で、ソートしておいて大きい順からとればよいです
なので、ソートした形をなんとかして維持できるといいな～と思います
aiは大きいですが、出てくる種類数はN+Q以内であるため、クエリを先読みして座圧します
こうすると、各数字における個数を管理することでソート状態を保てます
では、クエリに高速に答えていきましょう
クエリ1,2：これは各数字における個数を更新すればよいです
クエリ3:ここが本番です、愚直にやると大きい順からたどるので各クエリに最悪N+Q回かかってしまいます
この問題を解消しましょう
必要なことは[i:N+Q]の和がx以上となる最大のiをみつけることです
これはセグメント木での二分探索を用いるとO(log(N+Q))で解けます
よって、クエリ3にも高速に答えることができ解けました
本番はセグ木への加算がバグって通らず...
(AC --:--)
総括
G通して勝てると思ったんだけどな
