ABC158 D - String Formation
問題原文
問題要旨
英子文字からなる があり、これに対しての操作クエリが 個与えられる。
クエリには2種類ある。
- 反転クエリ: 現状の を反転する
- 文字追加クエリ: の (先頭: / 末尾: ) に 英子文字 を追加する
個のクエリを処理したあとに出来上がる を求めよ。
解法
毎回愚直に反転処理をしていては間に合わないので何か工夫する必要がある。
少し考えると、「反転しているかどうか」の状態だけ持っておけば、文字追加クエリについて結局どちらに追加すればいいのかがわかるので、最後に構築できる。
実装
「未反転状態かつ先頭追加」「反転状態かつ末尾追加」の時は先頭追加、
「未反転状態かつ末尾追加」「反転状態かつ先頭追加」の時は末尾追加、
というようになっているので、工夫すると条件式が排他的論理和で楽に書ける。
S = list(input()) Q = int(input()) reverse, front, tail = False, [], [] for q in range(Q): query = list(input().split()) # 反転クエリ if len(query) == 1: reverse ^= 1 # 文字追加クエリ elif len(query) == 3: f, c = int(query[1]), query[2] f -= 1 # XORで判定できるように-1しておく if f ^ reverse: tail.append(c) else: front.append(c) if reverse: print(''.join((front[::-1] + S + tail)[::-1])) else: print(''.join(front[::-1] + S + tail))
感想
こういう考え方のXOR判定が解法になる問題がどこかにあった気がするなぁ。。。