AtCoder ABC470振り返り (PythonでABC問題)

ABC470を振り返ります

今回はABCまで3問解答でした。

C問題はXORの性質が分かっていれば解ける問題ですが、私はわかっていなかったので時間がかかりました...。
80分ぐらいに解けて満足感はあったのですが、思ったほど順位は上昇せず...。

C問題よりD問題の方が、配点が高い割に難易度が低く、解く人が多かったようです。
(C問題はdiff:1006、D問題は 777)。
今回は、先にD問題を解くのが良い手順のようでした。

A - Fizz

3の倍数のときに〇〇する問題です。

N = int(input())
for i in range(N):
    if (i + 1) % 3 == 0:
        print("Fizz")
    else:
        print(i + 1)

B - Monocolor

初期状態で、最も多い色の数を求めて、その色で塗るようにしました。

N = int(input())
C = list(map(int, input().split()))

# 色ごとの数をカウントする
colors = defaultdict(int)
max_color = 0
for c in C:
    colors[c] += 1
    max_color = max(max_color, colors[c])

# 最大の色以外を塗れば良い
print(N - max_color)

C - Inc, Dec, Xor

以下を計算することで、query 1 のときは素早く計算できます。

# 前回の xor 和
prev_answer = (A1 ^ A2 ^ A3)

# 前回の xor 和に対し、 A2 を (A2+1) に変更したあとのxor和を求めるには
# (前回の xor 和) ^ A2 ^ (A2+1) とすれば良い
prev_answer ^ A2 ^ (A2 + 1)
# ↓
(A1 ^ A2 ^ A3) ^ A2 ^ (A2 + 1)
# ↓ A2 ^ A2 = 0 なので、A2が消える
(A1 ^ A3) ^ (A2 + 1)
# ↓
A1 ^ (A2 + 1) ^ A3

下記の回答例では 1385 msかかっているので、結構ギリギリな気もします。

N, Q = map(int, input().split())

# 0以外の数のみを対象にする
plus_value_dict = defaultdict(int)

xor_sum = 0
for i in range(Q):
    query = list(map(int, input().split()))

    if query[0] == 1:
        index = query[1]

        # 前回の答えに (A[i]) を xor する → 前回の答えから A[i] がなくなったのと同じ
        xor_sum = xor_sum ^ plus_value_dict[index]

        plus_value_dict[index] += 1

        # 前回の答えに (A[i] + 1) を xor する
        xor_sum = xor_sum ^ plus_value_dict[index]
    else:
        # 全探索で xor を求める
        xor_sum = 0
        for key in plus_value_dict.keys():
            plus_value_dict[key] = max(0, plus_value_dict[key] - 1)
            xor_sum = xor_sum ^ plus_value_dict[key]

    print(xor_sum)