Codeforces Round #624 (Div. 3), Codeforces Round #627 (Div. 3), Codeforces Round #629 (Div. 3) バチャ

Codeforces Round #624 (Div. 3)(2022/4/28)

A: Add Odd or Subtract Even

$a\lt b$ かと $(a-b)\%2$ によって場合分けをする.
必ず2手以内で達成可能.
https://codeforces.com/contest/1311/submission/155118712

B: WeirdSort

ソートできる隣組を連結させていくと, 各連結成分内では自由にソートできる.
よって, $p$ を昇順に並べて置き, 自由にソートできる区間を求め, その区間内を実際にソートするという事を全ての区間に対して行えばよい.
https://codeforces.com/contest/1311/submission/155119403

C: Perform the Combo

各文字まで入力してリセットしたのが何回あるかをカウントしておく.
すると, $i$ 文字目まで入力した時の各文字の出現数と, 各文字までにミスをしたときの文字の入力数を求められるので各文字に対してこれを足し合わせればよい.
https://codeforces.com/contest/1311/submission/155119880

D: Three Integers

$B$ を決め打ちすると, $A,C$ が互いに影響を与え合わせないので考えやすい. (公式解説だとAを決め打ちしているのでそれでも普通にできるらしいが.)
$B$ を決め打ちした後, $A$ は $B$ の約数のうち $a$ に最も近い値を選ぶのが最適である.
これは予め $10^5$ 程度までの数に対して約数を全部並べた配列を用意して置き, この配列の $B$ に対して, $a$ をkeyにlower_bound をすればよい.
$C$ に関しては, $B$ の倍数のうち, $c$ に最も近い値をぶのが最適である.
これは, $\left\lfloor\frac{c}{b}\right\rfloor*b$ , $\left\lceil\frac{c}{b}\right\rceil*b$ のうち, 良い方を選べばよい.
前計算や本計算はどちらも $O(n\log{n})$ である.
$B\gt 10^4$ の場合もあるので注意.( $a=137,b=10000,c=10000$ の場合, $A=137,b=10001,c=10001$ が最適解である.)
https://codeforces.com/contest/1311/submission/155121401

E: Construct the Binary Tree

判定問題までは解けた. 後は上から判定しつつ必要な分だけ子を伸ばしていけば行ける気もするけどムムム......

F: Moving Points

$x_i\lt x_j$ なる2点に対しての $d(i,j)$ を考える.

$v_i\gt v_j$ ならば, どこかのタイミングで2点が重なるので $d(i,j)=0$
$v_i\ge v_j$ ならば, 2点の距離は縮まらないので $d(i,j)=x_{j}-x_{i}$

である.
よって, 速さの具体的な値は解に影響せず, 他の点の速さとの大小関係のみ保持しておけばよいので速さを座圧できる.
すると, 始点の座標の小さい方から順に, 自身より座標が小さくかつ速さが自身以下であるものすべてに対して上記場合分けの2個目の方を足し合わせていけばよく, 区間和のセグメント木によって実現できる.
https://codeforces.com/contest/1311/submission/155122940

総括

68分ABCDF5完1ペナ145位. Eみたいな構築問題苦手......

Codeforces Round #627 (Div. 3)(2022/4/28)

A: Yet Another Tetris Problem

テトリスの配置で2の倍数の差は埋めることができる.
初期状態において全てのテトリスの偶奇が一致していることが必要十分条件.
https://codeforces.com/contest/1324/submission/155190492

B: Yet Another Palindrome Problem

全ての長さ3以上の回文は部分文字列に長さ3の回文を含んでいる.
よって, 長さ3の回文が存在するか判定すればよく, 特に長さ3の回文は1文字目と3文字目が等しいという条件のみからなるため, 同じ文字で間に1文字以上存在しているものがあるかを確かめればよい.
https://codeforces.com/contest/1324/submission/155190629

C: Frog Jumps

Lのマスに止まってはいけない場合の問題でも答えが元の問題と同じであることに気づけるかが本質.
Lのマスに止まった場合, それより左にあるRのマスを踏まないと右に進めず, つまりはそのLのマスにはそもそも止まる必要がないという事が全てのLマスに対して言える.
Rマスのみに止まる問題の場合は, 全てのRマスに順番に止まるようにするとジャンプ力の必要値の最小値を達成できる.
https://codeforces.com/contest/1324/submission/155190833

D: Pair of Topics

$c_{i}:=a_{i}-b_{i}$ とすると, $i\lt j,\ c_{i}+c_{j}\gt 0$ となる $(i,j)$ のペアを数えればよい.
これは, $c_{i}+c_{j}\gt 0$ を満たすペア $(i,j)$ の数から $a_{i}>0$ なる $i$ の数を引いた値の半分に等しい.
$a_{i}>0$ なる $i$ の数は簡単に $O(n)$ で求まる.
$c_{i}+c_{j}\gt 0$ を満たすペア $(i,j)$ の数は, $i$ を固定した場合, $c_{j}\gt -c_{i}$ なる $j$ の数を数えればよいので, あらかじめ $c$ を昇順にソートしておいてupper_bound によって高速に数えることができる.
https://codeforces.com/contest/1324/submission/155191700

E: Sleeping Schedule

$i$ 回目の睡眠を終え, 現在 $j$ 時である時の良い眠り回数の最大値を DP $\lbrack i\rbrack\lbrack j\rbrack$ としてこれを更新していく.
DP $\lbrack i\rbrack\lbrack j\rbrack$ からは DP $\lbrack i+1\rbrack\lbrack (j+a_{i})\%h\rbrack$ , DP $\lbrack i+1\rbrack\lbrack (j+a_{i}-1)\%h\rbrack$ へ更新すればよい.
https://codeforces.com/contest/1324/submission/155192194

F: Maximum White Subtree

全方位木DP感がとてもあり実際全方位木DPで解ける.
まず0を根として, 各頂点の部分木でのスコアの最大値を葉から順に計算していき, その後根を動かしながら解を求めていけばよい.
https://codeforces.com/contest/1324/submission/155193298

総括

45分全完2ペナ71位. 全方位木DPを書くのにも若干慣れた気がする.

Codeforces Round #629 (Div. 3)(2022/4/28)

A: Divisibility Problem

$b$ の倍数のうち, $a$ 以上の最小の値をとる最適である.
これは, $\left\lfloor\frac{a}{b}\right\rfloor*b$ , $\left\lceil\frac{a}{b}\right\rceil*b$ あたりの値になって場合分けが面倒くさかったのでどっちも試して良い方を答えとした.
https://codeforces.com/contest/1328/submission/155203097

B: K-th Beautiful String

1つ目のbが $i$ 番目より前にある文字列が何個あるかは計算で求めることができる.
よって, 1つ目のbが何番目に来るかをこれによって求めて, 2文字目で残りを調整するように全探索する.
https://codeforces.com/contest/1328/submission/155203523

C: Ternary XOR

$a,b$ を $a\ge b$ という追加の制約を定めて, $a$ の最小化を目指せばよい.
上の桁から決めていく.
$x$ の今見ている桁が

0の場合, $a,b$ ともにその桁を0とすればよい.
1の場合, 現状で $a=b$ なら $a$ に1を, $b$ に0を充てる. $a\gt b$ なら $a$ に0を, $b$ に1を充てる.
2の場合, 現状で $a=b$ なら $a$ に1を, $b$ に1を充てる. $a\gt b$ なら $a$ に0を, $b$ に2を充てる.

https://codeforces.com/contest/1328/submission/155204050

D: Carousel

どんな入力に対しても, $1,2,1,2,\dots, 3$ という風に1と2を交互に繰り返して最後のみ3にしたものは条件を満たすので答えの上界は3.
よって後は答えが1,2になるそれぞれの場合を求めればよい.
答えが1になるのは明らかに全ての種類が同じ時でありその時に限るので以下そうでない場合で答えが2になる条件を探す. 長さが偶数の時は $1,2,1,2,\dots,1,2$ とすると条件を満たす.
長さが奇数の時, もし隣り合う2要素で同じ種類が並ぶ場所があれば, そのうちの1か所のみ隣合う2つに同じ色を割り振って残りを交互に塗っていけばよい.
上のいずれにも属さない場合どう頑張っても3色必要な事は明らか.
https://codeforces.com/contest/1328/submission/155206436

E: Tree Queries

達成可能の場合に, 根からの深さが最も深い場所をパスの端点にするのが良いというのは直感的にも分かる.
よって, このように答え候補のパスを決めた後それが条件を満たすかの判定問題を解く.
まず愚直にパス上の頂点を列挙して, クエリで与えられる点と距離1以下の点があるかを判定するという方法を考えてみる.
この時, 以下の2つが原因で計算量がヤバイことになる.

全クエリで, 与えられる頂点と距離1以下の頂点の数の総和が最大で $n\sum k$ になる場合がある.
全クエリでのパスの長さの総和が最大で $mn$ になる場合がある.

まず1つ目を解決する方法を考える.
重要な事はパスの一方の端点が根であることである.
これのおかげで, クエリで与えられる頂点に対して, その頂点の子がパス上にあるならば自身もパス上に必ず存在してくれる.
よって, 子がパス上に存在するかは判定する必要が無く, 自身と親の少なくとも一方が存在するかを判定するだけで良くなる.
これにより, 1つ目のパートでみるべき頂点数は $\sum k$ に抑えられる.

2つ目を解決する.
1つ目の解決により, 見るべき頂点数は $\sum k$ であるので, これ以外の頂点はどれがパス上に有ろうと関係ない.
よって, パスの余分なところを見るのを省きたい.
そこでLCA(最小共通祖先)を用いる.
クエリで与えられている頂点のうち深い頂点から順に見ていく.
現在見ている頂点を $x$ , 次に自身か親がパス上に存在するか判定したい頂点を $y$ としたとき, $y$ か親がパス上に存在する必要十分条件は $y,x$ のLCAが $y$ か $y$ の親になる場合である.
初めに前計算としてLCA計算の準備をしておけば, 各LCAを $O(\log{n})$ で求められるので, 問題全体の計算量が $O(\log{n}\sum k)$ で抑えられる. https://codeforces.com/contest/1328/submission/155208967

F: Make k Equal

数列は昇順にソートされているものとする.
[tex; k] 個以上用意する値 $x$ を決めうちした時, それより小さい値達を $x$ に近づけていくか, 大きい値達を $x$ に近づけていくか, 両方をするかの3パターンが考えられる.
小さい値達を $x$ に近づけていく場合ができれば反対側も同じ感じででき, それらを合わせると両側verもできるので小さい方verを考える.

明らかに, 目標値 $x$ はもともと数列にあった値のいずれかにするのが最適である.
また, $x\lt y$ の時に, $y$ に近づけていく過程で, 数列の最小値が $x$ に揃う瞬間が訪れる.
よって, 目標値の昇順に計算をしていくことができる. 数列が $x,x,x,\dots,x,x,y,\dots$ という状況の時を考える. ([tex; x] の個数を $p$ とする.) この時, 最小値を $y$ にするためには, $(y-x)* p$ 回の操作が必要であるので,各値の個数を管理しながら計算を行う事ができる.

小さい値達を $x$ に近づけていき, $x$ が $k$ 個になった時, 数列は $x-1,x-1,\dots,x-1,x,x,x,\dots,x,x,hoge\dots$ のようになる場合があるため, 端数の余計な操作をしないようにも注意する.
https://codeforces.com/contest/1328/submission/155210814

総括

1時間32分全完4ペナ171位. Eで計算量計算をミスって $O(nk)$ になってしまっていた解法を実装ミスだと思ってコードいじって出してペナしてを数回繰り返してしまったのでダメだった.

仮のブログ

仮です