初心者必見！40代サラリーマンが競プロでPythonチャレンジ【ABC322_A-C問題】

こんにちは、こんぶちゃ(茶コーダー)です！

初心者視点から競プロAtCoderのABC322のA問題〜C問題の自身の解答と解答説明をしていきます。

こんな人にオススメしたい

競技プログラミング初心者で、問題の解き方がわからない方
AtCoderの公式解説は読んだが、内容が理解できなかった方
Pythonでの解法を知りたい方

まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。

では早速行ってみましょう！

今回の参加コンテスト(ABC322)
感想

今回の参加コンテスト(ABC322)

AtCoder Beginner Contest 322

A問題：First ABC 2

A – First ABC 2

問題(要約)

与えられた文字列Sの中で、最初に(連続した)部分文字列としてABCが現れる位置（文字のインデックス）を求めるプログラムを書いてください。ABCが見つからない場合は-1を返してください。ABCの文字列はSの中で3文字連続で出現しなければなりません。

解答

# 入力から文字列の長さを取得
n = int(input())

# 文字列Sを取得
S = input()

# 文字列Sを順番に探索するループ
for i in range(len(S)):
    # もしS[i]が"A"であり、かつS[i+1]が"B"であり、かつS[i+2]が"C"であれば
    if (S[i] == "A") and ((i + 1 < n) and S[i + 1] == "B") and ((i + 2 < n) and S[i + 2] == "C"):
        # ABCが見つかった場合、その位置（1-indexed）を出力してプログラムを終了
        exit(print(i + 1))

# ABCが見つからなかった場合、-1を出力
print(-1)

入力の取得:
最初に、整数nを入力として受け取ります。これは文字列Sの長さです。次に、文字列Sを入力として受け取ります。
文字列Sを探索:
プログラムは文字列Sを一文字ずつ順番に調査します。forループを使って、文字列Sの各位置（インデックス）を順番に調べます。
ABCの出現チェック:
ループ内部で、次の条件を確認しています。
- S[i] == "A": Sのi番目の文字が”A”であること
- ((i + 1) < n) and S[i + 1] == "B": Sの(i + 1)番目の文字が”B”であること（ただし、文字列の最後に到達しないようにするための条件）
- ((i + 2) < n) and S[i + 2] == "C": Sの(i + 2)番目の文字が”C”であること（同様に、最後から2番目の位置までしか探索しないようにするための条件）
もし上記の条件がすべて満たされる場合、それは”ABC”が連続して出現していることを意味します。この場合、その位置（インデックスは０始まりのため1を加算）を出力してプログラムを終了します。
ABCが見つからない場合:
上記の条件を満たす場所がループ内で見つからない場合、最後に-1を出力してプログラムを終了します。

B問題：Prefix and Suffix

B – Prefix and Suffix

問題(要約)

SがTのどの部分とも一致しない場合は3を、それ以外の場合は、接頭辞であるか (1を出力)、接尾辞であるか (2を出力)、またはその両方であるか (0を出力) を判定し、それに応じた値を出力して下さい

解答

スライスを用いて接頭辞・接尾辞を判断していきます。

# 入力から整数nとmを取得
n, m = map(int, input().split())

# 文字列SとTを取得
S = input()
T = input()

# Tの最初のn文字がSと一致し、かつTの後ろからn文字がSと一致する場合
if T[:n] == S and T[-n:] == S:
    # SがTの接頭辞であり、かつ接尾辞でもあるので、0を出力してプログラムを終了
    exit(print(0))
# Tの最初のn文字と最後のn文字がSと一致しない場合
elif T[:n] != S and T[-n:] != S:
    # SがTの接頭辞でも接尾辞でもないので、3を出力してプログラムを終了
    exit(print(3))
# Tの最初のn文字がSと一致する場合
elif T[:n] == S:
    # SがTの接頭辞であるので、1を出力してプログラムを終了
    exit(print(1))
# Tの後ろからn文字がSと一致する場合
elif T[-n:] == S:
    # SがTの接尾辞であるので、2を出力してプログラムを終了
    exit(print(2))

以下詳細

入力の取得: 最初に、2つの整数nとmを入力として受け取ります。これはそれぞれ文字列SとTの長さです。次に、文字列SとTを入力として受け取ります。
接頭辞と接尾辞の一致をチェック:
判定条件 T[:n] == S は、Tの最初のn文字がSと一致することを確認します。同様に、条件 T[-n:] == S は、Tの最後のn文字がSと一致することを確認します。これらの条件を満たす場合、SはTの接頭辞であり、かつ接尾辞でもあるので、0を出力してプログラムを終了します。
接頭辞と接尾辞の一致がない場合の判定:
判定条件 T[:n] != S かつ T[-n:] != S は、Tの最初のn文字と最後のn文字がSと一致しないことを確認します。これらの条件を満たす場合、SはTの接頭辞でも接尾辞でもないので、3を出力してプログラムを終了します。
接頭辞のみまたは接尾辞のみの一致をチェック:
上記のどちらの条件も満たさない場合、残る可能性はTの接頭辞か接尾辞のどちらかだけがSと一致する場合です。どちらかの条件を満たす場合、それに応じてSはTの接頭辞または接尾辞であるので、それぞれ1または2を出力してプログラムを終了します。

C問題：Festival

C – Festival

問題(要約)

AtCoder 王国では、N日間のお祭りが開催されます。お祭りの最終日には花火が上がることが保証されています。各日（1日目からN日目まで）について、その日以降で初めて花火が上がるのは、何日後かを求めてください。ただし、その日に花火が上がる場合は0日後とします。

解答

与えられた日に花火が上がる情報を元に、各日について花火が上がるまでの日数を計算し、その日数を表示します。for文を組み合わせ、cntに日数を保持しています。

# 入力から整数nとmを取得
n, m = map(int, input().split())

# 花火が上がる日をリストとして取得
A = list(map(int, input().split()))

# 花火が上がる日を示すリストfirework_daysを初期化する（0は花火が上がらない、1は花火が上がることを示す）
firework_days = [0] * n

# Aに含まれる日に花火が上がることを示すフラグを立てる
for a in A:
    firework_days[a - 1] = 1

# 現在のカウントを初期化
cnt = 0

# 各日について、花火が上がるまでの日数を計算する
for i in range(n):
    if cnt != 0:
        # カウントがゼロでない場合、カウントを表示して1減らす
        print(cnt)
        cnt -= 1
    elif firework_days[i] == 1:
        # 当日に花火が上がる場合、0を表示
        print(0)
    else:
        # 当日に花火が上がらない場合、その後の日数を計算する
        cnt = 1
        for j in range(i + 1, n):
            if firework_days[j] == 1:
                break
            else:
                cnt += 1
        # 花火が上がるまでの日数を表示して1減らす
        print(cnt)
        cnt -= 1

以下詳細

入力を取得する:
最初に、整数nとmを入力として受け取ります。これは日数と花火が上がる日数を示します。次に、m個の整数を入力として受け取り、花火が上がる日を示すリストAを作成します。
花火が上がる日を示すフラグを立てる:
リストfirework_daysを用意し、花火が上がる日を示す場所に対応するインデックスを1に設定します。Aの各要素に対して、その日が花火が上がる日であることを示すフラグを立てます。
各日について花火が上がるまでの日数を計算する:
- ループを使って、各日について以下の条件を確認します：
  - もしカウントcntが0でない場合、cntを表示して1減らします。これは、花火が上がる日までの日数を表します。
  - もし当日に花火が上がる日であれば、0を表示します。
  - それ以外の場合、当日から始まる花火が上がるまでの日数cntを計算します。次の日から順番に、花火が上がらない日が続く限りcntを増やしていきます。花火が上がる日が見つかったらループを抜け、cntを表示して1減らします（当日は0日後なので）。