AtCoder Regular Contest 059

Source codesPermalink

• My submissions (AtCoder)
• My source codes (GitHub)

SolutionsPermalink

C - いっしょ / Be TogetherPermalink

Solution #1Permalink

$-100 \leq t \leq 100$ の全ての値について、 $t$ に揃えるコストを全探索する。

Solution #2Permalink

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 - アンバランス / UnbalancedPermalink

SolutionPermalink

アンバランスな文字数の定義には、過半数が同じ文字と書いてある。ということは、偶数文字数なら隣と同じ文字になっている部分があり、奇数文字数なら、隣と同じ文字になっている部分があるか、または 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 CandiesPermalink

Assume $0$-indexed.

ObservationPermalink

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 coefficientPermalink

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

DefinitionPermalink

The table $h$ defined as (E.2).

Initial statePermalink

$h[i][0] = 0$.

AnswerPermalink

The table $h$ itself.

TransitionPermalink

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 answerPermalink

To compute (E.1), we convert it to DP.

DefinitionPermalink

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 statePermalink

$dp[0][0] = 1$; otherwise $0$.

AnswerPermalink

$A = dp[N][C]$.

TransitionPermalink

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 complexityPermalink

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 #1Permalink

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 #2Permalink

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 HackingPermalink

SolutionPermalink

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 partPermalink

DefinitionPermalink

vector<vector<mint>> $dp[i][j] =$ the number of ways to generate strings whose length is $j$ by using $i$ types.

Initial statePermalink

$dp[0][0] = 1$; otherwise $0$.

AnswerPermalink

$dp[N][M] / 2 ^ M$.

TransitionPermalink

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.

OthersPermalink