エクサウィザーズ 2019 D - Modulo Operations

解法

(現在黒板に書かれている数字に影響があるような数字を取り除くことをここでは”使う”、ないような数字を取り除くことを”使わない”と表現します)
まず、 $i$ 回目に取り除いた数字よりも大きい数字を、 $i+1$ 回目以降で取り除いても、黒板に書かれる数字に影響はありません。
ということで、 $S$ を降順にソートしておくと、前から見ていき、使うか使わないかの選択をするだけで、最終的に黒板に書かれる数字が決まります。
これを踏まえたうえで、次のようなDPをします。
$dp[i][j] = i$ 番目までの要素について使う、使わないを決めた上で、黒板に書かれている数字が $j$ になるような並べ方の場合の数
ここでの並べ方、というのは少し特殊で、 $S_{1}$ ~ $S_{i}$ をただ並べる、というものではなく、長さ $N$ の数列に $S_{1}$ ~ $S_{i}$ を配置する方法、とします。
初期値は、 $dp[0][x] = 1$ となります。
このDPが計算できると、答えは $\sum dp[N][j] \times j$ (ただし $j \lt S_{N}$ )となります。

$i$ 番目の要素を"使わない"場合
$i$ 番目の要素は、長さ $N$ の数列でまだ埋まっていない箇所のうち、左端以外に配置することで、この条件を満たすことができます。配置できる場所は全部で $N-i$ 個です。
この場合、黒板に書かれている数字はもちろん $i-1$ 番目までを配置し終えた状態から変化しないので、このパターンの場合の数は
$dp[i-1][j] \times (N-i)$
となります。
$i$ 番目の要素を"使う"場合
まず、 $j \geqq S_{i}$ の場合は明らかに0です。 $S_{i}$ を取り除いた時点で、黒板の数字はそれより小さくなっているはずです。
$i$ 番目の要素は、長さ $N$ の数列のまだ埋まってない箇所のうち、一番左に配置することで、この条件を満たします。配置できるのはこの1通りのみです。
また、 $j + k S_{i}$ は、 $i$ 番目の要素を使うことで黒板の数字が $j$ になります。
よって、このパターンの場合の数は
$\displaystyle \sum_{k=0}^{(x-j)/S_{i}}dp[i-1][j+ k S_{i}]$ (ただし $j \lt S_{i}$ )
となります。

あとは、上の2つのパターンの和を取ればよいので、
$dp[i][j] = dp[i-1][j] \times (N-i)$ ( $j \geqq S_{i}$ の時)
$\displaystyle dp[i][j] = dp[i-1][j] \times (N-i) + \sum_{k=0}^{(x-j)/S_{i}}dp[i-1][j+ k S_{i}]$ ( $j \lt S_{i}$ の時 )

という計算をすればよいです。
このDPを計算できたら、最後に
$\sum dp[N][j] \times j$ (ただし $j \lt S_{N}$ )
を出力して終了となります。
DPの遷移の中で、総和をとっていく部分によって計算量が大きくなりそうに見えますが、実は時間内に間に合います。総和のループが回る最悪ケースは、 $j=0$ のときで $x/S_{i} + 1$ 回ですが、この総和を計算するケースは $j \lt S_{i}$ という条件が必要なため、たかだか $S_{i}$ 回です。つまり、少なくとも $X+S_{i}$ 回には収まっています。

感想

小さい数字でmodを取った時点で、それより大きい数字が影響を及ぼすことはない、という考察は割とすんなりでてきました。
DPをするときに一部のみを見るだけでよい(今回で言うとある値で割った余りをDPの添え字にする)、というのは、LCMラッシュが似たような考え方をしているので、この問題を解いていてよかったです(思いつくのには時間がかかりましたが)。

ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

エクサウィザーズ 2019 D - Modulo Operations

解法

感想