けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 134 D - Preparing Boxes (緑色, 400 点)

一見すると  O(N^{2}) かかるように思えるかもしれない。でも実は  O(N \log N) になる。

問題概要

 N 個の整数  A_{1}, \dots, A_{N} が与えられる (それぞれ 0 または 1)。このとき、 N 個の 0-1 変数  x_{1}, \dots, x_{N} の値を、以下の条件を満たすように定めよ。

  •  i (=1, 2, \dots, N) に対して、 x_{i} + x_{2i} + \dots を 2 で割ったあまりが  A_{i} に一致する

制約

  •  1 \le N \le 2 \times 10^{5}

考えたこと

たとえば  N = 6 のときはこんなふうになる。

  •  x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} \equiv A_{1} \pmod 2
  •  x_{2} + x_{4} +  x_{6} \equiv A_{2} \pmod 2
  •  x_{3} + x_{6} \equiv A_{3} \pmod 2
  •  x_{4} \equiv A_{4} \pmod 2
  •  x_{5} \equiv A_{5} \pmod 2
  •  x_{6} \equiv A_{6} \pmod 2

これを見て思うことは、 x_{6}, x_{5}, x_{4}, x_{3}, x_{2}, x_{1} の順に自動的に決まっていきそうだということ。まず  x_{4}, x_{5}, x_{6} が決まり、それが決まると

 x_{3} + x_{6} \equiv A_{3} \pmod 2

より  x_{3} が決まり、

 x_{2} + x_{4} +  x_{6} \equiv A_{2} \pmod 2

より  x_{2} が決まり、

 x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} \equiv A_{1} \pmod 2

より  x_{1} が決まる。これは一般にも成り立ちそうだ。

計算量解析

以上から一般に、 x_{i+1}, x_{i+2}, \dots, x_{N} が決まっているときに

  •  x_{i} \equiv A_{i} - x_{2i} - x_{3i} - \dots

とすればよいことがわかる。しかしこの解法は一見すると  O(N^{2}) の計算量となりそうな気がしてしまう。

でもよくよく考えてみよう。 x_{i} を求めるのに参照する  x_{j} の個数は  O(\frac{N}{i}) となるのだ。そしてこれを  i = 1, 2, \dots, N について合計すると

 N + \frac{N}{2} + \frac{N}{3} + \dots + \frac{N}{N} = O(N \log N)

となるのである。一般に

 1 + \frac{1}{2} + \frac{1}{3} + \dots

を調和級数と呼び、 O(\log N) 程度の発散スピードであることが知られている (証明は  y = \frac{1}{x}積分 \log{x} であることから来る)。

コード

実装上は  A_{i} - x_{2i} - x_{3i} - \dots のところは

 A_{i} + x_{2i} + x_{3i} + \dots

に置き換えても OK。mod. 2 の世界では「引き算」も「足し算」も一緒だからだ。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N+1);
    for (int i = 1; i <= N; ++i) cin >> A[i];

    vector<int> x(N+1, 0);
    for (int i = N; i >= 1; --i) {
        int sum = A[i];
        for (int j = i*2; j <= N; j += i) sum += x[j];
        x[i] = sum % 2;
    }
    vector<int> res;
    for (int i = 1; i <= N; ++i) if (x[i] == 1) res.push_back(i);
    cout << res.size() << endl;
    for (auto v: res) cout << v << " ";
    cout << endl;
}