Codeforces Round #490 (Div. 3), Codeforces Round #494 (Div. 3), Codeforces Round #496 (Div. 3) バチャ

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

A: Mishka and Contest

両端から解けるなら解く, 解けないなら止まる.
https://codeforces.com/contest/999/submission/151242032

B: Reversing Encryption

操作の逆順で操作を行う. すなわち小さい順にみていき, 約数なら反転する.
https://codeforces.com/contest/999/submission/151242382

C: Alphabetic Removals

各文字の出現場所をみていき, a,b,c...の順に, これまでに消した数が $K$ 個未満なら消す, そうでなければ残すをする.
初めちょっと方針に迷った.
https://codeforces.com/contest/999/submission/151242909

D: Equalize the Remainders

数列を前から見ていき, その数の剰余が既に $\frac{n}{m}$ 個あったらまだ足りないところまで+1, そうでなければそのまま.
まだ足りないところはsetで管理しておくと, lowerbound で各値の操作が $O(\log{m})$ で行えるので全体で $O(n\log{m})$ .
https://codeforces.com/contest/999/submission/151243700

E: Reachability from the Capital

まず首都から辿れる街を記録しておく. 次にグラフを強連結成分分解し, 親から順に, 首都から辿れなければその街に道をつなげるという事をする.
強連結成分分解済みなので, 余分な道をつなげる恐れはなくなり, 新たに道をつないだ時に辿れる街の更新はBFSなどで行えば各街は1回ずつしかチェックしなくて済むので間に合う. sccはACLの中身を切り取って使った. https://codeforces.com/contest/999/submission/151245200

F: Cards and Joy

各好みの数字 $t$ 毎に最大何点取れるかをDPで求める. DP[i][j] は i人にカードを分けて, 計j枚配った時の得点の最大値を持たせる. $t$ 全てに対してこれを行うと(多分)間に合わないが, ~~各数を好む人数が同じならDPテーブルは同じになるので使いまわせる.~~
好む人数が違ってもDPテーブルの途中までに必要な情報は残っているのでこんな面倒くさいことをしなくて良い.
これにバチャ後に気が付いたのでコードを書きなおした. かなりすっきり書けたと思う.
コンテスト中 https://codeforces.com/contest/999/submission/151248881
後から https://codeforces.com/contest/999/submission/151252431

総括

1時間10分全完6ペナ97位 Eまで調子が良かっただけにもったいない感あるが時間内に修正出来て全て解けたのでまあよし.

Codeforces Round #494 (Div. 3)(2022/3/29)

A: Polycarp's Pockets

map で各数の出現回数を管理してその最大値が答え.
https://codeforces.com/contest/1003/submission/151255078

B: Binary String Constructing

基本的には01でXの値を稼いで残りを左右にくっつけて調整. 01で稼ぐときに片方の文字を使い果たす場合の実装が抜けておりかなり苦労した.
https://codeforces.com/contest/1003/submission/151259534

C: Intense Heat

初め丁度長さ $K$ でないといけないと誤読していた.
制約が小さめなので区間の長さを全探索すればよい. 制約が大きくなったら答えで二分探索で判定部分はRmQのセグメント木とかでできそう.
https://codeforces.com/contest/1003/submission/151256299

D: Coins and Queries

コインの種類数が $O(\log)$ 種類しかないかつ, より高額のコインに代替できる場所はして損はしないため, 額の大きいコインからある分だけ使えばよい.
https://codeforces.com/contest/1003/submission/151256757

E: Tree Constructing

以下の手順で(存在するならば)木を構成できる.

頂点 $D+1$ からなるパスを作る.
パス上の頂点に対し, 直径の制約と次数の制約からその頂点から部分木を生やせるか, 生やせるならどれだけの深さにしてよいかが求まる.
各頂点にどれだけゆとりがあるかを管理してゆとりのあるものに頂点をくっつける→くっつけた頂点のゆとりを2のように求める.
これを $N$ 頂点くっつくまで繰り返す.

1が出来なかったり, 4にたどり着くまでに3で選べる頂点が無くなったら構成不可能である.
ゆとりのある頂点はキューに突っ込んでおいて3の時はそこから取り出せばよい.
https://codeforces.com/contest/1003/submission/151258996

F: Abbreviation

基本的には全ての $1\le j\le i\le N$ に対して, $w(j,i)$ を省略した時の長さを求めてそれらの最小値を取ればよい.
$w(j,i)$ を省略した時の長さを求めるには全体の中から $w(j,i)$ と等しいものがどこに表れるか分かれば良く, KMP法を用いれば $O(N)$ でできるので全体で $O(N^{3})$ となる.
何となく文字列のままだと計算量が悪い気がして文字列を番号付けして整数列として管理した. これの効果のほどは分からない.
https://codeforces.com/contest/1003/submission/151262247

総括

83分全完5ペナ 48位. ペナが多かった. BやEのように何かの境界付近で落ちるケースが多かったので境界がサンプルに含まれていないときは気を付けたい. Eが面白かった.

Codeforces Round #496 (Div. 3)(2022/3/29)

A: Tanya and Stairways

直前に言った数以下の数を言った時が次の階段に移行したタイミングなのでそこをみる. 他にも1の出現場所をみるなどの方法も良さそう.
https://codeforces.com/contest/1005/submission/151287929

B: Delete from the Left

2つの文字列で末尾が一致している長さを考えればよい. (例えば west と test なら, 合わせて8文字あり, 後ろ3文字estはいじる必要がないので, いじる必要があるのは $8-3\times 2=2$ 文字. )
https://codeforces.com/contest/1005/submission/151288052

C: Summarize to the Power of Two

各 $a_{i}$ に対して, 和が2冪となるペアが存在するかは, $2^{0}-a_{i},\ 2^{1}-a_{i},\ 2^{2}-a_{i},\dots$ が存在するかをmultisetなどで判定すればよい. 自分自身とペアを組まないようにするのに注意する.
https://codeforces.com/contest/1005/submission/151288202

D: Polycarp and Div 3

後ろから数を貪欲に切っていく. 数が3の倍数⇔数の各位の数の和が3の倍数であることを考えると, 下の桁から, 各位の数をmod 3の累積和で取っていき, 同じ値が登場するたびに, 1個3の倍数となる区切りができる.
https://codeforces.com/contest/1005/submission/151288376

E1: Median on Segments (Permutations Edition)

E2と同じコードを出したため略

E2: Median on Segments (General Case Edition)

Atcoderの「Median of Medians (https://atcoder.jp/contests/arc101/tasks/arc101_b)」を考えたばっかりだったので一瞬で方針が立った.
直接中央値が $m$ のペアを数えるのが難しいので, 中央値が $m$ 以下のペアの数 - 中央値が $m-1$ 以下のペアの数を数える.
数列の中央値が $m$ 以下⇔ その数列中に $m$ 以下の値が $\left\lceil \frac{len}{2}\right\rceil$ 個以上存在 ⇔ 数列中の各要素を, $m$ 以下なら+1, 未満なら-1 に置き換えた時, 要素の総和が0以上
と条件を言い換えることができる.
よって, 置き換え後の数列の累積和 $S_{0},\ S_{1},\dots,\ S_{n}$ をとっておき, $S_{l}\le S_{r}$ を満たす $0\le l\lt r\le n$ の数を数え上げれば良く, fenwicktreeなどの区間和取得, 1点更新が高速に出来るデータ構造を用いればよい.
https://codeforces.com/contest/1005/submission/151288642

F: Berland and the Shortest Paths

まず $d_{1}+\dots+d_{n}$ の最小値を達成する条件を考える. 例えば首都から出ている道を用いないのは明らかに不利である. 色々考えると, 元のグラフと道を構成し直したグラフで, 全ての頂点の首都からの最短距離が等しくなることが必要十分であることが分かる. (題意の主張より明らかだった...)
よってまず首都から各頂点の最短距離 $dist_{1},\dots,dist_{n}$ を求める.
次に, 最短距離が変わらない道の選び方をしなければならないが, 最短経路を求めるアルゴリズムを考えると, 頂点 $u$ と繋いで良い道は $u$ と $dist$ の値が丁度1異なる頂点とをつなぐ道であることが分かる. これを踏まえると, 首都以外の各頂点について, 自身から伸びている道のうち, $dist$ が自分のものより1小さい頂点とをつなぐもののうち丁度1本選ぶというのを行っていけばよい.
こうしてできた木は最短距離を保っており, また, 1か所でも違う選択をしたものは木として異なる構造をしている.
よって上記のことをDFSなどで行っていけばよい. K通り完成した時点で打ちとめ, 最後まで探索をしてもK個そろわなければ構成不可である.
https://codeforces.com/contest/1005/submission/151289155

総括

46分全完1ペナ6位. E2の考察部分をほぼすっ飛ばせたのは大きいが, その他の問題もかなりスピーディに解けた.

仮のブログ

仮です