2024/3/23(土)
ABC346に出た。
A: やるだけ
B: 1オクターブ分は取って構わないので、まず{B-=5;W-=7;}
を繰り返す。その上で2オクターブの中の連続部分文字列を全探索する。BとWのうち片方にものすごく偏ってる場合は死ぬのでそれは別途検出する。これを忘れて1WA。
C: setに記録してK(K+1)/2から引く。
D: 01交互の列のどこか一カ所だけ連続、という文字列なので、左端からi文字を010101…にしたときのコスト、10101…にしたときのコスト、右端からi文字を同様にしたときのコストをそれぞれ求める。こうすると各場所で連続させた場合の全体コストを各O(1)で求められるので、全体O(N)で求められる。
E: 最後に書き換えた時刻を記録すればよい。ある列はより後で書き換えた行、行はより後で書き換えた列によって上書きされるのでその分を引く。
Categories: 未分類