【AtCoder】PythonでABC247のA, B, C, D, Eを解く

自分がコンテストでやった考察と実装を書いてみます.

# 目次

* [A問題 『Move Right』](https://qiita.com/yassu/items/11ed33af8ddeff8373df#a%E5%95%8F%E9%A1%8C-move-right)
* [B問題 『Unique Nicknames』](https://qiita.com/yassu/items/11ed33af8ddeff8373df#b%E5%95%8F%E9%A1%8C-unique-nicknames)
* [C問題 『1 2 1 3 1 2 1』](https://qiita.com/yassu/items/11ed33af8ddeff8373df#c%E5%95%8F%E9%A1%8C-1-2-1-3-1-2-1)
* [D問題 『Cylinder』](https://qiita.com/yassu/items/11ed33af8ddeff8373df#d%E5%95%8F%E9%A1%8C-cylinder)
* [E問題 『Max Min』](https://qiita.com/yassu/items/11ed33af8ddeff8373df#e%E5%95%8F%E9%A1%8C-max-min)

## A問題 『Move Right』

問題ページ: [A - Move Right](https://atcoder.jp/contests/abc247/tasks/abc247_a)
Difficulty: <font color="#808080"> 14 </font>
### 考察
与えられる $S$ を $S_1, S_2, S_3, S_4$とすると, 答えは $0, S_1, S_2, S_3$ である.
pythonではリスト $S$ の最後の値を除いたものは `S[:-1]` と表すことができ, 文字列 $T$ と 文字列 $S$ を連結したものは $T + S$ と書くことができる.
よって, 解答は `"0" + s[:-1]` である.
リストの長さは $4$ しかないので, 計算量は考える必要がない.
### 実装

``` python
#!/usr/bin/env pypy3
 
s = input()
print("0" + s[:-1])
```

## B問題 『Unique Nicknames』

問題ページ: [B - Unique Nicknames](https://atcoder.jp/contests/abc247/tasks/abc247_b)
Difficulty: <font color="#808080"> 202 </font>

### 考察

辞書 $cnt$ に対して $cnt[s]$ を文字列 $s$ が $s_j$ あるいは $t_j$ として現れた回数とする.
各 $1 \le j \le n$ に対して $a_j$ を選ぶことができるのは,以下のいずれかが成り立つ時である.

* `s_j != t_j` かつ `s_j` もしくは `t_j` はほかの文字列として現れない.
* `s_j == t_j` かつ `s_j` が他に現れない.

`cnt` を使うと, これを判定する処理はそれぞれ $O(1)$ なので, 全体の計算量は $O(N)$ である.

### 実装

``` python
#!/usr/bin/env pypy3

from collections import Counter

n = int(input())
A = [None for _ in range(n)]
cnt = Counter()
for i in range(n):
    A[i] = input().split()
    cnt[A[i][0]] += 1
    cnt[A[i][1]] += 1

res = True
for i in range(n):
    res &= ((cnt[A[i][0]] == 1 or cnt[A[i][1]] == 1)
            or cnt[A[i][0]] == 2 and A[i][0] == A[i][1])

if res:
    print("Yes")
else:
    print("No")
```

## C問題 『1 2 1 3 1 2 1』

問題ページ: [C - 1 2 1 3 1 2 1](https://atcoder.jp/contests/abc247/tasks/abc247_c)
Difficulty: <font color="#808080"> 149 </font>

### 考察

列 $S_n$ の長さを $a_n$ と置く. $S_n$ の作り方より

```math
\begin{align*}
& a_1 = 1, \\
& a_{n+1} = 1 + 2 a_n.
\end{align*}
```

これを解くと $a_n = 2^n - 1$ である. $a_{16} = 2^{16} - 1 = 65535$ である.
よってなにも考えずにリストの連結でしても $O(a_n) = O(2^n)$ なので, 、間に合う.


### 実装

``` python
#!/usr/bin/env pypy3

from collections import deque

n = int(input())
a = [1]
for i in range(2, n + 1):
    a = a + [i] + a

print(*a)
```

## D問題 『Cylinder』

問題ページ: [C - Cylinder](https://atcoder.jp/contests/abc247/tasks/abc247_d)
Difficulty: <font color="#804000"> 468 </font>

### 考察

典型的なdequeの問題.
要素の追加は `append([x, c])` とすれば $O(1)$ で処理できる.
要素を取り出して合計を計算するのは, 前の方から取り出せるだけ取り出して, 合計を出力する.
この時, 取り出す回数は高々今まで追加した回数なので, 取り出す回数の合計は $O(Q)$ である.

よって, 計算量は全体で $O(Q)$ である.

### 実装

``` python
#!/usr/bin/env pypy3
from collections import deque

deq = deque()
q = int(input())
for _ in range(q):
    t, *args = map(int, input().split())
    if t == 1:
        x, c = args
        deq.append([x, c])
    else:
        assert t == 2
        c = args[0]
        res = 0
        while c > 0:
            if deq[0][1] <= c:
                res += deq[0][0] * deq[0][1]
                c -= deq[0][1]
                deq.popleft()
            else:
                res += c * deq[0][0]
                deq[0][1] -= c
                c = 0
        print(res)
```


## E問題 『Max Min』

問題ページ: [E - Max Min](https://atcoder.jp/contests/abc247/tasks/abc247_d)
Difficulty: <font color="#00C0C0"> 1256 </font>

### 考察

区間の最も右のインデックスを走査して, 全ての個数を足し合わせることを考える.
求める区間が成り立ってほしい条件は

* 区間の全ての値は $x$ 以上 $y$ 以下である.
* 区間に $x$ がある.
* 区間に $y$ がある

である.
それぞれの考えられる区間について, 走査する際に, 区間の最も左のインデックス `left`, $x$ が出てくる最も右のインデックス `rightx`, $y$ が出てくる最も右のインデックス `righty` を計算します. それと同時に答えを更新します.
答えの更新について考えます. 区間の最も左の値は `left` 以上かつ `p = min(xright, yright)` 以下の値を取るので, `p - left + 1` を解答に追加すれば良いです.

それそれのインデックスの走査に対して, 計算量は $O(1)$ なので, 計算量は $O(N)$ です.

### 実装

``` python
#!/usr/bin/env pypy3

n, x, y = list(map(int, input().split()))
A = list(map(int, input().split()))

left = None
xright = None
yright = None
res = 0

for right, a in enumerate(A):
    if y <= a <= x:
        if left is None:
            left = right
        if A[right] == x:
            xright = right
        if A[right] == y:
            yright = right
        if xright is not None and yright is not None:
            p = min(xright, yright)
            res += p - left + 1
    else:
        left = None
        xright = None
        yright = None

print(res)
```