ABC299 回想・解説(Python)

Thumbnail

目次

前提

AtCoder Biginner Contest299のPythonの解答コードです。

雑談

ABC298, ABC299と二回続けて、AtCoderのサイトがDDos攻撃を受けたため、unratedのコンテストになっている。

コンテスト開催のタイミングでDDoS攻撃されているので、AtCoder社を明確に攻撃する意思があるのだろう。

DDoS攻撃に負けずに今後とも健全なコンテストを開催してほしいと思う。

A - Treasure Chest

問題文通りに実装する。for文を使って判定してもいい。以下は正規表現を使って判定している。問題分から「*」は一文字ということはわかっているが、念のために「*」が一文字以上あればTrueという判定にしている。

import re 

N = int(input())
S = input()
print("in" if re.search(r"\|.*\*+.*\|", S) else "out")

B - Trick Taking

初めにTが含まれるかを判定している。含まれない場合にはC[0]をTにしておけば、後続の処理を統一することができる。

N, T = map(int, input().split())
C = list(map(int, input().split()))
R = list(map(int, input().split()))

ans = 0
if T not in C:
    T = C[0]
    ans = 1
tmp = 0
for i, c in enumerate(C, start=1):
    if c == T and R[i - 1] > tmp:
        ans = i
        tmp = R[i - 1]

print(ans)

C - Dango

割と問題文の通り実装する。コーナーケースなどに気を付ける。

N = int(input())
S = input()

ans = -1
cnt = 0
flag = False
for s in S:
    if s == "o":
        cnt += 1
    else:
        ans = max(ans, cnt)
        cnt = 0
        flag = True
if flag:
    ans = max(ans, cnt)
print(ans if ans > 0 else -1)

D - Find by Query

解説AC。

二分探索で0と1がとなりあっている箇所を見つける。

中間の値（コードではmid）が0であれば、midからRまでの間に必ず0と1が隣接する箇所が存在する（Nが1のため）。midが1であれば逆にLからmidまでの間にある。それを二分探索で繰り返すと隣接する箇所を見つけることができる

def interactive(x):
    print("?", x)
    return int(input())


N = int(input())

L, R = 1, N - 1

while L < R:
    mid = (L + R + 1) // 2
    out = interactive(mid)
    if out == 0:
        L = mid
    else:
        R = mid - 1
print("!", L)