Atcoder Problems という競プロを勉強する上でのコンテンツがあります。AtCoder Problems
今回は、hard100問の内、31問目を解説していきたいと思います。
問題名 【D – Preparing Boxes】
入力
N：配列の長さ
ai: (iの倍数に書かれた箱に入っているボールの和)%2
考察
今回問題を理解するのが難しいです
1 以上 N 以下の任意の整数 i について、i の倍数が書かれた箱に入っているボールの個数の和を 2 で割った余りが aiするようにするには、どの箱にボールを入れれば良いですか？
という問題です。例えば
ex)
3
1, 0, 0
1の倍数に入っている(ボールの数)%2は・・・1
2の倍数に入っている(ボールの数)%2は・・・0
3の倍数に入っている(ボールの数)%2は・・・0 になるように箱にボールを入れてください となります。
今回の場合、箱1にのみにボールを入れれば条件を満たし良いのですが・・・
ここで考えなければならないのは、箱1にボールを入れても、2の倍数のとき、3の倍数のときに影響が出ないということです。逆に言うと、箱2を入れてしまうと、1の倍数のときと2の倍数のときの計算に影響が出てしまいます。
そのため、影響力の大きい箱からボールを入れるか入れないかを決め、徐々に影響力の小さい箱について探索すれば良いです(なぜならNの箱にボールを入れるとNの約数の結果にも影響が出てしまうため、大きい数から探索し最後に小さい数で調整する必要があるため)
コード
N = int(input())
A = list(map(int, input().split()))
A = [0] + A#1-indexにするために0を頭に挿入
#箱にボールを入れるか入れないかを記憶するリストを用意
box = [0 for i in range(N+1)]#1-indexにするためN+1の配列を生成(0番目は使用しない)
M = 0#何回ボールを入れたかをカウント
ans = []#ボールを入れた箱のindexを記憶
for baisuu in range(N,0,-1):#大きい倍数から探索
cnt = 0
for i in range(baisuu,N+1,baisuu):#baisuuの倍数の箱に
cnt += box[i]#入っているボールの数をカウント
if cnt %2 == A[baisuu]:#もし(baisuuの倍数に入っているボールの数)%2が入力と同じ時
continue#そのまま
else:#もし(baisuuの倍数に入っているボールの数)%2が入力と異なる時
box[baisuu] += 1#倍数番目の箱にボールを入れ
M += 1#ボールを入れた回数を+1し
ans.append(baisuu)#そのインデックスを記憶する
print(M)
print(*ans, sep = " ")まとめ
前の問題
次の問題
コメント