【AtCoder】ABC185-189のCをPython3で解説

## ABC185 C - Duodecim Ferra

https://atcoder.jp/contests/abc185/tasks/abc185_c

### タイプ
- comb()（組み合わせ）

### 解説
組み合わせの問題。
例えば、`oooooooooooooo`（oは整数）という並びがあったら、oとの間にかぶらないように11本の仕切りをおいて分割すれば求められる。したがって、`(L-1) C 11`の計算を`comb()`で行えば良い。

### 回答例
```python
# comb()
from math import comb

L = int(input())
num = L - 12
ans = comb(num + 11, 11)
print(ans)
```

## ABC186 C - Unlucky 7

https://atcoder.jp/contests/abc186/tasks/abc186_c

### タイプ
- oct()
- in str()

### 解説
問題文の通り、「1以上N以下の整数のうち、10進法で表しても8進法で表しても7を含まないような数はいくつありますか？」。
文字列の中にある文字が含まれているという書き方は、探したい文字列を`a`、検証する文字列を`b`とすると、`a in str(b)`とかける。8進数は`oct()`でわかるので、これについて`7`を含んでいるものを数え上げ、全体`N`から引くと、値が求められる。

### 回答例
```python
# oct(), in str()
N = int(input())
cnt = 0

for i in range(1, N+1):
    if '7' in str(i) or '7' in str(oct(i)):
        cnt += 1

print(N - cnt)
```

## ABC187 C - 1-SAT

https://atcoder.jp/contests/abc187/tasks/abc187_c

### タイプ
- set()

### 解説
問題文に忠実に従えば解ける問題。
要約すると、**文字列Sのなかに、頭に`!`がついた文字と`!`がついていない文字がどちらも存在したとき、ついていない方を出力する。**という問題。

`S`は重複なしでいいので、`set()`で文字を保存。これを一文字ずつループに入れていき、頭に`!`がついた文字があれば、ついていないものを`print()`して`exit()`。何もなければ、`'satisfiable'`を出力。

### 回答例
```python
# set()
N = int(input())
S = set(input() for _ in range(N))

for s in S:
    if '!' + s in S:
        print(s)
        exit()

print('satisfiable')
```

## ABC188 C - ABC Tournament

https://atcoder.jp/contests/abc188/tasks/abc188_c

### タイプ
- while
- （両端キュー）

### 解説
難しそうに書いてあるが、要は「トーナメントの準優勝の選手番号を出力してね」という問題。
今回は制約が緩いので、書いてあるとおりにやれば、ACできる問題。

トーナメントなので、2つずつ値を見ていく。`for i in range(len(result) // 2):`で、リストの半分の数だけループを回す。$2_i$番目と$2_i+1$番目を比べて、値が高い方をリスト`ans`に追加。これをもう一度`result`に入れ直して、再度ループを回す。決勝戦である`len(result) == 2`のときに`break`。準優勝者の値を`data`に参照し、index番号をとってくる。

また、両端キューでの実装も可能。

### 回答例
#### `while`で実装
```python
# while
N = int(input())
data = list(map(int, input().split()))

result = data

while True:
    if len(result) == 2:
        break

    ans = []

    for i in range(len(result) // 2):
        test = max(result[2*i], result[2*i+1])
        ans.append(test)

    result = ans

print(data.index(min(result))+1)
```

#### 両端キューで実装
```python
# 両端キュー
from collections import deque

N = int(input())
A = [-1] + [*map(int, input().split())]

stay = deque(range(1, 2 ** N + 1))

for _ in range(N-1):
    win = deque()
    while stay:
        left = stay.popleft()
        right = stay.popleft()
        if A[left] > A[right]:
            win.append(left)
        else:
            win.append(right)
    stay = win

left = stay.popleft()
right = stay.popleft()

if A[left] > A[right]:
    print(right)
else:
    print(left)
```

## ABC189 C - Mandarin Orange

https://atcoder.jp/contests/abc189/tasks/abc189_c

### タイプ
- 全探索
- （PyPyで実行）

### 解説
問題文を要約すると、**連続した皿から取れるみかんの合計の最大値はいくつですか、**ということ。

コードを上から順番に見ていこう。

まず、左端`l`を固定して、forで1ずつずらせるようにする。今回、条件が$l \leq r \leq N$となっているので、次のforは`l`から`N`までとする。

これらlからrの区間の最小値（みかんが取れる最小の数）を求め、`max()`で値が大きいものを保存していくというコードとなっている。

なお、このコードはPythonで実行してもTLEしてしまい通らない。したがって、実行速度の早いPyPyで提出する必要がある。（これがPythonのデメリット）

### 回答例
```python
# 全探索（PyPyで実行）
N = int(input())
A = [*map(int, input().split())]

ans = 0

# 左端をlで固定
# +1ずつ右にシフト
for l in range(N):
    init = 10 ** 6  # init > 10^5で初期化
    # l <= r <= Nを満たすようにループ
    for r in range(l, N):
        d = r - l + 1  # l-rの区間
        init = min(init, A[r])  # l-rの最小値
        score = init * d  # 最小のみかんの数、l-r区間の皿から取る
        ans = max(ans, score)  # 比較して多い方を取る

print(ans)

```

## 編集後記
185-189はそんなに難しくなかったという感覚。

「公式解説を見ても解説になっていない！」と思って始めました。
C100問解きのような、なにかの参考になれば幸いです。

＜参考文献＞
- https://qiita.com/u2dayo
- https://atcoder.jp/home

## 続きはこちら
https://qiita.com/uniTM/items/3e01fdc1477935ded3c4