AtCoder ABC408 振り返り(緑コーダーがPythonでABC問題)

## ABC408を振り返ります

https://atcoder.jp/contests/abc408

旅行に行っていたり、他の用事があったりで、3週間ぶりのABCです。

結果、A問題からC問題の3問正解で、レーティングは変わらずでした。ブランクがあった割にはC問題までは結構早く解けたので、レーティング現状維持はできました。

D問題も解きたかったのですが、TLEになってしまい解答が通らず...要復習ですね。（→ その後、D問題の回答を追記しました）


## [A - Timeout](https://atcoder.jp/contests/abc408/tasks/abc408_a)

最後に起きていた時間を記録しておき、肩叩きの時間 T[i] が、寝てしまう時間S以内に発生しているか...を全探索でチェックしました。

``` python
N, S = map(int, input().split())
T = list(map(int, input().split()))

# 最後に起きていた時間を更新
last_wake = 0

# 各T[i]についてしらべる
for i in range(N):
    # 最後に起きていた時間からの経過時間がSより大きいなら、NG
    if T[i] - last_wake > S:
        print("No")
        exit()

    # 最後に起きていた時間を更新
    last_wake = T[i]
print("Yes")

```

## [B - Compression](https://atcoder.jp/contests/abc408/tasks/abc408_b)

配列 A から set を作成すると、重複が無くなります。重複を除いたあとの値をsortして、出力すればokです。


```python
N = int(input())
A = list(map(int, input().split()))

# list から set を作成(重複削除)
set_a = set(A)

# 重複を除いたものをソートする
sorted_a = sorted(set_a)

print(len(sorted_a))
print(*sorted_a)
```

## [C - Not All Covered](https://atcoder.jp/contests/abc408/tasks/abc408_c)

入力例1について、

* 砲台がカバーしている壁=1
* 砲台がカバーしていない壁=0

とすると、以下のような表ができる。

```
w1 w2 w3 w4 w5 w6 w7 w8 w9 w10
1  1  1  1  1  1  0  0  0  0
0  0  0  1  1  0  0  0  0  0
0  0  0  0  1  1  1  1  1  1
0  0  0  0  0  0  1  1  1  1
------------------------------
1  1  1  2  3  2  2  2  2  2
```

最小の手数で壁を突破するには、最も砲台のカバーが少ない壁を破る。
↓
各壁に対してカバーしている砲台数をカウントして、その最小値を求めれば良い。

----

砲台のカバー範囲を求める際、0 or 1 の配列をたくさん作るとTLEします。

ので、「Lの位置で+1, R+1の位置で-1する」ルールを使うと、目的の配列を少ない計算量で求められます。

```
Lの位置で+1, R+1の位置で-1する
+1 0  0  0  0  0  -1 0  0  0
0  0  0  +1 0  -1 0  0  0  0
0  0  0  0  +1 0  0  0  0  0
0  0  0  0  0  0  +1 0  0  0
------------------------------
プラスマイナスを足し合わせる
+1 0  0  +1 +1 -1 0  0  0  0
------------------------------
↓ 目的の配列が作れる
1  1  1  2  3  2  2  2  2  2
```


``` python
N, M = map(int, input().split())
LR = []
for _ in range(M):
    l, r = map(int, input().split())
    LR.append((l, r))

# 各砲台が、どこの壁をカバーしているか記録
walls = [0] * (N + 1)
for l, r in LR:
    # L の位置でプラスして、R+1の位置でマイナスする
    walls[l] += 1
    if r + 1 <= N:
        walls[r + 1] -= 1

# 各壁をカバーしている砲台数を求める
for i in range(1, N + 1):
    walls[i] += walls[i - 1]

# カバーしている砲台数の最小値が答え
ans = min(walls[1:])
print(ans)
```

## [D - Flip to Gather](https://atcoder.jp/contests/abc408/tasks/abc408_d) (追加解答)

コンテスト中には解けなかったので、復習で追加回答しました。

解説を見ていると、どうやらDPで解くのがわかりやすかった様子。コンテスト中、DPもちらっと頭に浮かんだのですが、DPはあまり深く掘り下げずに他のやり方でやっていて、結局TLEでした。

求める数列が以下のどれかになれば良い。
* [0の連続 A][1の連続 B][0の連続 C]
* [0の連続 A][1の連続 B]
* [0の連続 A]

ということで、dpの配列は以下のように求めれば良い。

```
dp[数列の位置][A,B,Cのどの部分か] = その位置での回数の最小値
```

``` python
# [0,1]の配列を与えて、配列に対する最小の交換回数を返すメソッド
def count(s_list):
    dp = [[0] * 3 for _ in range(len(s_list) + 3)]

    # 0の位置は A のみ可能
    dp[0][0] = 0
    dp[0][1] = INF
    dp[0][2] = INF

    # 配列の位置を最後までループ
    for i in range(len(s_list)):
        s = s_list[i]

        # A
        dp[i + 1][0] = dp[i][0] + (0 if s == 0 else 1)

        # B
        dp[i + 1][1] = min(dp[i][0] + (0 if s == 1 else 1), 
                           dp[i][1] + (0 if s == 1 else 1))

        # C
        dp[i + 1][2] = min(dp[i][1] + (0 if s == 0 else 1),
                            dp[i][2] + (0 if s == 0 else 1))

    # A, B, Cの中で最小のものが答え
    answer = min(dp[len(s_list)][0], dp[len(s_list)][1], dp[len(s_list)][2])
    return answer

T = int(input())
for _ in range(T):
    N = int(input())
    S = list(map(int, input().strip()))
    print(count(S))
```