ARMERIA

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

Codeforces Round #654 (Div. 2) E2. Asterism (Hard Version)

Codeforces プログラミング 競技プログラミング

Problem - E2 - Codeforces

問題概要

長さ n の数列 a = \lbrace a_{0}, ..., a_{n-1} \rbrace と素数 p が与えられる。まず、以下の問題を考える。

  • 整数 x が与えられる。 \lbrace 0, 1, ..., n-1\rbrace を並び替えた順列 q_{0}, ..., q_{n-1} であって、全ての i について a_{q_{i}} \le x + i が成り立つようなものは何通りか？

この問題の答えが p の倍数とならないような x を全て列挙せよ。

制約

  • 2 \le p \le n \le 10^{5}
  • 1 \le a_{i} \le 10^{9}

解法

説明と実装を合わせるために0-indexedで表記します。また、与えられた数列 a をソートしておきます。

まず数え上げ問題の答えがどうなるかを考えます。 i 番目（最初を 0 番目とします）の選択において q_{i} として選べるインデックス k の候補は、 a_{k} \le x+i が成立するものから、 q_{i-1} までで既に使っている i 個を除外したものです。この選択肢の数は x が増えるほど増えていき、それ以前の選択で何を選んだかに依存しません。 n 個全てにおける選択肢の個数の積が数え上げ問題の答えになります。

p が素数であることから、NGになるのはこの選択肢の個数に p の倍数が含まれているときだけです。このNGになる条件を、選択肢が 0 個になる場合と p, 2p, 3p, ... 個になる場合でそれぞれ考えます。

選択肢が 0 個になる場合

i 番目の選択において選択肢が 0 個になる条件は、 a_{k} \le x+i が成立する k が i 個以下であること、つまり a_{i} \gt x+i が成立することです。どれか1つ以上の選択において選択肢が 0 通りとなる条件は、これら全ての和集合を取って

\displaystyle \max_{i \ge 0}(a_{i}-i) \gt x

が成立することです。

選択肢が p, 2p, 3p, ... 個になる場合

まずは選択肢がちょうど p 個になる場合だけ考えましょう。

i 番目の選択において選択肢が p 個になる条件は、 a_{k} \le x+i が成立する k がちょうど i+p 個であること、つまり

\displaystyle a_{i+p-1} \le x+i \lt a_{i+p}

が成立することです。これらのNG条件を順番に書き下して、 x が単独になるように移項すると

  • a_{p-1} \le x \lt a_{p}
  • a_{p}-1 \le x \lt a_{p+1}-1
  • a_{p+1}-2 \le x \lt a_{p+2}-2
  • ...
  • a_{n-1} -n+p \le x

となります。これらの式の並びを見ると、前の区間の終点より小さいところから次の区間が始まり、それを繰り返して最後は終点なく x \to \infty までNG区間が続いています。このことからこれら全ての和集合は、全区間の始点のうち最も小さいものだけを用いて

\displaystyle \min_{i \ge p-1}(a_{i}-i+p-1) \le x

と1つにまとめることができます。

f:id:betrue12:20200707220311p:plain

選択肢の個数が 2p, 3p, ... 個になるNG条件がまだ残っていますが、これらは選択肢が p 個になるような x より大きいので、これらも全て上記の条件に含まれます。

まとめ

以上でNG条件が全て考慮できて、これらは非常に扱いやすい形をしています。これらの2つの条件に当てはまらない x の範囲は

\displaystyle \max_{i \ge 0}(a_{i}-i) \le x \lt \min_{i \ge p-1}(a_{i}-i+p-1)

と1つの区間（あるいは空集合）として表現できるので、両端の値を求めることで答えを列挙することができます。

ACコード

Submission #85690039 - Codeforces