diverta 2019 Programming Contest
Updated:
diverta 2019 Programming Contest
Source codes
Solutions
A - Consecutive Integers
$N - K + 1$ を出力する。
B - RGB Boxes
$Rr + Gg + Bb = N$ を充たす $(r, g, b) \in \mathbb{N}^3$ の組の個数を求める。 $t = N - Rr - Gg$ とおくと、このような $b$ が存在する必要十分条件は $t \geq 0$ かつ $t \% B = 0$ である。 $0 \leq r, g \leq N$ を走査すれば十分なので $O(N^2)$ で求まる。
C - AB Substrings
まずどのように並べても $S _ i$ たち自身に AB が含まれていればそれがカウントされる。まずこれをカウントする。以下ではこれを除外して考える。問題は結合した際に新たに AB が生じるかどうかである。文字列 $S _ i, S _ j$ を結合して新たに AB が生成するための必要十分条件は、 $S _ i[-1] = $ A かつ $S _ j[0] = $ B である。
もう中間が関係ないので、語頭と語末だけ見ればいい。このような文字列がいくつかあるのかカウントするのだが、ここで頭を使う必要がある。問題は 同じ文字列 $S _ i$ と $S _ i$ を結合できない という点である。ここに気がつくと、ひとまず以下の $3$ パターンの個数を分けて持っておくのが良さそうだとわかる。
Bで始まり、Aで終わる文字列の個数 $x$,- それ以外の
Bで始まる文字列の個数 $y$, - それ以外の
Aで終わる文字列の個数 $z$.
すると、 AB 文字列の最大値 $A$ は、以下の数字で抑えられる。
\[
A \leq \min(x + y, x + z). \tag{C.1}
\]
A, B を結合して文字列 AB を作るから、その片方の文字の個数の小さい方は超えることはないという当たり前のことを言っている。
さてこの等号は成立するか？ ほとんどの場合は成立する。まず $x = 0$ の時は間違いなく成立する。 $x > 0$ の時はどうだろうか。まず $x$ 型の文字列を並べると、最初の B と最後の A 以外は無駄なく使い切れていることがわかる。このままだと、最初の B と最後の A は対となる A, B が存在しないので、これが無駄になる。逆に $y, z$ 型の片方が存在すれば、 $x$ 型連続文字列の語頭・語末とまず結合させ、あとは $y, z$ 型を両方結合させることにより、 (C.1) 式の等号は達成される。
以上より、答えは以下のようになる。
\[
A = \begin{cases}
0 & x = y = z = 0, \\
x - 1 & y = z = 0, \\
\min(x + y, x + z) & \text{otherwise}.
\end{cases}
\]
ポイント
例外処理に気がつけば難しくはない。
D - DivRem Number
$m$ が条件を充たすとする。商と余りを $q$ とする。次式が成立する。 \[ N = q m + q = q (m + 1) \] すなわち、 $m$ の候補は $N$ の約数から $1$ を引いたものに限られる。 $N \leq 10^{12}$ であるから、 $N$ の約数は $1 \leq i \leq 10^6$ まで全列挙することで、全部揃えることができる。 $m$ の候補を試して、商と余りが一致するかどうかを試せばいい。
ポイント
こっちの方がよほど簡単だと思った。
E - XOR Partitioning
累積 xor の考察
まず $X[0] = 1$,
\[
X[i] = \bigoplus _ {j = 1} ^ i A _ i
\]
として、累積 xor をとる。 $X[N] = 0$ or $X[N] \neq 0$ で場合分けをするが、 $X[N] = 0$ に後者がほぼ含まれるので、こちらを考察する。分割 $\{ 0 = x _ 0 < x _ 1 < \dots < x _ k = N \}$ が美しいための必要十分条件は、ある $0 \leq K < 2^{20}$ が存在し、
\[
\begin{align}
X[x _ 0] = X[x _ 2] = \dots = X[x _ k] &= 0, \\
X[x _ 1] = X[x _ 3] = \dots = X[x _ {k - 1}] &= K
\end{align}
\]
となることである。 $K = 0$ の場合は、
\[
L = \sharp \{ 1 \leq i \leq N - 1 \mid X[i] = 0 \}
\]
と定めると $2^L$ 通りある。 $K > 0$ の場合は、
$V[K] = \{ X[i] \} _ {i = 0} ^ N$ のうち $0$ と $K$ を取り出して並べたもの(正確な定義は後でする)
と定めると、この情報だけで場合の数が決まる。
Run Length 圧縮
しかしこのままでは $1 \leq K < 2^{20}$ で $V[K]$ の index 自体は持てるが、配列そのものは長すぎて持てない。その理由は、 $0$ が何度も出てくるからである。
そこで $0$ をランレングス圧縮をし、さらに全ての $K$ について $V[K]$ を同時に構築していく ことにする。以下の手順で求める。まず typedef tuple<int, ll> info; とする。 $V[K]$ を vector<info> を初期化する。さらに $zero[K] = 0$ とし $cnt = 0$ とする。 $i = 1, \dots, N - 1$ に対し、以下を実行する。
- $X[i] = 0$ のとき、 $cnt {++}$ とする。
- $X[i] > 0$ のとき、 $K = X[i]$ とする。
- $t = cnt - zero[K] > 0$ ならば、
V[K].push_back(info(0, t));とする。 V[K].push_back(info(K, 1));とする。- $zero[K] \gets cnt$ とする。
- $t = cnt - zero[K] > 0$ ならば、
最後に全ての $1 \leq K < 2^{20}$ に対し上の 1. を実行する。
こうすると $V[K]$ の長さの和は $O(N + K)$ になり、十分高速である。
DP で答えを求める
ここから美しい分割の個数を DP で求める。 $1 \leq K < 2^{20}$ に対し、 int S = V[K].size(); とする。
vector<ll> DP0(S + 1, 0): $DP0[i + 1] = V[i]$ まで見て最後にとった数字が $0$ である場合の数、
vector<ll> DP1(S + 1, 0): $DP1[i + 1] = V[i]$ まで見て最後にとった数字が $K$ である場合の数
と定める。初期状態： $DP0[0] = 1$ 。遷移： $i = 0, \dots, S - 1$ に対し、 int n = get<0>(V[K][i]);, ll s = get<1>(V[K][i]); としたとき、 $n = 0$ ならば
\[
\begin{align}
DP0[i + 1] &= DP0[i] + sDP1[i], \\
DP1[i + 1] &= DP1[i],
\end{align}
\]
$n > 0$ ならば、 $s = 1$ であるから、
\[
\begin{align}
DP0[i + 1] &= DP0[i], \\
DP1[i + 1] &= DP0[i] + DP1[i]
\end{align}
\]
となる。最終結果を $p_K = (DP0[S], DP1[S])$ で返すことにする。
答え：最初の場合わけに戻る。まず $X[N] = 0$ のとき、最後にとるのは $X[N] = 0$ であるから、その手前では $K$ をとっていることになる。つまり以下が答えである。 \[ 2^L + \sum _ {K = 1} ^ {2^{20} - 1} p _ K [1]. \] $X[N] > 0$ のとき、最後にとるのは $K = X[N]$ であるから、 $p _ K [0]$ が答えである。
ポイント
E は放棄して F を考えていたのだが、 E をやった方がよかったかもしれない。