Codeforces Round 1014

スポンサーリンク

A. Kamilka and the Sheep

max – min です.超えないことも実現できることも簡単.

B. Lady Bug

「$A$ の偶数インデックス,$B$ の奇数インデックス」の中で自由にスワップできます.

「$A$ の奇数インデックス,$B$ の偶数インデックス」の中で自由にスワップできます.

それ以外はできません.

C. Asuna and the Mosquitoes

偶数奇数の片方の種類しかない場合は自明です.

それ以外は,操作によって偶数・奇数の個数は変化しません.その不変量のもと,ひとつ以外の要素は $1$ 以下であるようにできます.$2$ 以上の要素が $2$ 個以上あるならその個数を減らせることがいえます.

D. Mishkin Energizer

文字種類が 1 種類だと不可能です.そうでないとします.

文字を ABC として,A が出現回数最多だとします.A とそれ以外の隣接箇所を適当にとります.

AB → ACB → ABCB などとすれば,A 以外の出現回数をひとつ増やせます.相対的に見れば A の回数がひとつ減っています.これを繰り返します.

E. She knows…

書き込む値は 0, 1 のどちらかだとします.「隣接する $2$ マスの和が奇数である場所の個数を偶数個にしてください」となります.すると「隣接する $2$ マスの和の総和を偶数個にしてください」となります.すると各マスの値が次数分寄与することが分かります.奇数次数のマスがいくつ埋まっているかと現在の和などを持ちます.

F. Andryusha and CCB

まず (beauty, k) を決めたときにそれが達成可能な prefix length を求めることにします.これは区間になります(証明は詰めなかったが $k$ で帰納法で証明できると思う).

(beauty, k) という組は調和級数 $O(N\log N)$ 通りしか出てきません.$k$ が定数であるような区間をまとめて ANS に足しこめばよいです.

区間の和集合を求めるところは,$k$ が定数であるような区間 $(l,r)$ は,beauty について $l$ も $r$ も単調増加することから,改めてソートする必要などはなくて線形時間でできます.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました