Codeforces Round #479 (Div. 3), Codeforces Round #481 (Div. 3), Codeforces Round #486 (Div. 3) バチャ

Codeforces Round #479 (Div. 3)(2022/3/25)

A: Wrong Subtraction

指示通りに-1と/10を行っていく.
https://codeforces.com/contest/977/submission/150834915

B: Two-gram

2文字をmapとかで数えていく.
https://codeforces.com/contest/977/submission/150835013

C: Less or Equal

ソートして小さい方からk番目を求める. この時にk番目とk+1番目が区別できなければ-1
適当に番兵を入れておくと楽だが番兵をそのままにしてしまい1ペナ
https://codeforces.com/contest/977/submission/150835106

D: Divide by three, multiply by two

元の数列において3で割れる回数は非増加→3で割れる回数の多い順にソート
3で割れる回数が等しい区間は2倍する操作を行うので値そのものを昇順ソート
https://codeforces.com/contest/977/submission/150835254

E: Cyclic Components

各連結成分毎に頂点数=辺数か?と全ての頂点の次数は2か?を調べる. BFS
https://codeforces.com/contest/977/submission/150835400

F: Consecutive Subsequence

最大の長さは何かを求めて後から復元
mapに $a_i$ を列に含める時の長さの最大値を管理する. $i$ の昇順に見ていき, mapに $a_i-1$ が存在すればそれ+1, 存在しなければ1である.
これで列の長さの最大と, その列の値が求まっているので復元は前から貪欲にとっていけばよい.
https://codeforces.com/contest/977/submission/150835665

総括

25分1ペナ全完33位. Dが面白かった

Codeforces Round #481 (Div. 3)(2022/3/25)

A: Remove Duplicates

setかなんかで被りがあるかを判定しなければ採用していく.
https://codeforces.com/contest/978/submission/150836487

B: File Name

xが3個以上並んでいる場所は操作が必要で, xが $a$ 個並んでいる場所は $a-2$ 個消す必要がある.
https://codeforces.com/contest/978/submission/150836565

C: Letters

部屋数の累積和をとっておき, 二分探索でどの寮かを求める. 部屋番号も累積和との差で求まる.
https://codeforces.com/contest/978/submission/150836759

D: Almost Arithmetic Progression

初項と2項目の{-1,0,+1} の組み合わせ9通りを全探索する. 最初2項が決まれば等差数列は一意に定まり, 操作によって目的の等差数列にできるか, 操作は何回必要かを求めることができる.
https://codeforces.com/contest/978/submission/150837052

E: Bus Video System

乗客数の初期値を $a$ 人で仮置きしてシミュレーションすると, 乗車人数が負にならないことと定員オーバーしないことから $a$ の上限, 下限が求まる.
https://codeforces.com/contest/978/submission/150837172

F: Mentors

$r$ の小さい順に見ていく. 仲の悪い組が無ければメンターになれる人数は既にみた(=自分より $r$ が小さい)人の人数である. (同じ $r$ の時に数え間違えに注意)
仲の悪い組は後から別個に除外すればよい.
https://codeforces.com/contest/978/submission/150837538

G: Petya's Exams

試験告知が出ているかつ勉強時間が足りていない教科のうち, 試験が最も近い教科から貪欲に勉強していく. これは試験告知が出ているかつ勉強時間が足りていない教科a,b(aの方が早くに試験があるとする)があった時に, もし今bを勉強して全ての試験勉強をこなせるスケジュールがあったとすると, 後ほどどこかでやることになるaの試験勉強の時間にbの試験勉強をして, 今aの試験勉強をすることができることから最適性が示せる.
実装は優先度付きキューなどで, 試験告知が出ている教科を試験日の昇順をkeyに入れていけばよい. 試験のない日にはキューから一つ取り出して, 勉強をし, 勉強が足りなければキューに戻すを繰り返せばよい. なお取り出した時点で試験日を過ぎておりかつテスト勉強が足りていない場合はその時点でNGである.(この処理を忘れて1ペナした) 最終的に全ての試験勉強が終わればOK. 無理だったらNG.
https://codeforces.com/contest/978/submission/150838115

総括

52分1ペナ全完112位. Dが面白かった.

Codeforces Round #486 (Div. 3)(2022/3/28)

A: Diverse Team

setかなんかで被りがあるかを判定しなければ採用していく. 採用数がK以上ならOK
https://codeforces.com/contest/988/submission/151206861

B: Substrings Sort

明らかに文字数の小さい順に並べなければならない. 小さい順に並べたものが条件を満たすかは愚直に見ていって間に合う.
https://codeforces.com/contest/988/submission/151207130

C: Equal Sums

各数列から1つ取り除いた時の総和をmapかなんかで管理して置き, 同じ値を作りだせるかを調べる. この時に一緒に数列番号と取り除いた番号を管理しておくと復元が不要で楽できる.
https://codeforces.com/contest/988/submission/151207504

D: Points and Powers of Two

実は答えの上限が小さいシリーズ.
$x,y,z\ (x\lt y\lt z)$ を採用したとすると $z-y=2^{a}, y-x=2^{b}, z-x=2^{a}+2^{b}$ と表せ, これが2のべき乗であるためには $a=b$ が必要十分である.
よって, もしここにさらに, $w\ (z\lt w)$ を採用できたとすると, $x,z,w$ を採用できたことから, $w-z=z-x=2^{a+1}$ であり, さらに $y,z,w$ を採用できたことから, $w-z=z-y=2^{a}$ であるので矛盾する. よって採用数は高々3つである.
よって, 3つ採用できるか? 2つ採用できるか? を調べられればよい.
上の考察から, 3つ採用する場合, 採用する中で最も小さい値と, その次に小さい値との差を決め打ちすれば3つの値は一意に定まる. また, 差は2冪であるので候補は $O(\log{})$ 個程度であるので, これらを全探索することで3つ採用が可能かを調べられる.
2つ採用の場合も小さい方の値と差の全探索で良い.
https://codeforces.com/contest/988/submission/151207896

E: Divisibility by 25

25の倍数は下2桁が 00,25,50,75 のいずれかであるのでこれを決め打ちして操作回数を求める. 動かすのは出来る限り下の桁が良いのでそうする.
直感的にこの動かし方をすれば最小値では最上位に0が来ることは無いだろうと思っていたがそんなことは無く2ペナ. 実際, 509997みたいな時何も考えないと099975が最適解となるのでこれはマズい.
下2桁を目的の形にする+最上位を0以外にする操作回数を考えればよい.
https://codeforces.com/contest/988/submission/151210654

F: Rain and Umbrellas

傘を2本以上持っているのは明らかに不利である. よって, 状況としては, 傘 $i$ を持っているor傘を何も持っていないの $M+1$ パターンである.
そこで, $DP_{a,m}$ ( $a$ の位置にいて, 傘 $m$ を持っているときの疲労の最小値. 便宜上 $m=M$ とかに傘を持っていない状態を割り当てる) という動的計画法を回せばよい. 傘を持たずに雨の区間に入る遷移では適当に疲労をINFとかにすれば良い.
傘を新たに拾う時, それまでに持っていた傘の情報はいらないので, いずれかの傘を持っているときの疲労の最小値も管理しておくと更新が $O(1)$ で行えるので全体で $O(am)$ になって間に合う.
追記) 傘を拾うタイミングは $m$ 回しかないので遷移を愚直にやっても $O(am+m^{2})$ とかで間に合う気もしないこともないけど試していないから分からない.
https://codeforces.com/contest/988/submission/151209542