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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 358

A問題：Welcome to AtCoder Land

A – Welcome to AtCoder Land

問題文(要約)

高橋君は AtCoder Land を目指しています。目の前に看板が置かれているので、ここが AtCoder Land であるかどうか判定したいです。

文字列 S,T が空白区切りで与えられます。 S= AtCoder かつ T= Land であるかどうか判定してください。

解答

# 入力された文字列を空白で分割し、SとTに代入
S, T = input().split()

# Sが'AtCoder'かつTが'Land'である場合
if S == 'AtCoder' and T == 'Land':
    # 条件を満たしている場合は'Yes'を出力
    print('Yes')
else:
    # 条件を満たしていない場合は'No'を出力
    print('No')

考え方）

問題の指示通り、S= AtCoder かつ T= Land　であるかを調べます。pythonで等しいかを判断するには、== (二つの等号記号)を使います。

コード詳細

input().split() を使って、入力された文字列を空白で分割し、変数 S と T にそれぞれ代入します。
if 文を使って、S が ‘AtCoder’ かつ T が ‘Land’ であるかどうかをチェックします。
- もし、条件が真（True）であれば、print(‘Yes’) を実行します。
- もし、条件が偽（False）であれば、print(‘No’) を実行します。

B問題：Ticket Counter

B – Ticket Counter

問題

AtCoder Land の入り口には 1 つのチケット売り場があり、来園客はこのチケット売り場の前に一列に並んで順にチケットを購入します。チケットの購入手続きには一人当たり A 秒かかり、列の先頭の人がチケットを購入し終わると、（存在すれば）次の人がすぐさま購入手続きを開始します。

現在チケット売り場に並んでいる人はおらず、今から N 人の人が順にチケットを買いに来ます。具体的には、i 番目の人は今から T_i 秒後にチケット売り場を訪れ、既に列が存在すればその最後尾に並び、存在しなければすぐさま購入手続きを開始します。ここで、T₁ < T₂ < ⋯ < T_N です。

各 i (1 ≤ i ≤ N) について、i 番目の人がチケットを購入し終わるのは今から何秒後か求めてください。

解答

# n: 人数, a: 1人あたりの購入時間を取得
n, a = map(int, input().split())
# 各人の到着時間をリストとして取得
T = list(map(int, input().split()))

# 最初の人がチケットを購入し終える時間を計算
time = T[0] + a
# 最初の人がチケットを購入し終える時間を出力
print(time)

# 2人目以降の人の購入時間を計算
for i in range(1, n):
    # 現在の時間が次の人の到着時間より大きい場合
    if time > T[i]:
        # 現在の時間に購入時間を加算
        time += a
    else:
        # 次の人の到着時間に購入時間を加算
        time = T[i] + a
    # 現在の時間を出力
    print(time)

考え方）

i番目の人が T[i] に購入時間の a を足した時間に次の購入者が訪れるかを確認し、次の対応を行います：

購入時間内に次の人が到着した場合は、現在の時間に購入時間を足す
購入時間内に次の人が到着しなかった場合は、到着時間に購入時間を足す

コード詳細

入力から N（人数）と A（一人あたりの購入時間）を取得します。
各人の到着時間をリストとして取得します。
最初の人がチケットを購入し終える時間を計算します。
- 到着時間 T[0] に購入時間 A を加算します。
最初の人の購入完了時間を出力します。
2人目以降の人の購入完了時間を計算します。
- 現在の購入完了時間が次の人の到着時間より大きい場合は、購入時間 A を加算します。
- 現在の購入完了時間が次の人の到着時間より小さい場合は、次の人の到着時間に購入時間 A を加算します。
各人の購入完了時間を順次出力します。

C問題：Popcorn

C – Popcorn

問題(要約)

AtCoder Land には N 個のポップコーン売り場があり、各売り場では M 種類の味のポップコーンが売られています。しかし、すべての売り場で全種類のポップコーンが売られているわけではありません。高橋君は全種類のポップコーンを食べたいですが、できるだけ少ない売り場を訪れたいです。高橋君が全種類のポップコーンを購入するために最低何個の売り場を訪れる必要があるかを求めてください。

解答

# n: ポップコーン売り場の数, m: ポップコーンの味の種類
n, m = map(int, input().split())

# 各売り場のポップコーンの販売状況をリストとして取得
S = [list(input()) for _ in range(n)]

# 訪れる必要がある最小の売り場数を無限大に初期化
ans = float('inf')

# 売り場の組み合わせを全探索するために2^n通りを試行
for i in range(2**n):
    # 各味のポップコーンが購入可能かをチェックするリスト
    popcorns = [0] * m
    # 訪れる売り場を記録するリスト
    stores = []
    # 各ビットに基づいて売り場を訪れるかどうかを決定
    for j in range(n):
        if i >> j & 1:
            stores.append(1)
        else:
            stores.append(0)

    # 訪れる売り場が決まったら、各味のポップコーンが購入可能かをチェック
    for k in range(n):
        if stores[k] == 1:
            for l in range(m):
                if S[k][l] == 'o':
                    popcorns[l] = 1
    # 全ての味のポップコーンが揃っているか確認
    if sum(popcorns) == m:
        # 最小の売り場数を更新
        ans = min(ans, sum(stores))

# 最終的な最小の売り場数を出力
print(ans)

解き方）

売り場の組み合わせを全探索は 2ⁿ 通り存在します。N, M の制約条件も N, M ≦ 10 と小さいため、全検索を行います。全ての通りの全検索にはbit全検索を用いるとことにより求めることができます。

解き方(詳細)：