AtCoder Beginner Contest 129
Updated:
- Review: 2020-05-18
Source codes
Solutions
A - Airplane
$P + Q + R - \max(P, Q, R)$ を出力する。
B - Balance
$S = \sum W _ i$ とする。 $t _ j = \sum _ {0 \leq i < j}$ とすると、求めるものは以下のもの。 \[ \min _ {0 \leq j \leq N} \left\lvert S - t _ j - t _ j \right\rvert. \]
C - Typical Stairs
$1$-indexed とする。 DP で答えが出る。
DP part
Definition
$ok[i] = i$ 段目へ登れるなら
trueそうでないならfalse,
$DP[i] = i$ 段目への登り方
と定める。
Initial state
初期状態： $DP[0] = 1$, otherwise $DP[i] = 0$.
Answer
答え： $DP[N]$.
Transition
遷移： $i = 0, \dots, N - 1$ に対し、
\[
\begin{align}
DP[i + 1] & \mathbin{ {+} {=} } DP[i] & & \text{ if } ok[i + 1], \\
DP[i + 2] & \mathbin{ {+} {=} } DP[i] & & \text{ if } ok[i + 2].
\end{align}
\]
D - Lamp
$0$-indexed とする。
$X[i][j] = (i, j)$ にライトを置いた時に $x$ 軸方向に照らされるマスの数、
$Y[i][j] = (i, j)$ にライトを置いた時に $y$ 軸方向に照らされるマスの数
と定めると、これらは連続する . の数を数えて $O(HW)$ で記入できる。答えは以下である。
\[
\max_{ (i, j) \in H \times W } \left( X[i][j] + Y[i][j] - 1 \right).
\]
E - Sum Equals Xor
Solution
桁 DP である。 $0$-indexed とする。上の桁からみていく。
DP part
Definition
$DP[0][i] = $ 上から $i$ 桁目未満までみた時に $a + b$ が $L$ と一致している $(a, b)$ の場合の数、
$DP[1][i] = $ 上から $i$ 桁目未満までみた時に $a + b$ が $L$ 未満であることが確定している $(a, b)$ の場合の数
と定める。
Initial state
初期状態： $DP[0][0] = 1$, otherwise $DP[i][j] = 0$.
Answer
答え： $DP[0][N] + DP[1][N]$.
Transition
遷移： $i = 0, 1, \dots, N - 1$ に対し、以下を実行する。
- まず $i$ 桁目未満までで $L$ 未満であると確定している場合は、 $i$ 桁目は $(0, 0)$, $(0, 1)$, $(1, 0)$ のどれも正解である。つまり、 \[ DP[1][i + 1] \mathbin{ {+} {=} } 3DP[1][i]. \]
- 次に $i$ 桁目が $0$ のとき、 $L$ と一致させるのを保つ $(0, 0)$ しかない。それ以外は $L$ より大きいことが確定してしまう。つまり、 \[ DP[0][i + 1] \mathbin{ {+} {=} } DP[0][i]. \]
- 次に $i$ 桁目が $1$ のとき、 $L$ と一致させるのを保つには $(1, 0)$ または $(0, 1)$ である。 $(0, 0)$ にすると $L$ 未満であることが確定する。つまり、
\[
\begin{align}
DP[0][i + 1] &\mathbin{ {+} {=} } 2DP[0][i], \\
DP[1][i + 1] &\mathbin{ {+} {=} } DP[0][i]. \end{align} \]
F - Takahashi’s Basics in Education and Learning
Observation
まず $1$ ステップの遷移が数式でどうかけるか考える。できる数字を $X$ とする。今見ている項を $S$ とする。 $(X, S) \mapsto (X’, S’)$ と遷移するとする。すると、 $S$ の桁数を $k$ とすると、次式が成立する。
\[
\begin{align}
X’ &= 10^k X + S, \\
S’ &= S + B.
\end{align}
\]
これはアフィン変換である。次式に書き直せる。
\[
\begin{pmatrix}
X’ \\ S’ \\ 1
\end{pmatrix} =
\begin{pmatrix}
10^k & 1 & 0 \\
0 & 1 & B \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
X \\ S \\ 1
\end{pmatrix}. \tag{F.1}
\]
よって $1 \leq k \leq 18$ が一定である間 は、行列の累乗の計算で遷移を $O(\log L)$ ですることが可能である。
Solution
(F.1) 式の中央の行列を $M _ k$ とおく。
$f(i) = A + Bi$ の桁数
と定めると、これは狭義単調増加関数であるから、次の値を順次めぐる式二分探索で埋めることができる。 $\delta[0] = 0$, かつ、 \[ \delta[i] = \min \{ \delta[i - 1] \leq x < L \mid f(x) \neq i \}. \] $n _ i = \delta[i] - \delta[i - 1]$ とすると、答えは次式の第 $0$ 成分で求まる。 \[ M _ {18} ^ {n _ {18} } M _ {17} ^ {n _ {17} } \dots M _ {1} ^ {n _ {1} } \begin{pmatrix} 0 \\ A \\ 1 \end{pmatrix}. \]
ポイント
アフィン変換であることに気づけばあとは一直線である。これで mint を導入した。また Matrix ライブラリを書き換えた。