ABC134 D - Preparing Boxes

問題原文

atcoder.jp

問題要旨

個の箱が横一列に並んでおり、それぞれの箱には か「tex: 1」 が書かれている。 それぞれの箱につい玉を１つ入れる or 入れないを適切に選ぶことで、 を満たす任意の整数 について、
の倍数が書かれた箱に入っているボールの個数の和を２で割った余りが、箱 に書かれた数字に一致するようにせよ。

• 

解法

すでに「玉を入れる / 入れない」の選択をした箱について、もう一度チェックすることは避けたい。 もう一度チェックしなければならないような状況 = すでにチェックした箱番号の倍数の箱のボールの数が変化するような状況、である。

箱 に玉を入れることで影響が出るのは、 の約数の箱番号である。
当然 の約数は 以下なので、 以下の箱に影響が出る可能性がある と言える。

つまり、 が大きい方から計算していけばいい。

計算量は一見 [tex: O(N²)] だが、調和級数に似た形をしているので、 実は となる。
（ が大きければ大きいほど、チェックする箱は少なくなるので、 O(N²) よりぐっと計算量が落ちそうなことが感覚的にわかる）

実装

N = int(input())
A = [0] + list(map(int, input().split()))
 
B = [0] * (N + 1)
for i in reversed(range(1, N + 1)):
    ball = 0
    base = i + 1
 
    for j in range(i, N + 1, i):
        ball += B[j]
 
    if ball % 2 != A[i]:
        B[i] = 1
 
print(sum(B))
print(*[i for i, b in enumerate(B) if b == 1], sep=' ')

range の第３引数を使えば楽に実装できる。あと、 1-indexedにすると楽。

感想

いい問題。