ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

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

D - Modulo Operations

解法

単調減少列を考える

まず気付くべき点は、「ある値  a で余りを取ったあと、それより大きい値  b で余りを取っても値は変化しない」ということです。 a で余りを取った時点で黒板に書かれた値  x a-1 以下になっていて、その  x より大きい値で余りを取っても  x の値は変化しません。

このことから余りを取る操作列が1つ決まった時、実際に最後に残る値に影響するのは操作列から「それまでに登場した中で一番小さな値」だけを抜き出した単調減少列の並びだけであることが分かります。

f:id:betrue12:20190331080432p:plain

操作列からこのように抜き出される単調減少列を「実質的操作列」と呼ぶことにします。実質的操作列が同じ操作列は結果が同じになるのでまとめて考えることができます。例えば

  •  11 \to 13 \to 6 \to 22 \to 5
  •  11 \to 6 \to 5 \to 22 \to 13

この2つの操作列の実質的操作列はどちらも  11 \to 6 \to 5 になり、まとめて考えることができます。

ある実質的操作列になる操作列の個数を考える

では、ある実質的操作列に対応する操作列は何通りあるでしょうか。

与えられた全ての  S_{i} を降順にソートしておきます。実質的操作列としてあり得るものは、この降順ソートした数列から1個以上の要素を採用したものです。ここで「採用しなかった要素」は、自分より小さいどれかの要素の後ろに付くことになります。このときの選択肢の数によって操作列の個数が増えていきます。

f:id:betrue12:20190331082242p:plain

上の図のように考えると、ある実質的操作列に対応する操作列の個数は「採用しなかった要素について、それより小さい要素の個数を掛け算したもの」であることが分かります。

これを言い換えると、「降順にソートした数列を順に見ていって、 i 番目にある要素を採用しないと決めた時、場合の数は  N-i 倍される」と考えることができます(1-indexedです)。これが後のDPに繋がります。

DPする

降順ソートした列を順に見ていくDPができないか考えます。DPテーブルを「 i 番目まで見た時に○○である場合の数」とするのは良いとして、何を状態として持つべきでしょうか。

操作を適用していくのはその時点で黒板に書かれた数  x に対してなので、これを状態として持つことができないか考えます。 x の値は初期値  X 以下であり、 N \le 200 かつ  X \le 10^{5} という条件から  O(NX) が間に合いそうです。 x を状態として持ってしまいましょう。

 dp\lbrack i \rbrack \lbrack x \rbrack = 降順ソートした数列  i 番目まで見て、その時点での黒板に書かれた値が  x であるような場合の数

 dp\lbrack i \rbrack \lbrack x \rbrack からの遷移を考えます。遷移は  i+1 番目の要素を実質的操作列として採用するかしないかの2通りで考えることができます。

  • 採用する場合は、余りを取って  dp\lbrack i+1 \rbrack\lbrack x\%S_{i+1}\rbrack に遷移します。
  • 採用しない場合は、先ほど見たように場合の数を  N-(i+1) 倍した上で  dp\lbrack i+1 \rbrack\lbrack x\rbrack に遷移します。

これを最後まで計算すると各  x について「最後に書かれた値が  x になるような場合の数」を求められるので、答えを計算できます。

ACコード

Submission #4771085 - ExaWizards 2019

コンテスト本番コード。考察の過程で出てきたけど使わなかった階乗ライブラリが貼りっぱなしになっています(?)

公式解説では確率(期待値)の問題に置き換えて計算をしていますが、私自身が本番では場合の数ベースで考察をしたため、この記事でも場合の数ベースで解説しました。