【Codeforces】Educational Codeforces Round 127

E まで。

E の計算量解析できないの危機感を感じる。

コンテストのリンク

A

ランレングス圧縮して各要素について個数が 2 個以上か確かめる。

提出コード

B

$x_0$ をどうするかで最終的な数列は 3 通りできる。

それぞれにできるかどうかは絶対値の差がすべて 1 以下であるかで判定可能。

提出コード

C

$i$ を取る個数とし、 $f(i)$ を $i$ 個以上取れる日数とすると、求めるものは $\displaystyle \sum_{i=1}^{n} f(i)$ である。（若干見方を変えている。）

取る個数を決めたら安い順に貪欲に取るべきなのでソートする。

$s (\leq x)$ を小さいほうから $i$ 個取るときの初期コストとすると、 $f(i) = \dfrac{x-s}{i} + 1$ である。

提出コード

D

$a$ に要素を挿入しても答えが小さくなることはないので、下限として $\displaystyle \sum_{i=1}^{n-1} | a_i - a_{i+1} |$ が得られる。

$\min \{ a \}$ 以上 $\max \{ a \}$ 以下の要素は適当に挿入できる。

$1$ 以上 $\min \{ a \} - 1$ 以下の要素と、 $\max \{ a \} + 1$ 以上 $x$ 以下の要素については、 $1$ と $x$ について、それぞれ先頭に入れるか、要素間に入れるか、末尾に入れるかを考えれば良い。（それ以外の要素は適当に途中に挿入できる。）

提出コードのように $1$ と $x$ を完全に独立に考えると、要素間に入れる場合は良いとして、 $1$ と $x$ をどちらも先頭に入れたりどちらも末尾に入れたりする場合にコストを過小評価していそうだが、冷静に考えるとこのような場合は起こらないことが分かるので、OK。（一方を先頭に、もう一方を末尾に入れても損をしない。）

提出コード

E

$g(i)$ を $i$ を根としたときの部分木に対する作れる文字列の種類数とし、子から順に木 DP で求める。

$g(l_x)$ と $g(r_x)$ から $g(x)$ を求める方法だが、もし $g(l_x)$ と $g(r_x)$ で同じものがカウントされていない場合、 $g(x) = 2 \times g(l_x) \times g(r_x)$ である。

同じものがカウントされている場合についてよく考えると、 $l_x$ を根とする部分木と、 $r_x$ を根とする部分木に対して行える操作は変わらないので、実は同じものがカウントされているというか、数えているものが完全に同じ。

よって $g(x) = g(l_x) \times g(r_x)$ である。（スワップの意味がなくなるので。）

同じかの判定は、作れるものの中で辞書順最小のものが同じかで判定すれば良くて、問題は辞書順最小のものをどうやって持つか……と考えていたのだが、

よく考えると各頂点を根とする部分木について、作れるものの中で辞書順最小のものをすべて陽に持っても MLE しない。

証明

頂点が $0$ から $2^n - 2$ だとして、頂点 $0$ を深さ $0$ とする。

深さ $i$ の頂点数は $2^i$ で、各頂点に対する辞書順最小の文字列の長さは $2^{n-i} - 1$ なので、文字列の総長は $\displaystyle \sum_{i=0}^{n-1} \left ( 2^{n-i} - 1 \right ) 2 ^{i} = n 2^n - 2^n + 1$

となる。（証明終わり）

比較は文字列長のオーダーでできるので、 $O(n 2^n)$ で通る。

提出コード (ACL を使用)