AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Beginner Contest 035 C – オセロ
オセロっぽくは無いような……。範囲操作はそのまま扱うとTLEになるものが多く、何らかの形で工夫する必要がある事が多い。
# AtCoder Beginner Contest 035 C - オセロ
# https://atcoder.jp/contests/abc035/tasks/abc035_c
# tag: 範囲操作 いもす法 典型問題
# 範囲操作のクエリが多数あるため、そのまま実装すると TLE。
# どうにか情報を圧縮してやる必要がある。
# 00000000 に対して、(2, 6) の操作が行われるとすると
# 01111100 となる。これを素直に実装すると 5 箇所書き換える
# 必要があるのを、
# 01000010 (imos) という具合に記録することを考える。
# これは、1 の現れたところで直前の駒に対して反転させるという
# 意味合い。
# ちなみにここに更に (4, 6) の操作を行うと、
# 01010000 (imos)
# ^ ^ ここを書き換える
# といった感じになる。
# これにより、操作一回分につき 2 箇所を書き換えるだけで
# 済むようになる。
# 回答列は、この操作を記録した列を元に再構成していく。
# 01010000 (imos)
# ^ ^ 反転箇所
# 01100000 (result)
def main():
N, Q = map(int, input().split())
ops = [list(map(int, input().split())) for _ in range(Q)]
# 駒が反転するところに 1 を設定していく。
imos = [0] * (N+1)
for l, r in ops:
# 反転の反転を元通りにするため、xor 1 としている。
imos[l-1] ^= 1
imos[r] ^= 1
# 順に回答の列を再現していく。
# imos の末尾は使用しないので注意。
result = []
tmp = 0
for v in imos[:-1]:
tmp ^= v
result.append(tmp)
print(''.join(str(v) for v in result))
main()
関連
