ABC220 参加記録 - geam1113’s diary

コンテスト中AC:A,B,D

$A$ の合計を $S$ とすると、 $X$ は $n$ 個の $S$ と $A$ の $m$ 番目の要素までの和で構成されているはずです。すなわち、

$X = S+...+S+A_1+...+A_m$

です。

$n$ は、 $n \leq \frac{X}{S}$ を満たす最小の整数で、 $m$ は順番に足していけば求まります。

コンテスト中にACできなかったのですが、実装に問題がありました。

マクロSUMを以下のように登録していました。

#define SUM(v) accumulate((v).begin(), (v).end(), 0)

しかし、long long型では以下のようにする必要があります。

#define SUM(v) accumulate((v).begin(), (v).end(), 0LL)

こういうミスがあるとなかなか気づけませんでした。

各操作後の状態は0〜9までしかないので、DPできます。

$dp[i][j]:=i$ 回目の操作で、余りが $j$ であるものの総数

遷移は、 $i$ 回目の操作結果から、 $i+1$ 回目の操作を考えます。

$i$ 回目の操作結果が $j$ なら、 $j+A_{i+1}\ mod\ 10$ と $j\times A_{i+1}\ mod\ 10$ が考えられるので、

$dp[i+1][j+A_{i+1}\ mod\ 10]+=dp[i][j]$

$dp[i+1][j\times A_{i+1}\ mod\ 10]+=dp[i][j]$

となります。

初期値は、 $dp[0][A_1]=1$ です。

答えは $dp[N][0],...,dp[N][9]$ を順に出力します。

全方位木DPというところまでわかったのですが、用意してあったライブラリの内容の本質を理解しておらず、実装が間に合いませんでした。

別記事にまとめたいと思います。