ABC 272 E — Add and Mex

考察

mex(数列に含まれない最小の非負整数)を求めるには、数列の長さ未満の値が存在するかだけ分かればよい。各要素について、その範囲に入る操作回数だけを求め、操作回数ごとのリストへ値を振り分ける。全要素を毎回更新する代わりに、答えに関係する組だけを列挙する方針である。

要素の添字を i=1,…,Ni=1,\ldots,N、操作回数を j=1,…,Mj=1,\ldots,M とする。以降、AiA_i は初期値を表す。毎回 ii を加えるので、jj 回目の操作後の値は Ai+ijA_i+ij である。素朴に全要素を更新して毎回mexを求めると O(NM)O(NM) 時間となり、更新だけでも最大 4×10104\times 10^{10} 回になる。そこで、mexに関係しない値の更新を省けないか考える。

mexを決めるために必要な値

長さ NN の数列には、異なる値も高々 NN 個しかない。一方、0,1,…,N0,1,\ldots,N は N+1N+1 個あるので、少なくとも一つは数列に含まれない。従ってmexは NN 以下である。

0,1,…,N−10,1,\ldots,N-1 のどこかが欠けていれば、最初に欠けた値が答えになる。すべて存在すれば答えは NN である。この場合、NN 個の要素をすでに使い切っており、値 NN は存在できない。従って値 NN 自体を保存する必要はなく、負数や NN 以上の値は無視できる。

ただし、各時刻で全要素を調べてから不要な値を捨てても、NMNM 回の確認が残る。要素を固定し、必要な値になる時刻だけを先に求めるのが次の一手になる。

各要素が有効になる時刻区間

要素 ii を記録する条件は

0≤Ai+ij<N0\leq A_i+ij<N

である。すべて整数なので、右側は Ai+ij≤N−1A_i+ij\leq N-1 と同値になる。i>0i>0 より、jj について解くと

⌈−Aii⌉≤j≤⌊N−1−Aii⌋\left\lceil\frac{-A_i}{i}\right\rceil \leq j\leq \left\lfloor\frac{N-1-A_i}{i}\right\rfloor

を得る。ここで ⌈x⌉\lceil x\rceil は xx 以上の最小の整数、⌊x⌋\lfloor x\rfloor は xx 以下の最大の整数である。実際に答えを求める操作回数 1≤j≤M1\leq j\leq M との共通部分を取り、両端を

Li=max⁡(1,⌈−Aii⌉)L_i=\max\left(1,\left\lceil\frac{-A_i}{i}\right\rceil\right)
Ri=min⁡(M,⌊N−1−Aii⌋)R_i=\min\left(M,\left\lfloor\frac{N-1-A_i}{i}\right\rfloor\right)

とする。Li>RiL_i>R_i なら有効な時刻はない。それ以外では、j=Li,…,Rij=L_i,\ldots,R_i だけを列挙すればよい。

例えば N=5,M=4N=5,M=4 で、要素 i=2i=2 の初期値が A2=−5A_2=-5 なら、操作後の値は順に −3,−1,1,3-3,-1,1,3 である。下端は L2=3L_2=3、上端は R2=4R_2=4 となり、最初の負数二つを調べずに必要な値 1,31,3 を取り出せる。

保存する値の総数を数える

同じ要素の値は、時刻を一つ進めるたびに ii ずつ増える。有効時刻の個数を kik_i とすると、ki≥1k_i\geq 1 の場合、最初と最後の有効な値の差は (ki−1)i(k_i-1)i である。どちらも 0,…,N−10,\ldots,N-1 に収まるため、

(ki−1)i≤N−1(k_i-1)i\leq N-1

より

ki≤⌊N−1i⌋+1=⌈Ni⌉k_i\leq\left\lfloor\frac{N-1}{i}\right\rfloor+1 =\left\lceil\frac{N}{i}\right\rceil

となる。ki=0k_i=0 でもこの上界は成立する。初期値がどれほど負でも、有効範囲の幅と増加量だけで個数を抑えられる。

保存する組 (i,j)(i,j) の総数を KK とすると、

K=∑i=1Nki≤∑i=1N⌈Ni⌉≤N∑i=1N1i+N=O(Nlog⁡N)\begin{aligned} K&=\sum_{i=1}^{N}k_i\\ &\leq\sum_{i=1}^{N}\left\lceil\frac{N}{i}\right\rceil\\ &\leq N\sum_{i=1}^{N}\frac{1}{i}+N\\ &=O(N\log N) \end{aligned}

である。最後は調和級数 ∑i=1N1/i=O(log⁡N)\sum_{i=1}^{N}1/i=O(\log N) を使った。時刻ごとには多くの要素があっても、全時刻を合わせて保存する個数は小さい。

時刻ごとのリストからmexを求める

操作回数 jj ごとに空のリスト bucket[j] を用意する。各要素 ii について有効時刻区間を求め、その区間内の各 jj に対して Ai+ijA_i+ij を bucket[j] へ追加する。このリストには、その時刻のmexに関係する値だけが入る。同じ値が複数回入ってもよい。

次に j=1,…,Mj=1,\ldots,M の順に答えを求める。リストの要素数を sjs_j とする。異なる値は高々 sjs_j 個なので、mexは sjs_j 以下である。従って、この時刻ではさらに存在確認の範囲を 0,…,sj−10,\ldots,s_j-1 に縮められる。

  1. 添字 0,…,sj0,\ldots,s_j を持つ真偽値配列を、すべて偽で初期化する。
  2. bucket[j] の値 vv のうち v<sjv<s_j について、添字 vv を真にする。同じ値を再び見ても真のままでよい。
  3. 添字 00 から順に調べ、最初に偽となる添字を答えとして出力する。添字 sjs_j は偽のままなので、遅くともそこで止まる。

例えばリストが (0,0,2)(0,0,2) なら、重複を含めた要素数は3だが、存在する値は0と2だけなのでmexは1である。空のリストでは、長さ1の配列の添字0が初めから偽となり、0を出力する。

典型の発動条件

mexの値域による枝刈り

要素数からmexの上界が分かり、各値が存在するかだけを使うときに適用できる。長さ NN なら 0,…,N−10,\ldots,N-1 の存在だけを保存し、すべて揃った場合は NN と答える。値の大きさではなく、答えに影響する範囲を先に決める。

調和級数による疎な列挙

添字 ii ごとの処理回数を ⌈N/i⌉\lceil N/i\rceil のように抑えられるとき、各回の最大値を掛ける代わりに総和を取ると O(Nlog⁡N)O(N\log N) になる。ただし、不要な候補を生成してから捨てるのでは足りない。有効区間の両端を直接求めるなど、その個数に比例して生成できることも必要である。

問題固有の要素

「各要素へ、その添字を毎回加える」という操作から、要素ごとの値を時刻の一次式で書ける。全時刻の数列を作る必要はなく、各要素が必要な値域を通過する時刻だけを逆に求められる。増加量が添字そのものであることが、調和級数による総数評価につながる。

正当性

有効時刻区間は、条件 0≤Ai+ij<N0\leq A_i+ij<N と 1≤j≤M1\leq j\leq M を同時に満たす整数時刻全体である。従って bucket[j] には、操作後の数列のうち 0,…,N−10,\ldots,N-1 にある値が、各要素につき一度ずつ漏れなく入る。この範囲外を除いてもmexは変わらない。

リストの要素数が sjs_j なら、重複があっても異なる値は高々 sjs_j 個なのでmexは sjs_j 以下である。真偽値配列は sjs_j 未満の各値の存在を正しく表す。そこで最初に偽となる添字が sjs_j 未満なら、それが最小の欠けた非負整数である。そこまで欠けていなければ 0,…,sj−10,\ldots,s_j-1 の sjs_j 種類で要素を使い切るので、mexは sjs_j である。空のリストも同じ手順でmexが0となる。

記録する組の総数は K=O(Nlog⁡N)K=O(N\log N) である。各時刻の初期化・存在の記録・mex走査は O(sj+1)O(s_j+1) 時間であり、空でも0の確認と出力に定数時間かかる。∑j=1Msj=K\sum_{j=1}^{M}s_j=K より、全時刻の処理は O(K+M)O(K+M)、区間計算も含む全体は O(Nlog⁡N+M)O(N\log N+M) 時間となる。

実装上の注意

  • C++の整数除算は0方向へ切り捨てるため、負数の数学的な床関数とは異なる。例えば ⌊−1/2⌋=−1\lfloor-1/2\rfloor=-1 だが、C++の -1 / 2 は0になる。
  • 負数の除算を避けるなら、まず Ai≥NA_i\geq N の要素を飛ばす。残りは N−1−Ai≥0N-1-A_i\geq 0 なので、上端を min(M, (N - 1 - A_i) / i) で求められる。下端は Ai≥0A_i\geq 0 なら1、Ai<0A_i<0 なら (-A_i + i - 1) / i である。最後に Li>RiL_i>R_i を確認し、空区間なら何も追加しない。両端が等しい場合や最初の有効時刻が MM の場合も、その一回を含める。
  • 要素の添字は1始まりである。配列を0始まりで実装する場合、加える量は配列の添字に1を足した値になる。積 ijij は最大 4×10104\times 10^{10} なので、値の計算は積を取る前から64 bit整数型にする。
  • 毎回長さ NN の存在配列を初期化すると O(NM)O(NM) 時間に戻る。上の手順では長さ sj+1s_j+1 の局所配列を使うため、初期化の総費用も O(K+M)O(K+M) となる。長さ NN の配列を使い回すなら、最初に一度だけ0で初期化した stamp を用意し、その時刻の値 vv に対して stamp[v] = j と記録する方式でもよい。各時刻で x=0x=0 から始め、x<Nx<N かつ stamp[x] == j の間だけ xx を増やせば、全消去なしでその時刻のmexを求められる。

復習の核

  • mexは要素数以下。その上界までの存在確認へ絞り、すべて揃った場合の答えも決める。
  • 「全時刻×全要素」が重いときは、各要素が答えに関係する時刻だけを直接求められないか考える。
  • 列挙件数を抑えたら、初期化と答えの探索までその件数に比例するか確認する。空でも一回の処理と出力が必要なので、時刻数の項を落とさない。

計算量と制約

時間

O(Nlog⁡N+M)O(N\log N+M)。各要素の区間計算に O(N)O(N)、リストの準備に O(M)O(M)、値の追加に総計 O(K)O(K) 時間かかる。各時刻の配列初期化と存在の記録は O(sj+1)O(s_j+1)、mex走査も停止時の確認を含めて高々 sj+1s_j+1 回である。出力を含む総時間は O(N+K+M)O(N+K+M) となり、K=O(Nlog⁡N)K=O(N\log N) を代入する。すべてのリストが空でも O(N+M)O(N+M) 時間かかる。

空間

O(Nlog⁡N+M)O(N\log N+M)。入力に O(N)O(N)、リストの管理と保存する値に O(M+K)O(M+K)、一時刻ずつ再利用する局所配列に高々 O(N)O(N) を使う。同じ時刻に各要素は高々一度しか追加されず、sj≤Ns_j\leq N である。

制約との対応

1≤N,M≤2×1051\leq N,M\leq 2\times 10^5、−109≤Ai≤109-10^9\leq A_i\leq 10^9。制限は2秒・1024 MiBである。初期値の絶対値や操作回数に比例して要素ごとの時刻を探すのではなく、区間の両端を直接求めることで、保存する値は総計 O(Nlog⁡N)O(N\log N) 個に収まる。i>0i>0 による値の単調増加と、mexの上界が NN であることを使っている。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Add and Mex の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 候補数を界して全列挙・有限case分解する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 有界全列挙・有限case分解

      執筆: abc-explanation-author1.1.1 / revision 3

      学習の位置

      体系上の位置: 候補数を界して全列挙・有限case分解する

      • 制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。

      この解説で扱わないこと:

      • 探索空間を二つへ分けて照合するmeet-in-the-middle、および再帰部分問題へ分ける分割統治。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題