見出し画像

[ABC299 Python]東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 299）A～D問題Python解説

Kai

A問題

# 入力
N = int(input())
S = input()
# "｜"の場所
vertical_bar = []
# "*"の場所
asterisk = 0

for i in range(N):
    # S[i]が"|"ならその場所をvertical_barに追加
    if S[i] == "|":
        vertical_bar.append(i)
    # S[i]が"*"ならその場所をasteriskに追加
    elif S[i] == "*":
        asterisk = i

# "|"の2か所vertical_bar[0]とvertical_bar[1]の間に、
# *の場所asteriskがあれば"in"と出力する
if vertical_bar[0] < asterisk < vertical_bar[1]:
    print("in")
else:
    print("out")

2か所の"|"と1か所の"*"の場所を保持し、
場所の関係が、"|" < "*" < "|"
となっていれば、”in”と出力する。

B問題

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

# 色がTであるプレイヤー
playerT = set()
# 色がプレイヤー1と同じであるプレイヤー
player1 = set()
# プレイヤー1の色
color1 = C[0]

for i in range(N):
    # 色がTである場合、そのプレイヤーの値をplayerTに追加
    if C[i] == T:
        playerT.add(R[i])
    # 色がcolor1である場合、そのプレイヤーの値をplayer1に追加
    elif C[i] == color1:
        player1.add(R[i])
        
# 色Tのプレイヤーがいない場合、player1の中から、
# 最大の値を持ったプレイヤーの番号を出力
if playerT == set():
    print(R.index(max(player1))+1)
# 色Tのプレイヤーがいる場合、playerTの中から、
# 最大の値を持ったプレイヤーの番号を出力
else:
    print(R.index(max(playerT))+1)

初めに色がTであるプレイヤー、色がプレイヤー1と同じプレイヤーの値を保持し、
その中で最大の値を持つプレイヤーの番号を最後に出力します。

C問題

# 入力
N = int(input())
S = list(input())
# 連続する"o"を数える変数c
c = 0
# 最大連続"o"を表す変数ans
ans = 0

for i in range(N):
    # S[i]が"o"だったら、c+=1
    if S[i] == "o":
        c += 1
    # "o"でなければ、ansを更新し、c=0とする
    else:
        ans = max(ans, c)
        c = 0

ans = max(ans, c)
# Sの中身が全て"o"または"-"である、つまり、
# 種類数が1の場合、ダンゴ文字列は存在しないので、-1を出力
if len(set(S)) == 1:
    print(-1)
# それ以外の時はだんご文字列の最大長さansを出力する
else:
    print(ans)

考えられる文字列をすべて考えるとTLEになります。
ダンゴ文字列の特徴として、
長さL+1のうち、"o"がL個連続します。
なので、"o"が連続しているところを探し、
その両端が"-"であるかどうかを確認することで求めていきます。

では、Sの中にダンゴ文字列が含まれない場合にはどのような場合があるか、
答えは全て"o"または全て"-"の時です。
それ以外の時は、Sにダンゴ文字列が含まれます。

D問題

# 入力
N = int(input())
# 二分探索する範囲を指定
left = 1
right = N
# leftとrightが隣同士になるまで
while right - left > 1:
    # 二分探索
    mid = (left+right)//2
    print("?", mid)
    S = input()
    # 入力された値が0であれば、midよりも右側を探索
    if S == "0":
        left = mid
    # 入力された値が1であれば、midよりも左側を探索
    else:
        right = mid
# 隣り合うleftとrightのうち、leftを出力
print("!", left)

2023/04/27追記しました。

20回までしか尋ねることができないので、
工夫して作成することが必要です。

題意より、
S[1]=0、S[N]=1であることが分かっています。
ここで二分探索の要領でS[N//2]を調べてみます。
S[N//2]=0の場合、
S[1]～S[N//2]までは全て0の可能性がありますが、
S[N//2]～S[N]までが全て0の可能性はありません。
(S[N]が1だからです。)
そのため、次はS[N//2]～S[N]だけを調べればいいのです。

同様に考えると、
S[N//2]=1の場合、
S[1]～S[N//2]だけを調べることになります。
これを繰り返していくとやがて
S[i]～S[i+1]を調べればいい、
つまり隣り合うときが出てきます。
この時、隣り合う2つの要素には
0と1が両方含まれているので、
条件を満たし答えを出力できます。

では、本当に20回で間に合うのか、最大値で試してみましょう。
問題文の条件より、
2<=N<=2*10**5
と記載があるため、
N<=2*105<2**20=1048576
なので十分間に合います。

この記事が気に入ったらサポートをしてみませんか？