Codeforces Round #624 Div3 - tinumu's reminder

問題たち

A

場合分けするだけ
同じだったら0, 答えが1にならない方は2になる

B

$P_{i-1}+1=P_i$ みたいなところを連続な区間と呼ぶとすると、連続な区間の中で昇順ソートすればいい
これで昇順になってなかったらNOだよね,ほかはYES

C

それぞれの段階で何回どのボタンを押したかはわかるので前計算する
$P_i$ で押し直していくので、 $P_i$ の段階のボタンを押す回数を答えに追加していけばいい
最後は最後まで行くので $N$ の段階のところを追加する
文字なので、配列を256個用意して楽にやろうとしたらMLEしてきれちゃった
ケチって26個だけにしようね

D

全部うまく見る for文のやりかたを工夫する
BやCは10000より大きくなるかもしれないので気をつけよう(30000くらいまでで良さそう)

E

木がリストになっている時、最大の数になっていることがわかる。
また、木が平衡している(この表現で良いのか)時は最小の数になることがわかる。
これがわかると、この範囲外は"NO"と出力できる。

実は、範囲内に入っていれば全て "YES" になる。
木の葉の数はリストになるまで、 $1$ より大きい。
$2$ 番目に深い位置にある葉を $u$ としよう。 $u$ の深さを $depth[u]$ と呼ぶことにする。
$1$ 番目に深い位置にある葉を $v$ とするとき、 $v$ そのものか、 $1$ から $v$ のパスにある頂点 $w$ について $depth[w] = depth[u]$ かつ子の数が $1$ 以下であるものが存在する。
頂点 $u$ の親を $w$ にしてあげると、総和が $1$ だけ増えるので、これをリストになるまで続ける。
実際に構成すればこの問題は解ける。

実装楽しい

F

要素 $i,j (i < j)$ について、
$x_i < x_j$ かつ $v_i > v_j$ ならば、 $i, j$ にかかるコストが $0$ になる。
そこで、 $x_i$ を昇順ソートすると、条件は $v_i > v_j$ のみになる。

速度が小さいほうから処理して、その部分のコストを消していけば、
大きい物は小さい物のコストを含めないように出来る。

$i$ より右にあるもののコストは、
条件を満たす $j$ についての $x_j$ を全て足して、 $x_i \times 条件を満たす j の数$ を引けば、 $i$ について求まる。
そのようなコストの総和や、条件を満たすものの数は、更新とクエリが早い BITやSegment Tree を使うと、 $O(\log N)$ で答えを求められるので、全体の計算量は $O(N \log N)$ となる。

感想

char型を添え字にするときに配列を[256]とかにしない！(素振り)
Eが解けたのは少し面白かった
Fは解きたいね、ABCの全完とかに必要そう