2022-06-08 ARC140 の B を解いた
ARC140 : AtCoder Regular Contest 140 の B を解いた。
- B - Shorten ARC
https://atcoder.jp/contests/arc140/tasks/arc140_b
- 提出: https://atcoder.jp/contests/arc140/submissions/32319514
- R に A, C が隣接していないケースを忘れて 1WA
- 奇数回目の操作は R を残して R の左の A 右の C を消す ARC → R
- 偶数回目の操作は R を消す ARC → AC
- 操作回数を最大にしたい
- 操作には R が必要なので R を残せるよう奇数回目の操作を多くしたい
- R に隣接する A, C が各 1 個の場合には偶数回目に選んでも良い (R を残しても操作回数は増えない)
- 各 R の左の A と 右の C の個数の MIN を取る (これの総和が奇数回目の操作だけを繰り返したときの最大の操作回数になる)
- この数列を B とする
- B を deque に詰め替える 1 個のものを前に 2 個以上を後ろに入れる
- 奇数回目には後ろから出して 2 個以上残っているなら後ろに 1 個なら前に入れ直す
- 偶数回目には前から出して捨てる
- deque から出した回数が最大の操作回数になる
- 解説では
min(2M, \sum{x_i})で求めているがこれは思いつかない
自力 AC はひさしぶりな感じがする。
『 101 匹わんちゃん』を観た。子どもの頃以来だと思う。子犬がかわいい。白黒の犬を雪景色に置くのはどうなんだ。
電源コードにひっかけて抜いてしまった。椅子を変えてからコードに当たりそうだなとは思っていたのだけど……。束ねて整理した。
今日のコミット。