Codeforces Round #498 (Div. 3), Codeforces Round #501 (Div. 3), Codeforces Round #506 (Div. 3) バチャ

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

A: Adjacent Replacements

偶数なら-1, 奇数ならそのまま.
https://codeforces.com/contest/1006/submission/151294155

B: Polycarp's Practice

難易度の高い方からK個をK日に分割するのが最適. 難易度の高いK個のindexを求めて, それらを丁度1つ含むように毎日の解く問題数を決める.
https://codeforces.com/contest/1006/submission/151294435

C: Three Parts of the Array

前からの累積和と後ろからの累積和を求めて, 値が等しいかつindexの和がNを超えないもので最大値を取ればよい.
https://codeforces.com/contest/1006/submission/151294601

D: Two Strings Swaps

aのi文字目とN+1-i文字目, bのi文字目とN+1-i文字目の4つを同時に見ていく. これらの文字の組み合わせによってこの中だと何文字変える必要があるかは場合分けをすれば求めることができる. 場合分けが面倒くさければ文字を変える/変えないを全て試すのも良いと思う.
https://codeforces.com/contest/1006/submission/151294939

E: Military Problem

DFSをして, 部下が何人いるかと行きがけ順を求めておく. 各人が行きがけ順の何番目に表れるかを求めておく. 各クエリでは部下の人数以下の値であるかを判定した後, 行きがけ順の何番目を出力するかを求めて配列から値を取り出せばよい.
https://codeforces.com/contest/1006/submission/151296522

F: Xor-Paths

${}_{20}C_{10}$ が丁度良いサイズというのを知っておくと便利かもしれない.
全ての経路を試すと ${}_{40}C_{20}$ 通りもありメモリも時間も間に合わないが, 経路の中間地点までを全て試すのは片側からで ${}_{20}C_{10}$ 通りで, 両側からでもこの2倍なので間に合う.
スタートかた中間までの経路で, XORが $k$ となるのが何通りあるかをunordered_map 等で管理しておくと, もう片側から見た時に, XORが $K\oplus k$ となるのが何通りあるか求まり, これらを足し合わせればよい.
実装によっては中間点を2重にXORとってしまったり, $N=1$ や $M=1$ の時に壊れたりするので注意. 自分は後者をやってしまった.
https://codeforces.com/contest/1006/submission/151296659

総括

53分全完2ペナ 30位. Dをスムーズに解きたかった. それ以外は及第点.

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

A: Points in Segments

制約が大きくなったらimos法だが, 今回は制約が小さいので愚直に各区間を更新していって間に合う.
https://codeforces.com/contest/1015/submission/151308701

B: Obtaining the String

文字数に対してswap回数の猶予が多いので愚直に1文字ずつ合わせていけばよい. 実装が楽な方針で行こうとしたらうまくいかなかったのでこの方法をとった.
https://codeforces.com/contest/1015/submission/151308999

C: Songs Compression

圧縮量の大きい物から貪欲に圧縮していけばよい. 全部圧縮してなお容量以上あれば不可能, そうでなければ入った時点での記録を出力すればよい.
https://codeforces.com/contest/1015/submission/151309457

D: Walking Between Houses

いろいろ方針がありそうで迷った.
自分は, まずYESorNOを判定し, その後構築という流れにした.
判定パートでは一回の移動で移動できる距離が $1$ 以上 $N-1$ 以下であることから, $K\le S\le K(N-1)$ かを判定をすればよい.
その後の構築パートでは, 最大の移動をできる時は最大の移動をする. できないときは一回帳尻合わせを挟んで, 残りは一個隣に移動を繰り返す. という流れを取った.
各移動をしたら残りの移動回数, 移動距離はどれだけかが分かるので, それが上記の判定基準から漏れないようにすればよい.
https://codeforces.com/contest/1015/submission/151310688

E1: Stars Drawing (Easy Edition)

E2と同じ

E2: Stars Drawing (Hard Edition)

基本的な流れは, 各マスを中心とした星を置けるならば, 置けるもののうち最大の星を置き, 全部の*マスを埋め尽くせるかを最後に判定.
まず各マスにどれだけの大きさの星を置けるか(あるいは置けないか)を求めるのは, 上下左右方向からみて, *が何個連続しているかチェックすればよい.
例えば, 右方向に見ていくときは, ".****.***." となっている部分は, 0012340123 となる. これを4方向から行い, それらの最小値が, そのマスにおける星のサイズの最大値となる.
次に実際に星を置いた時にどのマスを*とできるかを求める. これも4方向から行えばマス目サイズのオーダーで計算できる.
イメージとして星の大きさ=明るさと置き換えてみると想像しやすいような気がする.
最後に, これで*となったマスと, 与えられたものが完全に一致するかを判定すればよい.
類題: ABC018C ひし形カウント https://atcoder.jp/contests/abc018/tasks/abc018_3

https://codeforces.com/contest/1015/submission/151312434

F: Bracket Substring

難しかった.
初めに取った方針は, Sが含まれる位置を全探索というもので, これは実装後に, Sが複数含まれる場合が考慮出来ていないことに気が付いた.
次に, Sの出現回数を記録しながらよくある括弧列のDPをして, 最後に包除原理のようなことをするという方針を取ったが, これも N=4, S="()()()" みたいな時に "()()()()" を重複してカウントしてしまうためマズかった.
結局正解の方針は, DP[n][i][k]: 前からn文字見て, 括弧列の累積和がiで, 末尾k文字がSの前方k文字と一致しているものの数というのを考えればよかった.
前計算として, 末尾k文字がSの前方k文字と一致している時に1文字追加したら末尾の何文字がSの先頭と一致するかというのを求めておく. これは特別なアルゴリズムは特に要らず全て試すので十分間に合う.
この前計算をすると各遷移が $O(1)$ で状態数が [tex: O(N³)] の間に合うDPが出来上がる.
$k=|S|$ からの遷移を $k=|S|$ に行くようにしておくと, 求める答えは DP[N][0][|S|] となる.
https://codeforces.com/contest/1015/submission/151317669

総括

1時間40分全完5ペナ50位. 後半神経を使う問題が連続していて難しく感じた.

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

A: Many Equal Substrings

div3-Aにしてはかなり難しいと思う. $k=2$ の場合に二つの文字列のうちどれだけをかぶらせられるかを愚直に求めれば, そこから $k$ を1増やしたときに文字をどれだけ追加すればよいかが分かるので, 残りはまとめて計算できる.
https://codeforces.com/contest/1029/submission/151332932

B: Creating the Contest

コンテストは連続した区間の問題を採用するのが最適である. ( $a\lt b\lt c$ という難易度の問題があって, $a,c$ を採用した場合, $b$ を採用すると得しかない).
また, 隣接した問題でその両方ともをは採用できないのは, 難易度比が2倍以上となる時のみである.
よって, 隣接難易度比が2倍以下の区間の長さの最大値を求めればよい.
https://codeforces.com/contest/1029/submission/151333232

C: Maximal Intersection

全ての区間に含まれる範囲は, $\lbrack \max_{1\le i\le N}{L_i},\min_{1\le i\le N}{R_i} \rbrack$ である. これをベースに一つの区間を除いた時にどうなるかを考える.
例えば $k$ 番目の区間を除いた時, 共通部分の左端は, $\max(\max_{1\le i\lt k}{L_i},\max_{k\lt i\le N}{L_i})$ となる. (右端も同様)
よって, 両側から $L,R$ の累積max, 累積min を前計算しておくことで, 各区間1つだけ取り除いた時の残りの共通部分を $O(1)$ で求められる.
https://codeforces.com/contest/1029/submission/151334121

D: Concatenated Multiples

二つの数 $x,y$ を結合した時, $y$ の桁数を $d$ とすると, $x\times 10^{d}+y$ となる. 桁数の取りうる値は少ないので, それらすべてに対して, $a_{i}^{d}\pmod k$ の値を計算しておく.
すると, 各 $a_{i}$ を下側の桁として他の数と結合した時に, その値が $k$ の倍数となるものの個数を高速に求めることができる. 自身を2つつなげた時に $k$ の倍数となる場合の数え過ぎに注意.
https://codeforces.com/contest/1029/submission/151335110

E: Tree with Small Distances

やりたいこととしては木上でDPをして, 葉側からどうしても道をつなげなければならない時だけ付けるという事をしようとした. しかし, 根付近での挙動を上手くできず通せなかった.

F: Multicolored Markers

赤と青のどちらを長方形とするかを両方試す.
赤を長方形とする場合, 赤長方形の縦の長さ $d$ は $a$ の約数であるのでこれを全て試す.
全体の縦の長さは $a+b$ の約数であるのでこれも全て試す.
$10^9$ 程度の大きさの数の約数の個数は最大でも1500弱であるので, これの2乗の計算回数でも間に合う.
自分は直感的に間に合わないと思い, 正方形に一番近くなるようにしてそこをバグらせてしまった. 大人しく計算量解析をして, 上記の全てを試す方法にしたところすぐ通った.
https://codeforces.com/contest/1029/submission/151338152

総括

1時間ABCDF5完5ペナ87位. Eは落ち着けば解けそう. Fのペナはもったいない.

仮のブログ

仮です