AtCoder Beginner Contest 129

更新日時:

AtCoder Beginner Contest 129

ソースコード

解法のメモ

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 で答えが出る。

$ok[i] = i$ 段目へ登れるなら true そうでないなら false,
$DP[i] = i$ 段目への登り方

と定める。初期状態: $DP[0] = 1$, otherwise $DP[i] = 0$. 答え: $DP[N]$. 遷移: $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

桁 DP である。 $0$-indexed とする。上の桁からみていく。

$DP[0][i] = $ 上から $i$ 桁目未満までみた時に $a + b$ が $L$ と一致している $(a, b)$ の場合の数、
$DP[1][i] = $ 上から $i$ 桁目未満までみた時に $a + b$ が $L$ 未満であることが確定している $(a, b)$ の場合の数

と定める。初期状態: $DP[0][0] = 1$, otherwise $DP[i][j] = 0$. 答え: $DP[0][N] + DP[1][N]$. 遷移: $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

まず $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}. \] よって $1 \leq k \leq 18$ が一定である間は行列の累乗の計算で遷移を $O(\log L)$ にできる。真ん中の行列を $M _ k$ とおく。

$f(i) = A + Bi$ の桁数

と定めると、これは狭義単調増加関数であるから、次の値を順次めぐる式二分探索で埋めることができる。 $ub[0] = 0$, かつ、 \[ ub[i] = \min \{ ub[i - 1] \leq x < L \mid f(x) \neq i \}. \] $N _ i = ub[i] - ub[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 ライブラリを書き換えた。