yamake's blog

主に競プロ、たまに自転車

ARC114-C Sequence Scores

　ARC114お疲れさまでした。ABC3完で温まれてうれしいです。この問題を僕と同じ解き方をした人が少なかったので、自分の解法を紹介します。

問題概要

　日本語問題文があるので割愛

解法

　大まかな方針は 『愚直な操作回数 NM^N から不要な操作を引いていく。』です。
　初めに、愚直な操作について考えます。数列のそれぞれの要素を A と同じものに書き換える N 回の操作を全ての数列に対して行います。この時の操作回数は A のありうる個数 M^N と一度当たりの操作回数 N の積 NM^N になります。ここから不要な操作を減らすことを考えます。
　操作の条件から i < j に対して A_i\ =\ A_j かつ、 i < k < j を満たす k で A_k \leq A_j が存在しない j は i とまとめて操作して良いとわかります。

f:id:yamakeeee:20210315181649p:plain
操作の例

　したがって、NM^N からそのような i,\ j の個数を引くと答えが求められます。
　数列が i 番目まで埋まっているとき、値 j が最後である数列の埋め方の数について考えます。これは i 番目の値が j であり、i-1 番目以前の値は何でもよいので、M^{i-1} となります。
　次に、1 < i \leq N に対して i 番目の値が j のとき操作が不要になる条件を満たす組合せの数を求めます。これは 1 \leq k < i を満たす k 番目の値が j で終わる数と k+1 番目から i 番目までの値が j+1 以上になる組合せの数の積であるので、 (M-j)^{i-k-1} M^{k-1} として求められます。
　dp[i][j] を『数列の i 番目まで埋まっている時、値 j の操作が不要になる数』と定義して、dp 遷移について考えます。dp[i][j] は不要な操作の総和であるので dp[i][j]=\Sigma_{k=1}^{i-1}{(M-j)^{i-k-1} M^{k-1}} として求められます。この式を変形するとdp遷移は dp[i][j] = (M-j)dp[i-1][j]+M^{i-2} となります。
　dp 配列が求められているとき、 i+1 番目以降の数字は自由に選べることを考慮すると、それぞれの値 j において減らすことができる操作回数は M^{N-i-1}\ dp[i][j] となります。
　1 < i \leq N と 1 \leq j \leq M に対してこれを行うので、このアルゴリズムは時間計算量 O(NM) になります。
提出コード