Codeforces Round #784 (Div. 4)(2022/4/22)
数少ないdiv4. 当日は眠すぎたので翌日バチャ参加.
A: Division?
if文を用いて場合分けを行う.
https://codeforces.com/contest/1669/submission/154503167
B: Triple
連想配列を用意して, 数列に各値が何度現れるかを記録していく.
全ての記録が終わったら連想配列の中を順に見ていき, 3回以上現れた数があるか確認する.
https://codeforces.com/contest/1669/submission/154503316
C: Odd/Even Increments
まず数列を偶数番目の項と奇数番目の項に分ける.
各操作でそれぞれの数列内の偶奇は全て一斉に変わるため, 各数列内に偶奇の異なるものがあればそれらは何度操作をしても偶奇を一致させることはできない.
逆にそうでない時, 高々1回の操作で(元の数列において)全ての項の偶奇を一致させることができる.
結局, それぞれの数列内の偶奇が全て一致しているかを判定すればよい.
https://codeforces.com/contest/1669/submission/154503531
D: Colorful Stamp
白いマスにはスタンプは押されないため, まずマス目を白いマスで区切って考える.
この時, 各連結のマス目において, 適切なスタンプの押し方がある事と, 赤マスと青マスの両方が存在することは同値である. (赤マスと青マスが両方ある時, どこかに赤マスと青マスが並んでいる場所があり, そこを以外を適当にスタンプを押していき, 最後にことなる色が並んでいる場所にスタンプすればよい. )
よって, 各連結成分を前から見ていき, 赤マスと青マスのそれぞれの出現を管理しておけばよい.
https://codeforces.com/contest/1669/submission/154503780
E: 2-Letter Strings
求めるペアの数は, (少なくとも1文字目が等しいペアの数)+(少なくとも2文字目が等しいペアの数)-2(1文字目と2文字目が等しいペアの数) であるので連想配列でそれぞれの数を持っておけばよい.
https://codeforces.com/contest/1669/submission/154504207
F: Eating Candies
前からの累積和と後ろからの累積和が一致する場所を探せばよい.
前からの累積和を事前に計算しておけば, 後ろからいくつ取るかを全探索して, 前からの累積和で一致する場所があるかをlower_bound等で高速に求められる.
https://codeforces.com/contest/1669/submission/154504562
G: Fall Down
列ごとに独立に見ていく.
制約に余裕があるため下の石から見ていって落下をシミュレーションという方針でも通ると思う.
自分は, 上から各障害物間に何個の石があるかを数えていき, その数分だけ障害物の上に積もらせるという方針を取った. 計算量はこちらの方が良い.
https://codeforces.com/contest/1669/submission/154512129
H: Maximal AND
出来るだけ上の桁が1になるようにしていく.
ある桁を最終的に1にするために, その桁に対して行う必要のある操作回数は, の要素でその桁が0であるものの数だけである.
よって, 各桁について, その桁が0である要素の数を求めておき, 上の桁から順に操作回数 を消費して変更を加えていけばよい.
https://codeforces.com/contest/1669/submission/154505247
総括
23分全完0ペナ53位. 気持ちよくSpeedrunできた. 100点.
