AtCoder Beginner Contest 135

更新日時:

AtCoder Beginner Contest 135

ソースコード

解法のメモ

A - Harmony

$K = (A + B) / 2$ とするしかない。計算機の割り算をする。 $\lvert A - K \rvert = \lvert B - K \rvert$ かどうかを判定する。

B - 0 or 1 Swap

$0$-indexed とする。 $\sharp \{ i \in \mathbb{N} \mid A _ i = i \} = 0, 2$ が条件である。

C - City Savers

前の方から貪欲に倒すのが最善である。

D - Digits Parade

DP による。 $M = 13$, $K = 5$ とする。 $S$ を reverse しておく。

$DP[i][j] = S$ の $i$ 文字目までみて $M$ で割ったときの余りが $j$ である場合の数

と定める。初期状態: $DP[0][0] = 1$, otherwise $0$. 答え $DP[S.size()][K]$. 遷移: $i = 0, \dots, S.size() - 1$ に対し、 $S[i] = ?$ の場合、 $j = 0, \dots, M - 1$ に対し、 $k = 0, \dots, 9$ に対し、 \[ DP[i + 1][(j + 10^i k) \% M] \mathbin{ {+} {=} } DP[i][j], \] その他の場合は、 $j = 0, \dots, M - 1$ に対し、 $k = S[i]$ とすると、 \[ DP[i + 1][(j + 10^i k) \% M] \mathbin{ {+} {=} } DP[i][j]. \]

E - Golf

ポイント

F - Strings of Eternity

ポイント

その他