Codeforces Round #560 (Div. 3), Codeforces Round #565 (Div. 3), Codeforces Round #570 (Div. 3) バチャ

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

A: Remainder

下 $x$ 桁のみを見ればよい. 目的の数とのbitの不一致を数える.
https://codeforces.com/contest/1165/submission/152671148

B: Polycarp Training

$i$ 日目に $i$ 問以上のセットが残っているかを判定し, 残っているなら問題数の最も少ないセットを使う.
https://codeforces.com/contest/1165/submission/152671407

C: Good String

前から使える文字を順番に使っていけばよい.
https://codeforces.com/contest/1165/submission/152672079

D: Almost All Divisors

素因数が一種類の場合, $p^{k}$ の形にかけ, 特に $p^{n+1}$ でないといけないので判定問題を解けばよい.
そうでない場合, 元の数は数列の項の最小公倍数となる.
その最小公倍数約数の個数が $N+2$ 個であり, 数列の項に自身を含まないことが必要十分である.
https://codeforces.com/contest/1165/submission/152673645

E: Two Arrays and Sum of Functions

全てを足し合わせた時, $\displaystyle\sum_{i=0}^{n-1}(i+1)*(n-i)*a_{i}*b_{i}$ である.(添え字は0index にずらしてある.)
よって, $a_{i} \leftarrow (i+1)*(n-i)*a_{i}$ としたときに, $\displaystyle\sum_{i=0}^{n-1}a_{i}*b_{i}$ を最小化すればよく, これは片方を昇順に, もう一方を降順に並べた時が良い.
https://codeforces.com/contest/1165/submission/152673996

F1: Microtransactions (easy version)

F2と同じことをした.

F2: Microtransactions (hard version)

答えで二分探索をする.
$D$ 日以内に全てを買えるかの判定問題を考える.
まず, $D$ 日の期間内にセール日がある商品は, 期間内最後のセール日に買うのが最適である.
また, 買うべき個数に不足している場合はこの最後のセール日に変えるだけ買ってしまってよい.
このもとで全て買えるか否かを判定すればよい.
上記の正当性は, お金は出来るだけ後まで残しておいた方が選択肢の幅が狭まらないこと, 後半は買う商品の個数が一定なら, 使うお金の総額はセールで何個買うかのみに依存することからわかる. https://codeforces.com/contest/1165/submission/152676186

総括

57分全完3ペナ37位. 順調に解けたので楽しく感じた.

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

A: Divide it!

操作2を行うと追加で操作1を一回行えるので, 操作2を2回分の操作を纏めて行って, $n$ を $\frac{n}{3}$ に置き換えると思ってよい.
操作3も同様に言えるので, これにより, $n$ が2,3,5で何回割り切れるかを求めればよい.
https://codeforces.com/contest/1176/submission/152723953

B: Merge it!

元々3の倍数の項は何もしなくて良く, 余りが1と2の項をペアにしていく. 残った者たちで, 余りが同じもの3つ組を1まとめにすれば最適.
https://codeforces.com/contest/1176/submission/152724088

C: Lose it!

数列から 4,8,15,16,23,42 という部分列をできるだけ多く取り出すことを目標にする.
これは, できるだけ前からとっていけばよく, setのlowerbound を使えばよい.
余談だがこの数列はLostという映画だかに登場する数らしい.
実装時には数字が飛んでいるとただ面倒くさくなるだけだったので42だけを24に置き換えて, $\div 4-1$ をした. これで並びが0,1,2,3,4,5 となって実装しやすい.
https://codeforces.com/contest/1176/submission/152724507

D: Recover it!

$b$ の項で最大の数に注目する.
これが素数の場合, この値は, ある $a_{i}$ が存在して, $p_{a_{i}}$ として得られた数である. 各素数が何番目の素数かを前計算しておけば, この $a_{i}$ は定数時間で求まる.
素数でない場合, ある $a_{i}$ が存在して, $a_{i}=b$ であり, ある $b_{j}$ が存在して, $b$ の自身でない最大の約数が $b_{i}$ である. 各自然数について, その数を割り切る最小の素因数をエラトステネスの篩で前計算しておけば, $b_{i}$ は定数時間で求まる.
従って, 最大の数に注目すると, いずれの場合でも, 元の数列 $a$ に登場する数と新規で追加された数を1つずつ特定できる.
よって, この操作をまだ特定していない最大の数に対して行う事を $n$ 回繰り返せば全ての項を分類できる.
https://codeforces.com/contest/1176/submission/152725328

E: Cover it!

問題文がどんなグラフに対しても解が存在することを言っているので, グラフから全域木を取り出して考えても良い.
すると, 根を適当に決めた時に, 葉から順に頂点として選ばないといけないか否かを決定することができる. ここで選ぶ必要のある頂点は明らかに $\frac{n}{2}$ 個以下で, 元のグラフに対しても条件を満たす.
https://codeforces.com/contest/1176/submission/152726084

F: Destroy it!

各ターンで出されるカードの構成は, コストに注目したとき, "1", "2", "3", "1,1", "1,2", "1,1,1" の6パターンしかない. また, 出すコストの組を決めれば, 出すカードはそのコスト内で高ダメージの物から順に選ぶのが良い.
よって, DP[n][c] でnターン終了時に出したカードの枚数 $\pmod {10}$ がcである時のダメージ最大値という動的計画法を各状態間を高々6回の遷移で行える.
得点2倍の処理も, 出すカードのうちどのコストのカードを2倍にするか全て試せばよい. "1,2" の組の出し方以外, ダメージ2倍にすべきカードは一意なので実装も大変ではない.
https://codeforces.com/contest/1176/submission/152728833

総括

1時間15分全完4ペナ55位. Fが面白い. 無駄なペナがあったのは減点.

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

A: Nearest Interesting Number

1の位が0~4まで動けばその間に必ず良い数が現れるので, 適当にwhile文を良い数が現れるまで回すという方針で良い.
https://codeforces.com/contest/1183/submission/152733416

B: Equalize Prices

答えの上限は, 数列の最小値+ $k$ である. また, 良い $B$ が選べるならば, 数列の最小値+ $k$ も良い $B$ とできることも容易に分かる.
よって, この値が適切かを判定すればよい.
https://codeforces.com/contest/1183/submission/152733644

C: Computer Game

二分探索で答えを求める.
$d$ 日を最初のタイプでプレイできるための必要十分条件は, $ad+b(n-d)\le k$ であるのでこれで判定すればよい.
この一次不等式を解けばそのまま答えも出せた気がするが制約的に間に合うのでどちらでもよし.
https://codeforces.com/contest/1183/submission/152733968

D: Candy Box (easy version)

飴の個数が多い種類物から順に, 現在入れれる数の最大値を入れていけばよい.
ある種類の飴を処理した後, 次に入れれる飴の最大値はたった今入れた数-1である.
https://codeforces.com/contest/1183/submission/152734649

E: Subsequences (easy version)

Hと同じ

F: Topforces Strikes Back

めちゃくちゃ面白い問題だと思う.
サンプルの2個目のケースが本質をついている.
考察の上で大事な観察は, 約数は自身と比べてかなり小さい数になるという事である.
数列内に表れる最大値を $M$ とする.
$M$ を選ぶか選ばないかどちらが最適かを考える.
まず選ばない場合を考える.
この時の最適解において, 選ばれる数を $a,b,c$ とする.
$a,b,c$ のうち, $M$ の約数が存在しない時, $a$ を $M$ に置き換える方が明らかに総和は大きくなる.
$M$ の約数が1つのみ存在する場合, それを $M$ に置き換えるとこれまた明らかに総和が大きくなる.
$M$ の約数を2つ含むとき, $M$ の約数を $a,b$ とすると, $a+b\le \frac{M}{2}+\frac{M}{3}=\frac{5}{6}M\lt M$ より, $c,M$ という選び方をした方が総和は大きくなる.
$M$ の約数を3つ含むとき, $\lbrace a,b,c\rbrace=\lbrace\frac{M}{2},\frac{M}{3},\frac{M}{5}\rbrace$ の時は, これらの総和は $\frac{M}{2}+\frac{M}{3}+\frac{M}{5}=\frac{31}{30}M$ である. そうでないときは, $a+b+c\le \frac{M}{3}+\frac{M}{4}+\frac{M}{5}=\frac{47}{60}M\lt M$ であるので, 全て消して $M$ だけ選んだ方が総和が大きくなる.
以上より, $M$ を選ばない場合で, 総和が $M$ より大きくなりうるのは $\lbrace a,b,c\rbrace=\lbrace\frac{M}{2},\frac{M}{3},\frac{M}{5}\rbrace$ の場合に限られることが分かった.

次に $M$ を採用する場合を考える. この時, $M$ の約数を選ぶことはできないので, $M$ の約数を全て消したのち, 残りの2つを選ぶことを考えればよい. 残った数で最大の数を $L$ とする. この時, 先ほどと同様に考えると, $\frac{L}{2}+\frac{L}{3}\le \frac{5}{6}L\lt L$ であるので, 今度は $L$ を採用するのが最適である.
残りの一つは $M,L$ の約数でないもので最大の数 $T$ を選べばよい.
以上より, 最大となりうる候補を絞れたので, 候補となった1つ( $M+L+T$ )か2つ( $M+L+T, \frac{31}{30}M$ )の大きい方を選べばよい.
途中で3つ選べなくなる場合もあるのでそれはよしなに.
https://codeforces.com/contest/1183/submission/152738631

G: Candy Box (hard version)

1種類あたり $k$ 個以上の飴が入ったセットを作れるかを $k$ の大きい方から貪欲に作っていく.
作れる条件は, その時点でまだ用いていない飴で, $k$ 個以上あるものが存在することである.
そのうえで, 1 である飴の数を最大化するには, $k$ 個以上ある飴のうち, 1である飴の数が最大の物を選べばよい.
以上を実装するには, 優先度付きキューを用意して, 各 $k$ を見るごとに, 丁度 $k$ 個飴があるものの, 1である飴の個数をキューに追加, その後, キューが空でなければ, 1である飴の数が最大の物を取り出して, ギフトにその飴を組み込むという事を繰り返していけばよい.
https://codeforces.com/contest/1183/submission/152735720

H: Subsequences (hard version)

部分列DPに, 部分列の長さを持たせればよい. 部分列DPに関しては調べた方が分かりやすい情報が見つかると思う.
これをすると長さ毎にできる部分列の個数が得られるので, 長さの大きいものから $k$ 個を採用して, 全体で $k$ 個に満たなければ-1を出力すればよい.
オーバーフローしないように, 各長さ $k$ 個を超えそうになったら $k$ 個で統一するなどの処理が必要.
https://codeforces.com/contest/1183/submission/152737199

総括

1時間12分全完0ペナ19位. とても良い. 繰り返しになるがFが面白い.

仮のブログ

仮です