AtCoder Regular Contest 059

Updated:

AtCoder Regular Contest 059

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.

Others