# AtCoder Regular Contest 059

Updated:

AtCoder Regular Contest 059

# 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$.

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.$

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 = 1$; otherwise $0$.

$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 = 1$; otherwise $0$.

$dp[N][M] / 2 ^ M$.
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.