2022-06-09 ARC138 の B を解いた
大和証券プログラミングコンテスト2022 Spring (ARC138 : AtCoder Regular Contest 138) の B を解いた。
- B - 01 Generation
https://atcoder.jp/contests/arc138/tasks/arc138_b
- 提出: https://atcoder.jp/contests/arc138/submissions/32335237
- 空の数列 x から長さ N の 0 or 1 からなる数列 A を次の 2 つの操作で構築できるか
- 操作 1 : 左端に 0 を追加し、それ以外を反転する
- 操作 2 : 右端に 0 を追加する
- 最後の形 (かもしれない) が与えられているので操作を逆向きに考えて空の数列にできるかを考える
- 末尾の 0 は操作 2 で何個でも追加できるので、これを取り除く
- このとき数列は空 or 末尾が 1 になる
- 空なら Yes で終了する
- 1 は反転しないとつくれないので操作 1 が要る
- 先頭が 0 かを確認する
- 1 なら No で終了する
- 残りを反転させたいが、単純に反転させると何度も走査させられるのでおそらく間に合わない
- 反転されているかされていないかを判断する boolean で管理する
- ↑の 0 or 1 をそれに従って読み替える
- あとは末尾の 0 (反転しているなら 1) を取り除くところから繰り返せば良い
- 先頭・末尾からの削除があるので VecDeque を使うと良い
- N 回の要素削除があるだけなので O(N) で解ける
今日のコミット。