AtCoder Regular Contest 059
Updated:
Source codes
Solutions
C - いっしょ / Be Together
Solution #1
$-100 \leq t \leq 100$ の全ての値について、 $t$ に揃えるコストを全探索する。
Solution #2
Let $f \colon \mathbb{R} \to \mathbb{R}$ as follows. \[ f(x) = \sum _ {i \in N} (x _ i - x) ^ 2. \] This is a convex quadratic function. We have the following. \[ f’(x) = \sum _ {i \in N} - 2 (x _ i - x). \] Let $x _ 0 = (\sum _ {i \in N} x _ i) / N$ be its unique root. $f$ attains its minimum when $x = x _ 0$.
Let $n = (\sum _ {i \in N} x _ i) / N$, where the division is $\mathbb{Z}$’s. Since $f$ is a convex quadratic function, $f \colon \mathbb{Z} \to \mathbb{Z}$ attains its minimum at $x = n$ or $x = n + 1$.
D - アンバランス / Unbalanced
Solution
アンバランスな文字数の定義には、過半数が同じ文字と書いてある。ということは、偶数文字数なら隣と同じ文字になっている部分があり、奇数文字数なら、隣と同じ文字になっている部分があるか、または 1 個飛ばしで同じ文字が積み上がっているかである。前者は 2 文字のアンバランスな部分文字列、後者は 3 文字のアンバランスな部分文字列を見つけたことになる。だから最初からこの 2 通りだけチェックしてやればよろしい。
Roughly speaking, if $S + T$ is unbalanced, $S$ or $T$ is unbalanced. This is a key idea to consider the substrings whose length is $2$ or $3$.
E - キャンディーとN人の子供 / Children and Candies
Assume $0$-indexed.
Observation
We would like to compute
\[
A = \sum _ {x _ 0 = A _ 0} ^ {B _ 0} \dots \sum _ {x _ {N - 1} = A _ {N - 1}} ^ {B _ {N - 1}} \sum _ {a _ 0 + \dots + a _ {N - 1} = C} \prod _ {i \in N} x _ i ^ {a _ i}.
\]
Here, $\sum _ {a _ 0 + \dots + a _ {N - 1} = C}$ means that $(a _ 0, \dots, a _ {N - 1}) \in \mathbb{N} ^ N$ runs under the constraint $a _ 0 + \dots + a _ {N - 1} = C$. First, we execute deformation of $A$ as follows.
\[
\begin{align}
A &= \sum _ {a _ 0 + \dots + a _ {N - 1} = C} \sum _ {x _ 0 = A _ 0} ^ {B _ 0} \dots \sum _ {x _ {N - 1} = A _ {N - 1}} ^ {B _ {N - 1}} \prod _ {i \in N} x _ i ^ {a _ i} \
&= \sum _ {a _ 0 + \dots + a _ {N - 1} = C} \prod _ {i \in N} \left( \sum _ {x _ i = A _ i} ^ {B _ i} x _ i ^ {a _ i} \right).
\end{align}
\]
Here, for $i \in N$, let $g _ i \colon \mathbb{N} \to \mathbb{N}$ be defined as follows.
\[
g _ i (a _ i) = \sum _ {x _ i = A _ i} ^ {B _ i} x _ i ^ {a _ i}.
\]
Then, $A$ is computed as follows.
\[
A = \sum _ {a _ 0 + \dots + a _ {N - 1} = C} \prod _ {k \in N} g _ k (a _ k). \tag{E.1}
\]
Let $M = 410$ for the upper bound for $B _ i$’s.
DP for the coefficient
Second, we consider how to compute $g _ i$. Let vector<vector<mint>> $h$ be defined as follows.
\[
h[i][j] = \sum _ {x = 0} ^ {j - 1} x ^ i. \tag{E.2}
\]
Then, it follows that
\[
g _ i (a _ i) = h[a _ i][B _ i + 1] - h[a _ i][A _ i].
\]
What remains is to fill $h$.
Definition
The table $h$ defined as (E.2).
Initial state
$h[i][0] = 0$.
Answer
The table $h$ itself.
Transition
For $i = 0, \dots, C$, this problem is separated for each $i$. For $j = 0, \dots, M - 1$, we execute the following. \[ h[i][j + 1] = h[i][j] + j ^ i. \]
DP for the answer
To compute (E.1), we convert it to DP.
Definition
vector<vector<mint>>$dp[i][j] = $ defined as follows.
\[ dp[i][j] = \sum _ {a _ 0 + \dots + a _ {i - 1} = j} \prod _ {k \in i} g _ k (a _ k). \]
Initial state
$dp[0][0] = 1$; otherwise $0$.
Answer
$A = dp[N][C]$.
Transition
For $i = 1, \dots, N$, for $j = 0, \dots, C$, we consider making $a _ {i - 1}$ be fixed as $l$ with $l$ running $[0, j]$. Then, $a _ 0 + \dots + a _ {i - 2} = j - l$, i.e., we have the following.
\[
\begin{align}
dp[i][j] &= \sum _ {a _ 0 + \dots + a _ {i - 1} = j} \prod _ {k \in i} g _ k (a _ k) \
&= \sum _ {l = 0} ^ j g _ {i - 1} (l) \sum _ {a _ 0 + \dots + a _ {i - 2} = j - l} \prod _ {k \in (i - 1)} g _ k (a _ k) \
&= \sum _ {l = 0} ^ j g _ {i - 1} (l) dp[i - 1][j - l].
\end{align}
\]
Time complexity
For DP for $h$, it takes $O(CM)$-time. For DP for $dp$, each transition takes $O(C)$-time, which result in $O(N C ^ 2)$-time. Hence, the total time complexity is $O(CM + N C ^ 2)$.
Remark #1
We interpret the DP for $dp$ from the viewpoint of polynomial. Let $P _ k (x) \in \mathbb{N}[X]$ for $k \in N$ as follow. \[ P _ k (X) = g _ k (0) + g _ k (1) X + \dots + g _ k (C) X ^ C. \] Then, the answer is the coefficient of $X ^ C$ of $P _ 0(X) P _ 1(X) \dots P _ {N - 1}(X)$.
Remark #2
If $A _ k = B _ k = x _ k$ holds for all $k \in N$, we have the following equation for $i = 1, \dots, N$ and $j = 0, \dots, C - 1$. \[ dp[i][j + 1] = dp[i - 1][j + 1] + x _ {i - 1} dp[i][j]. \] This is because, from $(j + 1)$ candies, we give one candy to $(i - 1)$-th child to obtain the latter term. If we give no candy to $(i - 1)$-th child, it result in the former term.
F - バイナリハック / Unhappy Hacking
Solution
Let $M = \lvert S \rvert$. First, we calculate how many ways of typing that generate a string of the length $M$. This is done by DP argued later. Let $A$ be this value. Then, how many of them generates the string $S$? These $A$ ways generates $2 ^ M$ strings in the same number. Thus the answer is $A / 2 ^ M$.
DP part
Definition
vector<vector<mint>>$dp[i][j] = $ the number of ways to generate strings whose length is $j$ by using $i$ types.
Initial state
$dp[0][0] = 1$; otherwise $0$.
Answer
$dp[N][M] / 2 ^ M$.
Transition
For $i = 0, \dots, N - 1$, for $j = 0, \dots, i$, we execute the followings.
\[
\begin{align}
dp[i + 1][j + 1] &\mathbin{+ =} 2dp[i][j], \
dp[i + 1][\max(0, j - 1)] &\mathbin{+ =} dp[i][j].
\end{align}
\]
Here, the former line represents 0 and 1 key, wheres the latter one does B key.