Codeforces Round #515 (Div. 3), Codeforces Round #521 (Div. 3), Codeforces Round #527 (Div. 3) バチャ

Codeforces Round #515 (Div. 3)(2022/3/30)

A: Vova and Train

丁寧に計算をする. 地味に切り上げ, 切捨て辺りが自分の計算と怖かったのでセルフテストケースを試してから出した.
https://codeforces.com/contest/1066/submission/151379014

B: Heaters

端からiまでの位置をみて, 温まっていない区間がj個ある時に付けるヒーターの数の最小値をDP[i][j]として動的計画法をする.
温まっていない箇所が出来てしまう条件や端だけちょっと例外処理的な事をしないときない実装をしてしまったので結構ペなった.
https://codeforces.com/contest/1066/submission/151379402

C: Books Queries

mapで本のidと座標を管理して置き, 変数で本の座標の左端と右端を管理する.
挿入クエリでは左端/右端の座標から次に追加する本の座標が分かり, 左端/右端を1ずらせばよい.
出力クエリでは, 本の座標と左端/右端の情報から, 左右それぞれから本を取り出すとき何冊取り出せばよいかが計算できるので, 小さい方を出力.
https://codeforces.com/contest/1066/submission/151379666

D: Boxes Packing

右から詰めれる $M$ 箱で詰めれる分だけ詰めて, 詰め切れなかった分を捨てる時に最大値を達成できる.
証明は順番を指定されて物を詰める時に貪欲に詰めれるだけ詰めるのが最適であることを踏まえると簡単で, 左端からの最適な貪欲で $a$ 個詰めれる⇔ $a$ 個詰めれる⇔ 右端からの最適な貪欲で $a$ 個詰めれるとなるので, 左右から貪欲にやって数が不一致することは無い.
https://codeforces.com/contest/1066/submission/151379873

E: Binary Numbers AND Sum

寄与ゲー.
$b$ をずらして全体の& を足し合わせるのでは無く, 全体を通してみた時に $2^k$ が何回足されるかを考える.
まず, $a$ の $k$ 番目のbitが立っていないときは明らかに寄与は0である.
そうでないときは, $b$ の $k$ より上位のbitで立っているものの数だけの寄与がある.
よって累積和的に, $b$ のある桁より上のbitがいくつ立っているかを求めて寄与を計算してそれを足し合わせればよい.
https://codeforces.com/contest/1066/submission/151380172

F: Yet another 2D Walking

説明上各ポイントの右左を $(INF,INF)$ を向いている時の右左とする. (単にこの説明上の話なので特に気にしなくて良い)
同じレベルのポイントに行くときは端から端まで行くのが最適である. よって, 各レベルのポイントを全て巡った時にそれぞれの端にいる時の移動回数の最小回数を順次計算していけばよい.
遷移は, 右/左端から右/左端の移動の4通りを計算すればよく, 各端の座標を持っておけば, 移動距離も計算できる.
レベルは最大で $2*10^9$ となるので配列として持つのではなく変数として持っておくと良い. (あるいは連想配列でやっても良いが過去のデータを保持しておくことに意味はない).
Atcoder に類題があった気がするが思い出せない. https://codeforces.com/contest/1066/submission/151380907

総括

52分全完3ペナ30位. Bで3ペナもしたのがもったいない. 後半3問をペナなくスピーディに解けたのはとても良かった.

Codeforces Round #521 (Div. 3)(2022/3/30)

A: Frog Jumping

$(a-b)$ の移動を $\lfloor\frac{k}{2} \rfloor$ 回と $a$ の移動を $k%2$ 回行う. https://codeforces.com/contest/1077/submission/151406045

B: Disturbed People

番号の若い人から見ていき, 眠れない人がいたら次の人の電気を消してもらう.
https://codeforces.com/contest/1077/submission/151406181

C: Good Array

他の要素の総和となりえるのは数列の最大値のみである. よって, 数列から各要素を抜いた時, 残りが良い列となるかを確認するためには, 各要素を抜いた後の最大値, 総和が分かれば良い.
ここで最大値となりうる値は, 元の数列の最大値か2番目に大きい値であるのでそれのみを管理しておけばよい.
https://codeforces.com/contest/1077/submission/151406500

D: Cutting Out

まず二分探索で, 最大何個のコピーを作れるかを探す.
$mid$ 個のコピーを作れるかを判定するには, 各値が $mid$ 個のコピーを作る際に何個の要素をねん出できるかを計算して, その総和が $k$ 以上か否かを見ればよい.
コピー数の最大数が分かれば, 後は同様に, 要素を何個捻出できるかを見ていけばよい.
https://codeforces.com/contest/1077/submission/151407044

E: Thematic Contests

コンテストの日数は高々40日くらいである. よって, 初日のコンテストの問題数を全て試して, 何日開けるかを確かめるという方針で良い.
初日の問題数 $k$ を決め打ちしたら $d$ 日目には $k*2^{d-1}$ 問の問題を出すので, まだ出していないタイプかつ $k*2^{d-1}$ 問以上あるものから, 問題数の最も少ないものを探せばよい.
私は lower_bound をした.
https://codeforces.com/contest/1077/submission/151408594

F1: Pictures with Kittens (easy version)

最後に採用したのがn枚目で, 合わせてx枚の写真を撮った時の満足度の最大値をもつ.
更新は合わせてx-1枚とっていて, 最後に採用したのが n-K+1枚目からn-1枚目であるものの最大値を取得できれば良いので, セグメント木を配列で持った.
F2も同じコードを出したが, MLEした.
恐らく想定解は, DP[n][k][x]: n枚目まで見て, 最後に採用したのがk枚前で, x枚採用済みという動的計画法である.
https://codeforces.com/contest/1077/submission/151410298

F2: Pictures with Kittens (hard version)

範囲の両端が単調増加の区間最大値なのでスライド最大値でやればメモリと時間計算量を節約できる.
https://codeforces.com/contest/1077/submission/151413162

総括

1時間20分全完4ペナ43位. F2のMLEを小手先で解消しようとしてペナを重ねてしまった. スライド最大値の発想は普段頭の引き出しに入っていないので使いこなしていきたい.

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

A: Uniform String

abc....kabc....k...を繰り返せばよい.
https://codeforces.com/contest/1092/submission/151435185

B: Teams Forming

スキルの昇順に並べて隣り合う二人をペアにしていけばよい.
https://codeforces.com/contest/1092/submission/151435295

C: Prefixes and Suffixes

細かいところを詰める前にお気持ちで実装して通った.
長さがN-1の文字列が2つあるので接頭辞と接尾辞のどちらがどちらに対応するかを決めると元の文字列が復元できる.
そこで, 残りの文字列に接尾辞, 接頭辞を対応できるかを判定した.
https://codeforces.com/contest/1092/submission/151436516

D1: Great Vova Wall (Version 1)

$\pmod 2$ の違いを無視できるので01文字列に変換できる.
その後は, 括弧列を対応させるようなのりでstackにpush&popをすればよい.
初めは偶奇偶奇...の時のみ不可だと思っていてそれを投げたが当然WA.
https://codeforces.com/contest/1092/submission/151440672

D2: Great Vova Wall (Version 2)

今度も同様にstackにpush&popしていく. 自分は複数種類の括弧がある括弧列をイメージして考察した.
この時, 内側の括弧の方が値が大きい場合, 後から整合性を取れないのでこの時点でNO.
最後まで帳尻合わせができた場合, stackに何も残らないor最大値の要素のみが残るかのいずれかである.
https://codeforces.com/contest/1092/submission/151441208

E: Minimal Diameter Forest

まず各木に対して, 直径と中心を調べる.
木同士をマージするときは中心同士をくっつければよく, 中心をくっつけた時に新たにできる木の直径は計算で求まり, 中心は元の中心となる.
https://codeforces.com/contest/1092/submission/151440156

F: Tree with Maximum Cost

全方位木DPの良い練習問題となると思う.
全方位木DPの典型を抑えていればその通りに全頂点を中心としたときのスコアを求めることは容易だと思う.
https://codeforces.com/contest/1092/submission/151441208

総括

1時間20分全完4ペナ13位. 実装量の割にはかなり早く解けたと思う.

仮のブログ

仮です