Codeforces Round #529 (Div. 3), Codeforces Round #531 (Div. 3),Codeforces Round #535 (Div. 3) バチャ

Codeforces Round #529 (Div. 3)(2022/3/31)

A: Repeating Cipher

1文字目, 1+2文字目, 1+2+3文字目, ...を出力すればよい.
https://codeforces.com/contest/1095/submission/151459710

B: Array Stabilization

取り除くべきは数列の最大値or最小値. 両方試して小さい方を出力すればよい.
https://codeforces.com/contest/1095/submission/151459744

C: Powers Of Two

まず $N$ をできるだけ少ない個数の2冪の和で表す. これは $N$ の2進法表記を考えればよい. ここで使った個数が $K$ 以上なら構成不可能.
次に用いる2冪の数を増やしていく. 用いた2冪のうち, 1でないもの $2^d$ があれば, これらを $2^d=2^{d-1}+2^{d-1}$ と分解することで, 用いる2冪の数を1増やせる.
これを $K$ に達するまで繰り返せばよく, 途中で全てが1になったらそれ以上増やせないのでNO.
https://codeforces.com/contest/1095/submission/151459847

D: Circular Dance

人1の隣は $a_{1,1},\ a_{1,2}$ の2通りがあるが, ここを決め打ちすれば, 上手く構成できる場合一意に構成できる.
よってこれを試せばよい.
構成時には, 自身の次が既に決まっている状況では自身の2個先を決定できるので, これを繰り返せば, 常に自分の隣の人が決定済みという状況にできる.
https://codeforces.com/contest/1095/submission/151460362

E: Almost Regular Bracket Sequence

正しい括弧列=括弧列の総和が0かつ累積和が常に非負であることから考察を始める.
1個の括弧を反転させた時, その先の累積和の正負と総和というのは, 後ろ側からの累積minをとっておくと $O(1)$ で求まるので, 全て反転を試して, 正しい括弧列になった数をカウントすればよい.
https://codeforces.com/contest/1095/submission/151460621

F: Make It Connected

久しぶりにプリム法の最小全域木.
素直に全ての辺を考慮に入れると辺の数は $O(n^2+m)$ で間に合わない.
値が最小の頂点を起点とするプリム法のアルゴリズムを思い浮かべると, スペシャルオファーを用いないときは, 起点と新たに繋げる頂点を結ぶ辺がコスト最小である.
よって, スペシャルオファー以外で考えるべき辺は起点と他の頂点を結ぶものだけで良く, これで辺の数が $O(n+m)$ に落ちるので間に合う.
https://codeforces.com/contest/1095/submission/151461242

総括

1時間全完3ペナ83位. 自分としてはそこそこ良くできたと思ったが, そこまで高順位ではなかった. Dで2ペナしてしまったのとFでクラスカル法でやろうとしてうまくいかない時間があったのがロスだったかもしれない.

Codeforces Round #531 (Div. 3)(2022/3/31)

A: Integer Sequence Dividing

4の倍数に注目すると良い. $n\equiv 0,3\pmod 4$ ならば答えは0, そうでなければ1 である.
知識として知っていたので何も考えずにそのまま書き始めた.
敢えて証明を付けるとすると, まず答えが0となるためには $n$ 番目の三角数が偶数であることが必要. 逆に, 三角数が偶数の時, 三角数の半分を $a$ として, $n, n+(n-1), n+(n-1)+(n-2), \dots$ を考えていくと, どこかでそれ以上続けると $a$ を超えるというラインが現れるので, 残りは調整すればよい. 答えが1になる場合もほぼ同様に構成できる.
https://codeforces.com/contest/1102/submission/151478915

B: Array K-Coloring

まず $K$ 色すべて使うという条件を満たすため, 前から順に色1, 色2, ...と塗っていく. この時点で二つ目の条件に違反する恐れはない.
まだ色を塗っていないものものに関しては, 二つ目の条件に違反しないように, 同じ数字の中でまだ使われていない色を選ぶ. これは値毎にset等で使った色を見ればよい.
これで最後まで塗れたらOKである.
最後の懸案は, この方法だと塗りきれないが, 最初の前から順に塗っていたところを工夫したら塗分けられるパターンがあるのではないかという事であるが, もしこの方法で塗分けられないときは, ある値が色の数以上ある時なので, そもそも構成不可となる. よって最初に前から色を塗ってしまって何も問題がないのである.
https://codeforces.com/contest/1102/submission/151479360

C: Doors Breaking and Repairing

まず $X\gt Y$ の時は, 時間を掛ければ全てのドアを破壊できるので答えは $N$ である. そうでない時, "あなた" は一撃で壊せるドアを優先して壊そうとすべきである. なぜなら, 一撃で壊せないドアを叩いても, その直後に "Slavik" がそのドアを直すことによって, ドアの体力は元より増加してしまうからである.
"あなた" がとるべき戦略が決まれば, "Slavik" が取る戦略も分かる. "あなた" が一撃で壊せてしまうドアを先回りして直してしまい, 一撃で壊れないところまで体力を増やしてしまえばよいのである.
今, $X\le Y$ の時を考えているので, 一度直したドアは, "あなた" は一撃で壊すことはできない.
よって, このゲームの流れは "あなた" が一撃で壊せるドアを1枚ずつ壊す, 取り除く, 壊す, 取り除く, ... という繰り返しになる.
壊せる枚数は, "あなた" が一撃で壊せるもの(=与えられる値が $X$ 以下のドア) の数の半分, 小数点は切り上げである.
https://codeforces.com/contest/1102/submission/151479561

D: Balanced Ternary String

値を大きくしなければならないときは出来る限り後ろの文字を変更, 値を小さくしなければならないときは出来る限り前の文字を変更するのが最適である.
よって, 前から順に2,1を0に変更, 前から順に2を1に変更, 後ろから順に0,1を2に変更, 後ろから順に1を2に変更という事をすればよい.
但し, 変更回数が最小の物のうち, という制約があるので, 最終的な変更回数が増えるような変更を行わないように注意. https://codeforces.com/contest/1102/submission/151480179

E: Monotonic Renumeration

適当に小さい数で実験, 観察をすると大部分が同じ数でないといけないということに気づく. それもそのはずで, ある項の値が決まれば, それと同じ数の項は全て同じ値になり, その間の項も全て同じ数になり, さらには間の項の値と同じ数の項も同じ値になり, と連鎖するからである.
逆に, この連鎖に影響されない部分は, その直前と同じ値/+1の2通りを自由に選べる.
よって, この連鎖がおきる範囲を前から順に求めていき, 範囲外に出る度答えを2倍していけばよい.
https://codeforces.com/contest/1102/submission/151480685

F: Elongated Matrix

制約からとてもbitDP感が漂っていた.
1行目の行番号, 既に使い終わった行番号を表すbit, 現時点での一番下の行番号をDPに持たせる.
毎回更新を愚直にしていては間に合わないが, 事前に, 全ての行の組ごとに, それらの行を並べた時, 上下に隣り合う項の差の最小値を前計算しておけば, 更新が $O(1)$ で行える.
最終的な答えは, ここで求めたDPの値に, 最終行の値と1行目の値で隣り合う部分の差を反映させたものとなる.
計算量が [tex: O(2^n* n³+n^* m)] (実際には枝刈り的なループを抜ける処理を入れているので見た目よりは軽い) であったが十分間に合った.
https://codeforces.com/contest/1102/submission/151481593

総括

43分全完0ペナ5位. 完璧と言ってよいと思う. Bで若干方針に迷った以外は流れるように考察, 実装ができた. div3バチャを初めて初めてペナ0を達成できたのも嬉しい.

Codeforces Round #535 (Div. 3)(2022/4/1)

A: Two distinct points

題意の理解に苦労した. サンプルケースで落ちた場合ペナに加算されないという知見を得た.
問題自体は, 区間の端からそれぞれ取れば良い. 制約から端の組み合わせの全てがダメという事はありえない.
https://codeforces.com/contest/1108/submission/152292889

B: Divisors of Two Integers

一つ目の値は, 数列の最大値. 二つ目は, 一つ目の約数を1つずつ消して残ったものの最大値.
https://codeforces.com/contest/1108/submission/152293275

C: Nice Garland

色の並びを $3!=6$ 通り試して最も良かったものを出せばよい.
https://codeforces.com/contest/1108/submission/152293666

D: Diverse Garland

似た問題が数回前のdiv3でも出た気がするが見つけられなかった.
前から順番に見ていき, 隣接の2色が等しい時後半を変更すればよい.
変更後の色は自由に選べるので, そのさらに先と異なる色になるように選ぶ.
https://codeforces.com/contest/1108/submission/152294036

E1: Array and Segments (Easy version)

最大値としてどれを採用するかを決め打ちして全探索する.
この時, スコアを最大化するには, 最大値として選んだ項を含まない全ての区間を選ぶのが最適である.
上記の全ての区間を選んだとして, 各値がどう変化するかは変化量をimos法で求めれば線形時間でスコアを求められる.
提出はE2と同じものなので略.

E2: Array and Segments (Hard version)

今度は $N$ が大きいのでE1と全く同じことをするとTLEする. しかし, 項数に対して, 区間の数が少なく, 間に区間の境界が無いような連続する項は, 区間をどう選んでも値の変化量は等しい.
よって, 間に区間の境界が無いような連続する項を一つの値のように座圧することができる.
各項に持たせる値はその連続項の最大値と最小値のみで良いので, 数列の項数のオーダーが $N$ から $M$ に落ちる.
後は元の与えられる区間が座圧後のどこからどこまでの範囲をカバーするものかを求めて, E1と同じことをすればよい.
https://codeforces.com/contest/1108/submission/152298015

F: MST Unification

クラスカル法で最小全域木を求めた場合に選ぶ余地のある辺がどれだけあるかを考える.
どの辺を選ぶか選択の余地があるのは, 重みが等しく, 同じ連結成分の組をマージしようとする時である.
よって, 重みの昇順に, その重みの辺で, どの連結成分と連結成分(これらは異ならなければならない) をくっつけるものがいくつあるかを求めればよい. これはUnionFind でできる. この過程でもともと異なる連結成分をくっつける予定だったものが同じ連結成分をくっつけることになる場合があることに注意して処理をする. (最後のサンプル)
値を1増やすのみなので, 一度処理した辺が後程悪さをするような怖さがあるが, ここで一連の処理をした後はその辺を結ぶ2頂点は同じ連結成分に属しているので, 競合をおこす辺はそもそも選択の土俵に上がってこないため大丈夫である.
https://codeforces.com/contest/1108/submission/152299669

総括

1時間8分全完0ペナ28位. 座圧処理には毎度時間を取られてしまう.

仮のブログ

仮です