仮のブログ

仮です

Codeforces Round #575 (Div. 3), Codeforces Round #579 (Div. 3), Codeforces Round #582 (Div. 3) バチャ

コドフォ

Codeforces Round #575 (Div. 3)(2022/4/6)

A: Three Piles of Candies

最も大きいう山を二人で分配することにすれば, 半々に分けることができるので総和割る2を出力すればよい.
https://codeforces.com/contest/1196/submission/152813037

B: Odd Sum Segments

前から累積和が奇数になったらそこで数列を切り離して, 累積和をリセットというのを数列が k 個になるまで行えばよい. 最後の1つの和が偶数となってしまったり, そもそも数列を k 個に分けられなければ不可能.
https://codeforces.com/contest/1196/submission/152813246

C: Robot Breakout

各ロボットの到達できる範囲は長方形となる. (どこまでも行ける場合は 10^5 で止まるとしてよい) それぞれの移動可能範囲の下限, 上限, 左限, 右限についての最大値または最小値を取っていくと, 全てのロボットが到達できる範囲が求まる.
https://codeforces.com/contest/1196/submission/152813516

D1: RGB Substring (easy version)

D2と同じ.

D2: RGB Substring (hard version)

1文字目から k 文字目が "RGBRGB..." とどれだけ一致しているかと, 2文字目から k+1 文字目が "GBRGBR..." とどれだけ一致しているかはほとんどのチェックを再利用できる.
よって, 文字列を決め打ちした時部分文字列としてとる範囲を尺取り法の気持ちで一つずつずらしていくと, 直前の結果を再利用することで全体で O(n) で求めることができる.
文字列として考えるべきは "RGBRGB..."とどれだけずれているかの3通りだけなので間に合う.
https://codeforces.com/contest/1196/submission/152813917

E: Connected Component on a Chessboard

片方の色に対してもう片方があまりにも多かったら構成出来なさそうである.
どれくらいの差なら構成できるかを考えると, 多い方の数が, 少ない方の3倍+1以下だったら作れることが分かる. ((1,4) は明らかに作れて, そこから1マス少ない方を伸ばすごとに多い方としてくっつけられるマスが高々3つまで付けられる)
また, 実際にこれを実現する方法には少ない方の色が横1直線に並ぶようにしてその周囲に多い方のマスをくっつけるというものがあり, さらにこの方法では多い方の使うマスの数を容易に調整できる.
結局, 白黒白黒...と並べていき, 余った多い方の色を周囲にくっつけていくだけで良い.
https://codeforces.com/contest/1196/submission/152814852

F: K-th Path

一瞬k-th shortest path でYen's Algorithm でも使うのか?と身構えたが, この問題は多始点多終点なので難しそう.
制約を見ると, 際立って小さいのが k である. この小ささを利用する方法を考えると, そもそも辺も小さい方から k 本のみを見ればよいことが分かる. さらに頂点も, これら高々 k 本の辺をなす頂点のみを考えればよいことが分かる.
よって, 問題が一気に頂点数 O(k) の問題に落ち, このサイズならワーシャルフロイド法で全頂点間のパス長を求めることができるので, 小さい方から k 番目を求めることができる.
(400*2)^3 が間に合うかちょっと不安だったが, 1secもかからず通った.
https://codeforces.com/contest/1196/submission/152815797

総括

56分全完2ペナ10位. とても良い. Fで実際に小さいケースを描いて試せたのが良かった気がする.

Codeforces Round #579 (Div. 3)(2022/4/7)

A: Circle of Students

条件を読解して満たしているかを確認する.
https://codeforces.com/contest/1203/submission/152925902

B: Equal Rectangles

まず向かいあう2辺は長さが等しいので, 同じ長さの物で2つ組を作っていけるかを確かめる.
これは, 昇順ソートをして, 2i 番目と 2i+1 番目が等しいかを調べればよい.
次に, 面積を全て等しくできるかを見ていく. 最長辺が最短辺以外の辺と長方形をなしたとすると, 最短辺を含む長方形は明らかにこれより面積が小さくなってしまう.
よって, 最長と最短はペアにするしかなく, これを繰り返せば大きい方と小さい方から順にペアにしていけばよいことが分かる.
https://codeforces.com/contest/1203/submission/152926110

C: Common Divisors

数列の項の最大公約数の約数の数を求めればよい.
最大公約数は全体で O(n\log{n}) で, 約数の個数カウントは O(\sqrt{n}) でやればよい.
https://codeforces.com/contest/1203/submission/152926262

D1: Remove the Substring (easy version)

D2と同じ解き方をした.
D1としての想定解はおそらく, 抜き取る部分列を O(|S|^2) 通り全て試し, T を部分列として含むか確かめる方法だと思う.

D2: Remove the Substring (hard version)

部分列を抜き取った後, S は2つの文字列に分かれる. (片方が空文字列となる場合もある.) この2つのうち, 前の部分から T の i 文字目までを作り出すときの抜き出せる部分列の最長を求めて, i を全探索する.
i を決め打つと, T の前 i 文字は S の前の方で作った方が良く, T の後ろ |T|-i 文字は S の後ろに詰めれるだけ詰めた方が間を広くとれる. よって, S の部分列として T を取り出すときに, 出来るだけ前から作り出すときとできるだけ後ろから作り出すときそれぞれで T の i 文字目がどこから取り出せるかを前計算しておけばよい.
https://codeforces.com/contest/1203/submission/152927095

E: Boxers

重い人から順に重さを決定していき, 各重さの人は重くする方を優先して, その重さの人がいなければその重さにすれば最適.
https://codeforces.com/contest/1203/submission/152927645

F1: Complete the Projects (easy version)

まず, 得られる経験が非負のタスクを先にすべてこなすのが最適.
この時, 要求値が低いタスクからやるのが最適で, 途中でできないタスクに遭遇した場合答えはNOである.
残りの, 経験が負のタスクであるが, 結論から書くと a+b の大きい順に処理していくのが最適である.
タスク1: a_1, b_1 と タスク2: a_2, b_2 があり, a_1+b_1\lt a_2+b_2 であったとする.
タスク1→タスク2の順で処理できた場合, 初期値を r とすると, タスクを終わらせられる条件は,
r\ge a_1 ,r+b_1\gt0, r+b_1\ge a_2, r+b_1+r+b_2\gt 0 である.
このうち, タスクの順序を考慮する上で意味のある条件は, r\ge a_1, r+b_1\ge a_2 であるので, r\ge a_1, r+b_1\ge a_2, a_1+b_1\lt a_2+b_2\Rightarrow r\ge a_2, r+b_2\ge a_1 を示せばよい.
r+b_1\ge a_2, b_1\lt 0 より, r\ge a_2 は明らか.
a_1+b_1\lt a_2+b_2 の両辺に r-a_2 を足して, r+b_1+a_1-a_2\lt r+b_2
r+b_1\ge a_2 より, a_1\lt r+b_2
よって, a+b が大きいタスクからやってよいことが分かったので, この通りにソートして途中で不可能にならないか判定する.
Atcoderに絶対類題があるが思い出せなかった.
https://codeforces.com/contest/1203/submission/152928328

F2: Complete the Projects (hard version)

F1と同じように, 経験が正のものを先にこなして, 残りは a+b の大きい順に取るのが良い.
とる順序さえ決まってしまえば, 後は現在の経験が r の時のタスク量の最大値を持たせた配列で動的計画法をすればよい.
r として考えるべき値が 60000 以下で良く, タスクは 100 個しかないため十分間に合う.
F1で何で制約がこんなに小さいのかナゾだったが, F2の解法を思いついて完全に納得した.
https://codeforces.com/contest/1203/submission/152929009

総括

41分全完1ペナ3位!! 文句なし.

Codeforces Round #582 (Div. 3)(2022/4/11)

A: Chips Moving

偶数地点にあるものを全て0に, 奇数地点にあるものを全て1に集めるのはノーコストでできる.
よって, 最後に0に集めるか1に集めるかでコストの計算をすれば良く, 偶数の数と奇数の数の少ない方が最小コストとなる.
https://codeforces.com/contest/1213/submission/153382811

B: Bad Prices

a_{i} が悪い値 \Leftrightarrow a_{i}\gt \min\lbrace a_{i+1},\dots,a_{N}\rbrace であるので, 数列の後ろの方から \min を更新しながら見ていけばよい.
https://codeforces.com/contest/1213/submission/153383131

C: Book Reading

10m 周期で考えればよい. 10m 周期が本を読む間に何回あるかをカウントし, 残りは個別で数える.
https://codeforces.com/contest/1213/submission/153383386

D1: Equalizing by Division (easy version)

D2と同じ.

D2: Equalizing by Division (hard version)

全ての数を0になるまで操作をしたとしても, 操作回数は 10^7 回以下であるので全ての操作をしてみるだけの時間はある.
よって, D\lbrack i\rbrack\lbrack j\rbrack : j 回の操作で i となる数の個数という配列を用意できる.
これが用意できれば, 各数を K 個作るのにかかる操作回数が求まるのでそれらの最小値を取ればよい.
https://codeforces.com/contest/1213/submission/153384153

E: Two Small Strings

"aabbcc" のように, 同じ文字の塊を3つ繋げるのと, "abcabc" のように, 3種からなる長さ3の文字列を n 個繰り返すのを全て試せば必ずどこかに条件を満たすものがある.
証明は以下のようにできる.

  1. "abcabc..." と "acbacb..." がどちらも条件を満たさない時, s\in \lbrace ab,bc,ca \rbrace, t\in \lbrace ac,cb,ba\rbrace である.
  2. 1.において, s=ab,t=ba のように, 使われない文字がある時, それを挟むように文字を連続させればよい. (この場合, "aa...acc...cbb...b")
    1. でない時, s=ab,t=ac のように, s,t のどちらかの文字は一致している. その文字が最初か最後になるように文字を連続させればよい. (この場合 "bb...bcc...caa...a")

これですべてが尽くされる.
https://codeforces.com/contest/1213/submission/153385036

F: Unstable String Sort

強連結成分分解をしたときに, 異なる連結成分に含まれることと, 異なる文字を割り当てられることは同値である.
よって, 強連結成分の成分数が k 以上か判定した後, 親側から順に a,b,...と割り振っていけばよい.
https://codeforces.com/contest/1213/submission/153385708

G: Path Queries

パスの最大値が w 以下であることと, コストが w 以下の辺のみからなる部分グラフで同じ連結成分になる事は同値である.
よって, クエリを昇順にして, 順に辺を追加しながら同じ連結成分にある頂点の組の数を数えていけばよい.
頂点数が a,b の二つの連結成分を結合すると, 同じ連結成分にある頂点の組の数は ab 個増える.
これらの管理はUnionFind で行えばよい.
https://codeforces.com/contest/1213/submission/153386776

総括

41分全完2ペナ7位. かなり良い. Gでオーバーフローで1ペナ+デバッグ4分で14分失っているのでもったいなかった.