[AtCoder] ABC 134 D – Preparing Boxes

2019年7月20日

問題

方針

最後の箱から調べる

後ろの箱からボールを入れることを考えると、その箱以降の倍数の個数は変化しないことが分かります。

例えば、\( i < \dfrac{N}{2} \) を満たす \( i \) の倍数は、\( 2i < N \) より、ただ一つの箱が存在することが分かります。ここで、\( i = \dfrac{N}{2} \) の箱を考えると、\( i \) の倍数は、\( i \) と \( 2i \) の箱を考えれば良いことが分かります。

イメージとしては後ろからエラトステネスの篩をやる感じです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int N;
  cin >> N;
  int a[N + 1]{};
  for (int i = 0; i < N; i++) {
    cin >> a[i + 1];
  }
  int b[N + 1]{};
  int cnt = 0;
  for (int i = N; i >= 1; i--) {
    int k = 0;
    for (int j = i; j <= N; j += i) {
      if (b[j] == 1) k++;
    }
    if (a[i] != (k % 2)) {
      b[i] = 1;
      cnt++;
    }
  }
  if (cnt == 0) {
    cout << 0 <<"\n";
    return 0;
  }
  cout << cnt << "\n";
  bool flag = true;
  for (int i = 1; i <= N; i++) {
    if (b[i] == 1) {
      if (flag) {
        cout << i;
        flag = false;
      }  else {
        cout << " " << i;
      }
    }
  }
  cout << "\n";
  return 0;
}