yukicoder contest 370 E
解き方
※ ここに書く解き方は、解説に書かれている事実に気づかなかった人の解き方である まず、非負正数列$ A が良い数列となる条件を考える。
$ A の偶数番目にある要素の総和を$ s_{\mathrm{even}} 、奇数番目にある要素の総和を$ s_{\mathrm{odd}} とすると、解説にある通り、次が成り立つ。
$ s_{\mathrm{even}} \equiv s_{\mathrm{odd}} \mod M \iff A \text{ が良い数列}
まず右から左を示す。各操作で$ s_{\mathrm{even}} も$ s_{\mathrm{odd}} も$ 1 増えるため、$ A に対して操作を何度繰り返しても、$ s_{\mathrm{even}} - s_{\mathrm{odd}} は一定である。
また、仮定より、$ A に操作を繰り返すことで、全ての要素を$ M の倍数にすることができるので、その操作後の数列を$ A^{\prime} とする。
$ A^{\prime} の偶数番目にある要素の総和を$ s^{\prime}_{\mathrm{even}} 、奇数番目にある要素の総和を$ s^{\prime}_{\mathrm{odd}} とすると、明らかに$ s_{\mathrm{even}} \equiv s_{\mathrm{odd}} \mod M である。
また、$ A^{\prime} は$ A に操作を繰り返して得られた数列であるので、$ s_{\mathrm{even}} - s_{\mathrm{odd}} = s^{\prime}_{\mathrm{even}} - s^{\prime}_{\mathrm{odd}} \equiv 0 \mod M となる。よって示せた。
次に、左から右を示す。解説に書かれている通り、$ A の先頭の要素から$ M の倍数になるように操作を繰り返していくことを考える。
このとき、後ろの2つの要素を残して、それ以外の要素が$ M の倍数にできるのは明らかであるため、その時の数列を$ A^{\prime} とする。
$ A^{\prime} の偶数番目にある要素の総和を$ s^{\prime}_{\mathrm{even}} 、奇数番目にある要素の総和を$ s^{\prime}_{\mathrm{odd}} 、末尾にある2つの要素を$ A^{\prime}_{N-1}, A^{\prime}_{N} で表すとする。
このとき、末尾２つ以外の要素は全て$ M の倍数のため、$ A^{\prime}_{N-1} - A^{\prime}_{N} \equiv (-1)^{N-1}(s^{\prime}_{\mathrm{even}} - s^{\prime}_{\mathrm{odd}}) \mod M を満たす。
また、上での考察と仮定より、$ s^{\prime}_{\mathrm{even}} - s^{\prime}_{\mathrm{odd}} = s_{\mathrm{even}} - s_{\mathrm{odd}} \equiv 0 \mod M が成り立つ。
以上より、$ A^{\prime}_{N-1} \equiv A^{\prime}_{N} \mod M であるため、$ A^{\prime} 操作を繰り返すことで末尾２つの要素を同時に$ M の倍数にすることができる。
よって、数列$ A に操作を繰り返すことで全ての要素を$ M の倍数にできたため、$ A が良い数列であることが示せた。
以上より、$ s_{\mathrm{even}} と$ s_{\mathrm{odd}} を計算することで、良い数列かどうかは判定することができる。
次は、良い数列だった場合に、それが良い数列の中で何番目かを考えていく。
解説に書かれているような$ (M-1) 進数として考える方法が思いつかなかったため、動的計画法で計算する。
まず、解き方を書き下す際の都合により、$ A^{\prime}_{0},A^{\prime}_{1},\ldots,A^{\prime}_{N} を次を満たす$ N+1 の非負整数とする。
$ A^{\prime}_{0} = 0 かつ、$ 1 \le i \le N を満たす任意の整数$ i について$ A^{\prime}_{i} は$ A_{i}+M-A^{\prime}_{i-1} を$ M で割ったときの余りに等しい
これは、上の証明で書いたような、先頭の要素から$ M の倍数にしていく操作を考えたときの途中の状態を表している。
具体的には、$ i \le i \le N を満たす整数$ i について、$ i より前の要素が全て$ M の倍数になった直後の$ i 番目の値が$ A^{\prime}_{i} である。
また、先頭の要素についても他の要素と同じように扱えるよう、便宜上$ A^{\prime}_{0} = 0 としている。
さて、辞書順で$ A が何番目かを求めるには、辞書順で$ A より小さい数列で、良い数列がいくつあるかを求めれば良い。
後者は、$ 1 \le i \le N を満たす整数$ i それぞれについて以下の値を求め、それらを足せば求められる。
$ i-1 番目までの要素は$ A と等しく、$ i 番目の要素が$ 0 以上$ A_{i} 未満であるような良い数列の個数
よって、以降は良い数列の個数を計算することを考える。
この段落には、せっかくなので、最終的な方法を思いつくまでの私の思考過程の一部を記す。（解き方に影響ないため読む必要なし）
まずは、末尾の要素以外を自由に決めて、良い数列となるように末尾の要素で調整することを考えた。
この考えにもとづき、良い数列の個数は$ M-1 の累乗で表されると推測したが、サンプル1の答えが合わない。
サンプル1の説明をみると、先頭の要素が$ 0 ある良い数列の個数と、先頭の要素が$ 1 である良い数列の個数が異なることがわかる。
今回の問題では、$ M-1 を数列の要素にすることができないため、末尾の要素で調整することができない場合があることがわかった。
先頭の要素で良い数列の個数が変わるが、先頭の要素で場合分けして計算しようとすると、計算量が$ NM になり間に合わない。
サンプル1の場合は、先頭の要素が$ 0 かそれ以外かで変わるように思えたので、その2つで場合分けすることを次に考えた。
しかし、再帰的に考えたとき、先頭の要素が$ 0 である数列を作れる場合と作れない場合があることに気づき、コンテスト中はここで諦めた。
終了後に、$ 0 を特別扱いしたように、$ 0 にできない場合も特別扱いすれば良いのではと思いつき、それを突き詰めて下の方法に至った。
次のような性質を満たすように、関数$ \mathrm{dp} を構築することを考える。
$ \mathrm{dp} (N, 0) は、先頭の要素が$ 0 であるような良い数列の個数に等しい
$ 1 \le j \le M-2 を満たす任意の整数$ j について、$ \mathrm{dp} (N, 1) は、先頭の要素が$ j であるような良い数列の個数に等しい
$ \mathrm{dp} (N, 2) は、先頭の要素が$ M-1 であるような良い数列の個数に等しい
※ 本来は数列の要素に$ M-1 が含まれてはならないので、3つ目の性質はおかしいが
※$ A^{\prime}_{i} は$ M-1 になり得るので、先頭の要素だけは$ M-1 になって良いとして考える。
※ 解説で、$ (M-1) 進数を考えていることを考えると、これは繰り下がりのようなものかもしれない。
そのためには、任意の正整数$ i について次の漸化式を満たすように、関数$ \mathrm{dp} を構築すれば良い。
$ \mathrm{dp} (i+1, 0) = \mathrm{dp} (i, 0) + (M-2) \times \mathrm{dp} (i, 1)
$ \mathrm{dp} (i+1, 1) = \mathrm{dp} (i, 0) + \mathrm{dp} (i, 2) + (M-3) \times \mathrm{dp} (i, 1)
$ \mathrm{dp} (i+1, 2) = \mathrm{dp} (i, 2) + (M-2) \times \mathrm{dp} (i, 1)
関数$ \mathrm{dp} が構築できたら、例えば下のようにして、辞書順で$ A より小さい、良い数列の個数を計算できる。
変数$ \mathrm{ans} に$ 0 を代入する。
$ 1 \le i \le N を満たす整数$ i それぞれについて、下の計算を行う。
変数$ \mathrm{ans} に$ A_{i} \times \mathrm{dp} (N-i+1, 1) を加算する。
もし$ A^{\prime}_{i-1} \lt A_{i} ならば、変数$ \mathrm{ans} に$ \mathrm{dp} (N-i+1, 0) - \mathrm{dp} (N-i+1, 1) を加算する。
もし$ 0 \lt A^{\prime}_{i-1} \le A_{i} ならば、変数$ \mathrm{ans} に$ \mathrm{dp} (N-i+1, 2) - \mathrm{dp} (N-i+1, 1) を加算する。
変数$ \mathrm{ans} に格納されている値が、辞書順で$ A より小さい、良い数列の個数である。
解答例
下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
code: C
int main () {
int n = 0;
int m = 0;
int res = 0;
long long ans = 1LL;
long long mod_num = 998244353LL;
long long tmp = 0LL;
res = scanf("%d", &n);
res = scanf("%d", &m);
for (int i = 0; i < n; i++) {
res = scanf("%lld", a+i);
}
printf("-1\n");
return 0;
}
for (int i = 1; i < n; i++) {
}
for (int i = 0; i < n-1; i++) {
long long cnt = 0LL;
cnt += 1LL;
}
if (tmp > 0LL && ai >= tmp) { cnt += 1LL;
}
ans %= mod_num;
tmp = (((long long)m)-tmp+ai)%((long long)m); }
printf("%lld\n", ans);
return 0;
}
私の提出一覧
（工事中）
table: submissions_yukicoder_contest_370_E
提出のURL 提出時刻 結果 備考
1回目
感想
（工事中）