[AtCoder] ABC 134 D – Preparing Boxes
問題
方針
最後の箱から調べる
後ろの箱からボールを入れることを考えると、その箱以降の倍数の個数は変化しないことが分かります。
例えば、\( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません