ABC 134 D "preparing Boxes"

内容

• ABC 134 D(400点) "Preparing Boxes"を解きました。
• pypyで提出(pythonだとTLEしてしまったため)

  問題

  https://atcoder.jp/contests/abc134/tasks/abc134_d

  考えたこと

• iの箱に入れると、iの約数の箱に影響が出る。
• 玉を入れると、自分より大きい数の箱に影響を与えることがあるけど、自分より小さい数の箱に影響を与えることはなさそう
  • 後ろから見てく!!
• 大きい方から考えていくと、いい感じに実装できる。

ポイント

• 大事なのは、偶奇なのでxorで管理できる。
• Aを直接更新しながら見ていく。
• 入力配列 Aで、後ろから見ていって、
  • A[i]が1なら、その箱にボールを入れて、iの約数の箱も更新
  • A[i]が0なら、もう条件を満たしているので、何もしない。

実装

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
put = [] #　玉を入れた箱の番号のlist

for i in reversed(range(N)):
    if A[i]:
        put.append(i+1)
        # iを素因数分解して、約数に1をxorしていく
        tmp = 1
        n = i+1
        #約数を見つけて、A[約数] の数を更新(偶奇を逆にする)
        while tmp*tmp <= n:
            if n % tmp == 0:
                A[tmp-1] ^= 1
                if tmp != n//tmp:
                    A[n//tmp-1] ^= 1
            tmp += 1


if len(put) > 0:
    print(len(put))
    print(*put)
else:
    print(0)

終わりに

• 本番中に通せなくて悲しかった。
• 約数を見つけることろで、計算量を減らすために、while tmp*2<nにしていたのに、裏の約数?を考えるのを忘れていた。(裏の約数とは、a=bcの時に、bの裏の約数はcって意味と受け取ってほしい)