7K12 blog

猫でも分かるアルゴリズム解説

ABC134 D - Preparing Boxes

f:id:tkr987:20200805235032p:plain

https://atcoder.jp/contests/abc134/submissions/15708918

  • 1, 2, 3, ... の倍数毎に調べる要素数は調和級数になっている
  • 後ろから情報を確定していく

f:id:tkr987:20200805235417p:plain

i+1以降の箱のうち倍数iの箱だけ考える。(i+1以降の)倍数iの箱に入っているボールの合計をsとしたとき、s % 2 = 0 ⇔ (s+1) % 2 = 1、s % 2 = 1 ⇔ (s+1) % 2 = 0、になる。つまり、i番目の箱にボールを入れると合計sの剰余が逆転する。1, 2, 3, ...の倍数の箱を調べる回数は調和級数になるので O(N \log N)で済む。i番目の箱を確定させるためにはi+1以降の箱情報が必要なので、合計sの剰余と a_{i}が異なればボールを入れて、同じならボールを入れない、という処理を後ろから繰り返せば答えが得られる。

箱を0-indexにするとi=0のときに for (auto j = i; j < N; j += i) count += b[j]; のようなループ処理が永遠に終わらなくなったりして面倒なので、箱の配列を1-indexにしておくと実装がシンプルになる。