【Atcoder解法検討】ABC299 A~E Python

## A - Treasure Chest 
#### 問題ページ : [A - Treasure Chest](https://atcoder.jp/contests/abc299/tasks/abc299_a)
### 考察
解き方はいろいろありそうですが、２つの"|"の位置を$l$, $r$とし"*"の位置を$pos$としたとき、$l\ <\ pos\ <\ r$を満たしているかで判定。
### コード
```python
N = int(input())
S = input()

kakoi = []
pos = -1
for i in range(N):
    if S[i] == "|":
        kakoi.append(i)
    if S[i] == "*":
        pos = i

print("in" if kakoi[0] < pos < kakoi[1] else "out")
```

## B - Trick Taking
#### 問題ページ : [B - Trick Taking](https://atcoder.jp/contests/abc299/tasks/abc299_b)
### 考察
少し冗長ですが題意どおり、まず色$T$で判定してみて、色$T$がなければ色$C_1$で判定します。
### コード
```python
N, T = map(int, input().split())
C = list(map(int, input().split()))
R = list(map(int, input().split()))

player = -1
max_score = -1
for i in range(N):
    if C[i] == T and R[i] > max_score:
        player = i + 1
        max_score = R[i]

if player != -1:
    print(player)
    exit()

T = C[0]
for i in range(N):
    if C[i] == T and R[i] > max_score:
        player = i + 1
        max_score = R[i]

print(player)
```

## C - Dango
#### 問題ページ : [C - Dango](https://atcoder.jp/contests/abc299/tasks/abc299_c)
### 考察
"-"が先頭にある場合と末尾にある場合の両者を考えるのが少し面倒なため、Sを前後反転させたTを用意することで"-"が末尾にあるもののみを考えることにします。
この場合"-"の前にある"o"の連続する長さの最長値を求めることで解となります。
### コード
```python
N = int(input())
S = list(input())
T = list(reversed(S))

cnt = 0
ans  = 0
for i in range(N):
    if S[i] == "o":
        cnt += 1
    elif S[i] == "-":
        ans = max(ans, cnt)
        cnt = 0

cnt = 0
for i in range(N):
    if T[i] == "o":
        cnt += 1
    elif T[i] == "-":
        ans = max(ans, cnt)
        cnt = 0

if ans == 0:
    print(-1)
else:
    print(ans)
```

## D - Find by Query
#### 問題ページ : [D - Find by Query](https://atcoder.jp/contests/abc299/tasks/abc299_d)
### 考察
単調性はありませんが二分探索を用いると。いくつかあるかもしれない左側$0$、右側$1$の境界の一つを求めることができます。
インタラクティブな問題への対処ができれば実装は軽めでしょうか？。念のため$print$文に$flush = True$を付けます。
### コード
```python
N = int(input())
l = 1   # 0
r = N   # 1

while r - l > 1:
    m = (l + r) // 2
    print("?", m, flush = True)

    judge = int(input())
    if judge == 1:
        r = m
    else:
        l = m

print("!",l, flush = True)
```

## E - Nearest Black Vertex
#### 問題ページ : [E - Nearest Black Vertex](https://atcoder.jp/contests/abc130/tasks/abc130_e)
### 考察
①頂点$p_i$から距離$d_i$未満の頂点は（頂点$p_i$を含めて）白でなければならない。
②それ以外の頂点は白である必要がないので黒にする。
③この状態で頂点$p_i$から距離$d_i$に黒頂点があるか確認する。
実装にはBFSを用いる。
### コード
```python
from collections import deque

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)
K = int(input())
PD = [tuple(map(int, input().split())) for _ in range(K)]


ans = [-1] * N  # -1:未決定、0:白、1:黒

        
# 確実に白な頂点
for p,d in PD:
    Q = deque()
    Q.append(p-1)
    v = [-1] * N
    v[p-1] = 0
    while len(Q) > 0:
        x = Q.popleft()
        if v[x] >= d:continue
        ans[x] = 0
        for nx in G[x]:
            if v[nx] != -1:continue
            v[nx] = v[x] + 1
            Q.append(nx)

#　確実に白な頂点以外は黒にする
for i in range(N):
    if ans[i] == -1:
        ans[i] = 1

# この時点で黒頂点がなければ"No"
if ans == [0] * N:
    print("No")
    exit()

# 指定距離の黒頂点が存在するか確認する
for p,d in PD:
    is_black = False
    Q = deque()
    Q.append(p-1)
    v = [-1] * N
    v[p-1] = 0
    while len(Q) > 0:
        x = Q.popleft()
        if v[x] == d and ans[x] == 1:
            is_black = True
        if v[x] >= d:continue
        for nx in G[x]:
            if v[nx] != -1:continue
            v[nx] = v[x] + 1
            Q.append(nx)
    if is_black == False:
        print("No")
        exit()

print("Yes")
str_ans = ""
for a in ans:
    str_ans += str(a)
print(str_ans)

```

青色diff以上は後日挑戦