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

A - Treasure Chest

問題ページ : A - Treasure Chest

考察

解き方はいろいろありそうですが、２つの"|"の位置を$l$, $r$とし"*"の位置を$pos$としたとき、$l\ <\ pos\ <\ r$を満たしているかで判定。

コード

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

考察

少し冗長ですが題意どおり、まず色$T$で判定してみて、色$T$がなければ色$C_1$で判定します。

コード

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

考察

"-"が先頭にある場合と末尾にある場合の両者を考えるのが少し面倒なため、Sを前後反転させたTを用意することで"-"が末尾にあるもののみを考えることにします。
この場合"-"の前にある"o"の連続する長さの最長値を求めることで解となります。

コード

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

考察

単調性はありませんが二分探索を用いると。いくつかあるかもしれない左側$0$、右側$1$の境界の一つを求めることができます。
インタラクティブな問題への対処ができれば実装は軽めでしょうか？。念のため$print$文に$flush = True$を付けます。

コード

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

考察

①頂点$p_i$から距離$d_i$未満の頂点は（頂点$p_i$を含めて）白でなければならない。
②それ以外の頂点は白である必要がないので黒にする。
③この状態で頂点$p_i$から距離$d_i$に黒頂点があるか確認する。
実装にはBFSを用いる。

コード

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以上は後日挑戦