Codeforces Round #656 (Div. 3), Codeforces Round #661 (Div. 3), Codeforces Round #667 (Div. 3) バチャ

Codeforces Round #656 (Div. 3)(2022/5/4)

A: Three Pairwise Maximums

ひたすら場合分けをした. 公式解説によると1パターンだけ場合分けをすればよかったらしい.
https://codeforces.com/contest/1385/submission/155820941

B: Restore the Permutation by Merger

前から見ていって, 初出の数なら答えの順列に追加, そうでなければ無視をすればよい.
https://codeforces.com/contest/1385/submission/155821146

C: Make It Good

良い数列は, 広義単調増加列と広義単調減少列をくっつけた形になっている.
よって, このような形が元の数列の末尾にどれだけの長さであるかを求めればよい.
https://codeforces.com/contest/1385/submission/155821429

D: a-Good String

答えは,

sの前半を全てaに, 後半をb-good にする操作回数
sの後半を全てaに, 前半をb-good にする操作回数

の小さい方となる. よって, これを再帰的に計算していけばよい.
一見再帰の長さがとんでもないことになりそうであるが, 再帰で深堀する文字列の長さが半分に, 場合分けが2通りになるので, 再帰の深さ毎でみている文字列長の総和は一定である.
再帰の深さは $\log$ であるので十分間に合う.
https://codeforces.com/contest/1385/submission/155822065

E: Directing Edges

sccをして, その時点で有向ループが存在したら不可能.
存在しなかったら, sccの上流から下流に向かって向き付けをすればよい.
https://codeforces.com/contest/1385/submission/155822946

F: Removing Leaves

各頂点について, 葉である子をいくつ持っているか, 辺が何本伸びているかを求めておく.
葉である子を $k$ 個以上持っている頂点はqueueに入れて置く.
queueから取り出すときは, 葉である子を $k$ 個消し, まだ葉である子を $k$ 個以上持っている頂点はqueueに入れ直す. この操作によって自身が葉になった場合は親の持つ葉の数を1加算する.
https://codeforces.com/contest/1385/submission/155824152

G: Columns Swaps

全ての数が丁度2回現れるのが必要条件.
これを満たす場合, 各数が上列下列のどっちに表れるかによって, その数の存在する2つの列を共にswapする\しない or 片方だけswapするの2通りに絞れる.
各列を頂点に, このような関係を辺に持つグラフを考えると, 各連結成分の1頂点をswapするか否かを決め打ちすると, 先ほどの条件から連結成分内の各列をswapするかが一意に定まるので, 決め打ちして総swap回数が小さくなる方を選べばよい.
https://codeforces.com/contest/1385/submission/155826854

総括

1時間27分全完0ペナ40位. 難しかった後半2問をどっちも通せたので満足.

Codeforces Round #661 (Div. 3)(2022/5/4)

A: Remove Smallest

昇順にソートした時に隣接項の差が1であれば良い.
この時小さい2つを選び続ければ目標は達成され, そうでない時明らかに不可能.
https://codeforces.com/contest/1399/submission/155848025

B: Gifts Fixing

$a$ は $a$ の最小値にするのが良く, $b$ は $b$ の最小値にするのが良い.
この時各贈物から飴とオレンジをいくつずつ減らせばよいか分かるので, できるだけ2つセットで減らしたのち, さらに減らす必要のある方を減らせばよい.
https://codeforces.com/contest/1399/submission/155848251

C: Boats Competition

$s$ は2以上 $2\max{w}$ 以下のみを考えればよい.
$s$ を決め打ちした後は, 貪欲にペアを組んでいってよく, ペア相手がいるかをmultisetで持っておけばよい. 単に配列で持っても良い.
https://codeforces.com/contest/1399/submission/155848677

D: Binary String To Subsequences

前から処理をしていく. 現在作れている文字列で, 末尾が0であるもの, 1であるものをそれぞれ管理する.
次の文字が1である場合, 末尾が0のものがあればそこに1をつけたし, 末尾が1であるものの方に移す. 末尾が0のものが無ければ新たな文字列"1"を用意して末尾が1であるものに追加する.
0の場合はこの逆をする.
実際に毎回文字を追加したり動かしたりするとおそらくTLEするので文字列は別の場所で用意してindexのみを動かす.
https://codeforces.com/contest/1399/submission/155849196

E1: Weights Division (easy version)

初めに各頂点について部分木に葉をいくつ持つかを木DPで計算しておくと, 各辺の重みを半分にしたときに重みの総和がどれだけ減るかが求まる.
この減少量を優先度付きキューで管理して, 総和が $S$ 以下になるまで減少量最大を適用していけばよい. 減少後は次にその辺を選んだ場合の減少量を計算してキューに戻す.
https://codeforces.com/contest/1399/submission/155850558

E2: Weights Division (hard version)

E1の方法を利用すると, コスト1の辺のみを $i$ 回選んだ場合の総和の減少最大値 DP $\lbrack i\rbrack$ を求めることができる. 同様にしてコスト2の方も計算しておく.
すると, コスト1の辺を選ぶ回数を決め打ちした時にコスト2の辺を何回選ばないといけないかがlower_boundで求まり, コストの総和を高速に求められるので, コスト1の辺を選ぶ回数を全探索すればよい.
https://codeforces.com/contest/1399/submission/155852134

F: Yet Another Segments Subset

$O(n^3)$ の区間DPはすぐに思いついたがそこから少々時間がかかった.
$O(n^3)$ の区間DPは以下のようにする.
まず座標を座圧してすべての座標を $n$ 以下にしておく.
DP $\lbrack L\rbrack\lbrack R\rbrack$ には区間を $\lbrack L\rbrack\lbrack R\rbrack$ に絞った時の答えを持たせる. 区間幅の小さい方から順に求めていき, 更新はその区間の2分割を全て試せばよい.
区間が $O(n^2)$ 通りあり, 更新が $O(n)$ かかるので, 全体で $O(n^3)$ かかってしまう.
ここから高速化するには, セグメントの数が $n$ 個である事を利用する.
区間の更新をする際に, 左端を1ずらすか左端が $L$ であるセグメントを調べるようにすればよい.
https://codeforces.com/contest/1399/submission/155855163

総括

1時間21分4ペナ全完42位.

Codeforces Round #667 (Div. 3)(2022/5/5)

A: Yet Another Two Integers Problem

$|a-b|$ を10で切り上げ除算すればよい.
https://codeforces.com/contest/1409/submission/155890407

B: Minimum Product

$a$ をできるだけ減らしたのち $b$ をできるだけ減らすか, $b$ をできるだけ減らしたのち, $a$ をできるだけ減らすかをすればよい.
これは和が一定の2正整数の積は2数の差が大きいほど小さいことからこの方法で良いことが示せる.
https://codeforces.com/contest/1409/submission/155890736

C: Yet Another Array Restoration

初項と公差を全て試して最も良いのを出せばよい.
https://codeforces.com/contest/1409/submission/155891093

D: Decrease the Sum of Digits

最終的な $n$ の値は, 下から $k$ 桁全て0 で, 下から $k+1$ 桁目が元より1大きくて, 残りの桁は元と等しいという形となる. この候補は少ないので順番に試していけばよい.
https://codeforces.com/contest/1409/submission/155891311

E: Two Platforms

まず $y$ 座標はいらない情報であるので, 1次元座標と思ってよい.
また, プラットフォームの左端は点の位置としてよい.
$x$ 座標を昇順にソートすると, 各点を左端にプラットフォームを置いた場合に何個の点を拾えるかがlower_boundなどで求まる. これを前計算しておくと, 右側のプラットフォームの左端の位置を決め打ちした時に左側のプラットフォームを置く位置を前計算情報から求めることが出来る.
https://codeforces.com/contest/1409/submission/155891742

F: Subsequences of Length Two

$t$ の二文字が同じ場合, $s$ の $t$ と異なる文字ならどの位置の文字を変えても答えに影響しない.
そうでない時, DP $\lbrack i\rbrack\lbrack k\rbrack\lbrack j\rbrack$ で $s$ の前から $i$ 文字見た時に, $k$ 文字を書き換えて, $i$ 文字目より前に $t$ の1文字目が $j$ 個現れる場合の, $t$ を部分文字列としてもつ数の最大値という動的計画法を行う.
遷移は $s$ の $i$ 文字目が $t$ の文字と等しいか否かで場合分けして $O(1)$ で行える. 状態数は $O(n^2k)$ であるので全体の計算量は $O(n^\2k)$ である.
https://codeforces.com/contest/1409/submission/155893029

総括

54分全完0ペナ40位. Fに時間がかかったが, 及第点.

仮のブログ

仮です