Codeforces Round #550 (Div. 3), Codeforces Round #552 (Div. 3), Codeforces Round #555 (Div. 3) バチャ

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

A: Diverse Strings

各文字列を昇順にソートして, 隣り合う文字が全て連続した文字かを判定すればよい.
https://codeforces.com/contest/1144/submission/152572810

B: Parity Alternated Deletions

偶数と奇数で, 多くある方から大きい数から消していけばよい.
愚直に回してもソートして余るものだけを足し合わせても良い.
https://codeforces.com/contest/1144/submission/152573031

C: Two Shuffled Sequences

増加数列を貪欲にとっていき, 残りを減少数列にできるか判定をする.
https://codeforces.com/contest/1144/submission/152573358

D: Equalize Them All

1回の操作で変化のある数は高々1個であるので, 答えの下限は, 数列の個数-数列の最頻値の個数である.
逆に, 全ての値をもとの数列の最頻値に揃えようとすると, 隣り合う数字の片方のみが最頻値であるところのもう片方を最頻値に置き換える操作を繰り返すことで, 実際にこの下限で操作を終えることができる.
https://codeforces.com/contest/1144/submission/152574263

E: Median String

文字のままだと考えにくいので, 26進数の数と思って計算した.
2つの数の和を取る時は下の桁から繰り上がりを持ちつつ計算していき, その半分の値を求めたいときは, 上の桁から端数が出たら下の桁に回していけばよい.
https://codeforces.com/contest/1144/submission/152576179

F: Graph Without Long Directed Paths

YES/NOはグラフが二部グラフであるか否かを判定すればよい.
構築では, 二部グラフの片方を辺が入るのみにし, もう片方を出るのみにすればよい.
判定部分の証明は雑であるが, 十分条件は構築ができることから言え, 必要性はある頂点に辺が入ってきたら, その頂点には辺が入るのみでないといけない(逆も然り) ことから, 各辺は入るのみの頂点と出るのみの頂点を結ばないといけないことから言える.
https://codeforces.com/contest/1144/submission/152576789

G: Two Merged Sequences

数列を前から順に増加数列か減少数列に振り分けて, 増加数列の最後の項を $a_{i}$ にしたときの減少数列の最後の項として取りうる最大値を遅延セグメント木で管理することを考えたが, 実装が上手くいかなかったので投げ出した.
この考察のまま詰めれるかは不明. 解きなおし時にもう一度考える.

総括

49分A~F6完2ペナ73位. DEに時間を掛けすぎたかなという印象. Fは早かった.

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

A: Restoring Three Numbers

4つの数の最大値が, 3つの総和であり, 残りは2つの和である. 元の数を求めるには, 3つの総和-2つの和をすればよい.
https://codeforces.com/contest/1154/submission/152592961

B: Make Them Equal

値 $D$ の候補は, 数列の最大値-最小値またはその半分である.
それぞれで全て等しくできるかを見ていけばよい.
自分は最小のものを出力というところを見落としていた.
https://codeforces.com/contest/1154/submission/152593389

C: Gourmet Cat

周期性のあるものを処理するときは1周期分の変化を計算しておくのが定石のように思う. 今回も何週間+何日と分けるとよい.
1週間で, 魚3回, 兎2回, 鶏2回食事があるので, ここから何週間食材を持たせられるかが分かる.
この分を減らした残りの食材で後何日をしのげるかは, 端数の開始曜日を全探索して, 愚直に食材を消費してみて足りなくなるタイミングを探せばよい.
https://codeforces.com/contest/1154/submission/152593973

D: Walking Robot

日が出ていてかつ蓄電池に容量があればバッテリーを, そうでなければ蓄電池を消費するのが最適.
https://codeforces.com/contest/1154/submission/152594435

E: Two Teams

残っている人で最大値のindexを求めて, そこから残っている人のうち最大値の人に近い人を選出していく.
最大値のindexは, 値からindexを得る配列を事前に用意しておけばプログラム全体で $O(n)$ でできる.
残っている人のうち近い人を選出するときは, 残っている人をsetに持っておいて二分探索をすれば各選出を $O(\log{n})$ でできるので, 全ての選出にかかるのは $O(n\log{n})$ である. よって間に合う.
https://codeforces.com/contest/1154/submission/152595688

F: Shovels Shop

まず, 値段の低い $k$ 個の商品のみを考えればよい.
商品を $i\ (0\le i\le k)$ 個買う時の出費の最小値を DP[i] として配列にする. これを, DP[i] への遷移は商品の値段の累積和を前計算しておけば各オファーを使う時の遷移を $O(1)$ で行える. 実装の際には, $m+1$ 個めオファーとして, $(x,y)=(1,0)$ を入れておくと, オファーを使う/使わないを分けなくて良いので楽.
ループの順番に気を付けないといけないことを失念していてペナをしてしまった.
https://codeforces.com/contest/1154/submission/152600139

G: Minimum Possible LCM

まず部分問題として, 「 $a$ の中から $g$ の倍数であるものを2つ選んで, それらの積 $\div g$ の値を最小化せよ」
という問題を考える.
これは, $g,2g,\dots$ の値がそれぞれいくつあるかを求めればよい.
この問題ができれば, 後は全ての $g$ に対してこの問題の答えの最小値を求めればよい.
計算量は, $a$ の最大値を $M$ として, いつもの調和級数になるので, $M\log{M}$ である. 自分は探索を終えた $g$ はすぐにループを抜けるというのをサボったらTLEしたのでTLは結構ギリギリかもしれない.
https://codeforces.com/contest/1154/submission/152599273

総括

1時間32分全完8ペナ54位. G問題が面白かった.

Codeforces Round #555 (Div. 3)(222/4/4)

A: Reachable Numbers

操作10回で桁が1つ落ちるので, 異なる数の出現数は $\log$ で抑えられる. 愚直にシミュレーションすればよい.
https://codeforces.com/contest/1157/submission/152633525

B: Long Number

辞書順最小なので, できるだけ上の桁を大きくする. 上の桁から見ていき, 大きくできるなら大きくする. できないなら次の桁を見ていく.
一度ある桁に変更を加えたならば, 連続する区間のどこまでを変更するかを見ればよい.
https://codeforces.com/contest/1157/submission/152633763

C1: Increasing Subsequence (easy version)

数列の前後で小さい方の数からとっていけばよい.
https://codeforces.com/contest/1157/submission/152634579

C2: Increasing Subsequence (hard version)

数列の先頭と末尾が同じ値であった場合, そこから先は片方側からのみしか取り出せなくなる. よって, 各項について, 右方向, 左方向にそれぞれどれだけ単調増加列が続くかを前計算して大きい方を採用すればよい.
一部評価が狭義でなく広義を採用してしまっていてそれに気が使ずバチャ中に通せなかった.
https://codeforces.com/contest/1157/submission/152639776 (バチャ後)

D: N Problems During K Days

他の問題に時間を取られてあまり考えていない.

E: Minimum Array

これも前から小さくしていけばよい.
ある項を小さくしたければ, まだ使われていない $b$ の項で, $(a_{i}+b_{i})\pmod n$ を最小にすればよく, これはまだ使われていない $b$ の項をmutisetに入れておけばlowerboundで高速に求まる.
https://codeforces.com/contest/1157/submission/152636277

F: Maximum Balanced Circle

上手く並べると, 円を最小値の場所で切って数列とすると, 単調増加列と単調減少列をくっつけたものにできる.
そして, 両端の差が1以下になる事から, 最大値と最小値は1回以上現れ, それ以外は2回以上(単調増加列中と単調減少列中に少なくとも1つずつ)現れる事が分かる.
逆にこの条件を満たすとき, 条件を満たせる.
よって, 各数の出現回数を見た時, 2回以上出現するものの両端に1回出現するものをくっつけた区間で, 要素数が最大の物を探せばよい.
https://codeforces.com/contest/1157/submission/152637514

G: Inverse of Rows and Columns

操作の1/0を全て反転させると元に戻るため, 1行目に対しては操作をしなくても良い. 1行目の1/0の並びはどこまでが0でどこからが1かの $m+1$ 通りある. これを全て試す.
1行目の並びを決定したら, 1行目は操作しないことから, 各列の操作を行うか行わないかを求めることができる.
各列の操作が決定すれば, 2~ $n$ 行目に対して操作を決めた時に条件を満たせるかを調べる.
それより前の行で1が出現していたらその行の数を全て1にするしかなく, そうでなければ0を前に詰める. 計算量は $O(nm^2)$ である.
https://codeforces.com/contest/1157/submission/152641016

総括

1時間55分ABC1EFG6完8ペナ343位. C2Dが解けないのはうーん. それ以外にもペナが多かった. Gが解けたのでかろうじて良いところもあったといった感じ.

仮のブログ

仮です