Codeforces Round #540 (Div. 3), Codeforces Round #544 (Div. 3), Codeforces Round #547 (Div. 3) バチャ

Codeforces Round #540 (Div. 3)(2022/4/3)

A: Water Buying

1リットルボトルをできるだけ買うか2リットルボトルをできるだけ買うかのどちらかが最適.
https://codeforces.com/contest/1118/submission/152503428

B: Tanya and Candies

偶奇ごとに累積和を取っておくと, 1つ取り除いた時の偶数日, 奇数日に食べる飴の個数を定数時間で求めることができる.
https://codeforces.com/contest/1118/submission/152503691

C: Palindromic Matrix

数の種類ごとに個数を管理して, 奇数個の数, ２の倍数個ある数等をメモっておく.
回文行列において, どこが同じ数になるかは分かるので, 過不足なくこれらが当てはまるかを確かめる.
実装があらぶりまくってペナを重ねた. 反省.
Atcoderにも類題がある. C - Palindromic Matrix

https://codeforces.com/contest/1118/submission/152505472

D1: Coffee and Coursework (Easy version)

D2と同じ.

D2: Coffee and Coursework (Hard Version)

答えで二分探索して判定問題を考えるという典型パターン.
$mid$ 日で終えられるかという判定問題は,

各日に飲む本数は同じくらいの方が良い.
各日に飲むドリンクの集合が決まったら, それを効果の大きい順に飲むとしてよい.

といったあたりから考察を始めた.
前者は一日あたりに飲む本数が最大の時の一番最後に飲むものを別の日飲むことにしても損をしないことから, 後者はその日に得られる効果の総和が(ドリンクの効果の総和)-(一日に飲む本数のみから決まる値) とい式に直せることから従う. 厳密には, 順番によって, $\max(0,hoge)$ の部分の挙動が変わるが, これは後でどうにかする.
以上の考察から, 効果の大きい飲み物から順に, 1日目,2日目, ... , $mid$ 日目, 1日目, 2日目, ... と割り振っていくのが良い.
そして各日に実際に飲んでいき, 効果が正になるところまではのみ, 残りを放っておけばよい.
先ほどの $\max(0,hoge)$ の挙動が変わる問題はここで効果が0になるところを切り捨てられることから解答を得る上で問題にならないことが分かる.
これで, $mid$ 日で最大どれだけの進捗が産めるかが求まったので, この値と目標値の大小をもって判定とすればよい.
https://codeforces.com/contest/1118/submission/152506465

E: Yet Another Ball Problem

構築発想ゲー? 自分は $b$ を $1,2,\dots, k,1,2,\dots$ とし, $g$ を $b_{1}+1, b_{2}+1,\dots, b_{k}+1, b_{k+1}+2,b_{k+2}+2, \dots$ とする発想がスッと降りて来たのでそれを実装.
一個ずつ考察を詰めて構築するにはどうするのだろうか.
組めるペアの数の上限が $k(k-1)$ なのでそのあたりから, 上手くずらしながら列挙することを考えるとこんな感じにはなると思う.
https://codeforces.com/contest/1118/submission/152506874

F1: Tree Cutting (Easy Version)

木DPで辺の両側の頂点に赤と青頂点がそれぞれどれくらい求めていけばよい. 木DPの典型.
https://codeforces.com/contest/1118/submission/152507754

F2: Tree Cutting (Hard Version)

解けなかった. $k$ 色で $k$ 分割なので, 同じ色は同じ連結成分に含めなければいけなくて, そうすると, 答えが正になる時は色付きの連結頂点集合 $k$ 個と無色頂点のグラフになるのでここから木DPをするからもう少しいったところまで考察を進めたが, 作業量が多く終えられなかった.

総括

1時間A~F1の7完5ペナ92位. F2が解けなかったのはある程度仕方がないとして, Cの5ペナが痛かった. 類題がぱっと思いつく程度には見覚えのある問題なので, ペナなしで解けるべきだった.

Codeforces Round #544 (Div. 3)(2022/4/2)

A: Middle of the Contest

時刻を文字列で受け取って分に直して平均をとって, 時刻表示に戻す.
https://codeforces.com/contest/1133/submission/152476064

B: Preparation for International Women's Day

題意を理解するのに苦労した. 各 $k$ の剰余に対して, 組にしたときに余りがゼロになるのが何個あるかをmapで管理する.
https://codeforces.com/contest/1133/submission/152476677

C: Balanced Team

各選手をチーム内レート最小値としたとき, 最大で何人がそのチームに入れるかを尺とりや二分探索で求める.
自分は二分探索でやった.
https://codeforces.com/contest/1133/submission/152476996

D: Zero Quantity Maximization

$a=0$ の時, $c=b$ でこの値は $d$ に依らない.
それ以外の時, $c=d\cdot{} a+b=0\Leftrightarrow d=-\frac{b}{a}$ であるので, この分数をmap等でもって数をカウントすればよい. その際, 分母分子の定数倍によって異なる分数としてカウントされないように, gcdで分母分子を割って既約分数にして, 分母を正に揃えておく必要がある.
https://codeforces.com/contest/1133/submission/152477404

E: K Balanced Teams

レートの昇順に選手を並べて置き, 各人をチーム内最小レートとした場合に何番の人までを同じチームに含められるかを表す値 $T_{i}$ をC問題のように前計算しておく.
$DP\lbrack i\rbrack\lbrack k\rbrack$ : 前から $i$ 人までチームを決定して, $k$ チーム出来ているときの最大人数という動的計画法をする.
更新は,
$DP\lbrack i\rbrack\lbrack k\rbrack$ から $DP\lbrack i+1\rbrack\lbrack k\rbrack$ (選手 $i$ をチームに含めない)
$DP\lbrack i\rbrack\lbrack k\rbrack$ から $DP\lbrack T\lbrack i \rbrack \rbrack\lbrack k\rbrack$ (選手 $i$ をチームに含める)
とできる.
https://codeforces.com/contest/1133/submission/152479917

F1: Spanning Tree with Maximum Degree

次数最大の頂点から伸びている辺を全て採用した後, 残りの辺から全域木になるようにいくつか選べばよい.
https://codeforces.com/contest/1133/submission/152480328

F2: Spanning Tree with One Fixed Degree

頂点1の次数を $d$ ,頂点1が存在しないときのグラフの連結成分の個数を $g'$ とすると, まずYES/NOの判定は. $d\le D\le g'$ かどうかで判定できる.
構築時には, 1と結ばれる辺のうち, 残りの辺数の猶予的に全ての連結成分を結べるなら採用して良く, そうでなければ採用しないとして, まず頂点1周りの処理を終えた後, 後は自由に残りの頂点間の辺を結んでいけばよい.
https://codeforces.com/contest/1133/submission/152482182

総括

1時間14分全完4ペナ89位. EでDPの考察詰めが上手くいかず, 再帰的に解こうとしたのが間違いだった. 時間もペナもとられてしまった.

Codeforces Round #547 (Div. 3)(2022/4/3)

A: Game 23

$\frac{m}{n}$ が整数で2と3のみを素因数に持つならば指数の和が答えでそうでないなら-1が答え.
https://codeforces.com/contest/1141/submission/152535095

B: Maximal Continuous Rest

境界ごちゃごちゃが面倒くさいので配列を2つ繋げると実装が楽.
https://codeforces.com/contest/1141/submission/152535153

C: Polycarp Restores Permutation

初項を仮に決めると, 残りの項の値が決まり, その最小値が1に対応しないといけないことから, ここから真の初項が決まる.
初項が決まってしまえばあとは実際に列を構成して, 順列となっているか判定すればよい.
https://codeforces.com/contest/1141/submission/152535280

D: Colored Boots

まず?以外のブーツでペアを組めるならそこでペアを組んでしまってよい.
次は, ?と?以外でペアを組んでいく.
最後に余った?同士でペアを組む.
文字種ごとにブーツの数を管理すればよい.
実装にはいろいろな方針がありそう.
https://codeforces.com/contest/1141/submission/152535652

E: Superhero Battle

まず1ラウンドでの様子を見る.
1ラウンド目の途中でHPが0になるならそれを出せばよく, そうでなくて1ラウンド目の最後に最初よりHPが増えていた場合は永遠に倒すことができない.
それ以外の時はいつかは倒せる.
1ラウンドでのHPの減少量を $S$ とすると, 各ラウンド内で一番体力が低い瞬間の体力は $S$ ずつ減っていくので, これが0になる直前までのラウンド数を計算して, 残りは再びシミュレーションすればよい.
ラウンドの最初/最後だけを見た時には体力が0になってないが, 実は途中で0になる瞬間があって戦闘が終わってましたというパターンに注意.
例えば, 10 3
-7 4 2
みたいな時に, 1ラウンドで体力が1減るので, 10ラウンド近くかかるように見えるが, 3ラウンド終了時のHPが7で, 4ラウンド目の最初の攻撃でHPは0になるのでそこで終了である.
https://codeforces.com/contest/1141/submission/152535878

F1: Same Sum Blocks (Easy)

F2と同じ.

F2: Same Sum Blocks (Hard)

ブロックの値の総和を決め打ちする. これは, ブロックの一つの左右のindexを決め打ちすることを考えれば, 高々 $O(n^2)$ 通りの値を考えればよいことが分かる.
決め打ち後に何個ブロックを作れるかを考える.
事前に, 累積和から, 区間の総和の値毎に区間を分けておく.
すると, これは区間スケジューリング問題となるので区間の数を $d$ として $O(d\log{d})$ で解ける. 区間の数は全体で $n^2$ 個なのでこれで間に合う.
https://codeforces.com/contest/1141/submission/152536273

G: Privatization of Roads in Treeland

まず二分探索でいくつの会社を用意しないといけないかを探す. これは, 会社の数より多いの次数を持つこと⇔最適な会社訳分けにおいて不公平な頂点となるであるので, 会社の数より多い次数を持つ頂点と $k$ の大小を比較すればよい.
会社の数が決まれば, 不公平な頂点がどこかも決まるので, 後は辺に会社を割り振っていく.
どうせ不公平になる頂点は, その頂点から出る全ての辺を1つの会社に任せるのが最適である.
そうでない頂点には, まだ使われていない会社から順に割り振っていけばよい.
もしかしたら不公平になる頂点も順に会社を割り振っていってもうまくいく気もしている.
https://codeforces.com/contest/1141/submission/152537027

総括

55分全完0ペナ9位. とても良い. やはりペナなしは大きい. F2問題が面白かった.

仮のブログ

仮です