【ABC338】競プロのA-C問題を40代サラリーマンがPython解説！初心者にもわかりやすく

AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 338

A問題：Capitalized?

A – Capitalized?

問題文

英大文字・英小文字からなる空でない文字列 S が与えられます。以下の条件が満たされているか判定してください。

  • S の先頭の文字は大文字であり、それ以外の文字はすべて小文字である。

解答

# reモジュールをインポートします。これは、正規表現を扱うためのモジュールです。
import re

# 入力された文字列がパターンに一致するかどうかをチェックし、一致すれば"Yes"、そうでなければ"No"を出力します。
print("Yes" if re.match('^[A-Z][a-z]*$', input()) else "No")

考え方）

先週に正規表現を覚えたので、正規表現を用いて解いていきます。

  1. import re：この行で、正規表現を使うためのreモジュールをインポートします。
  2. re.match('^[A-Z][a-z]*$', input())：
    • match 関数は、文字列が正規表現のパターンと完全に一致するかどうかを試みます。
    • パターン ^[A-Z][a-z]*$ は以下のように解釈されます：
      • ^ は文字列の開始を表します。
      • [A-Z] は最初の文字が大文字のアルファベット（AからZ）であることを要求します。
      • [a-z]* は、それに続く0文字以上の小文字のアルファベット（aからz）を許容します。アスタリスク * は、「直前の要素の0回以上の繰り返し」を意味します。
      • $ は文字列の終了を表します。
    • input() はユーザーからの入力文字列を取得し、パターンとの一致を試みます。
  3. 三項演算子（"Yes" if 条件 else "No"）は、re.match() 関数がマッチを見つけたかどうかをチェックします。パターンが入力文字列全体と一致すれば、条件は真となり "Yes" を返し（文字列が指定された条件を満たすことを示す）、そうでなければ "No" を返します。

B問題：Frequency

B – Frequency

問題

英小文字からなる文字列 S が与えられます。S に最も多く出現する文字を求めてください。そのような文字が複数ある場合は、そのうちアルファベット順で最も早いものを答えてください。

解答

# 英小文字に対応するカウンターのリストを初期化します。26文字分の0を持つリストです。
word_num = [0] * 26

# 入力された文字列の各文字に対してループを行います。
for s in input():
    # 入力された文字のASCIIコードから97を引くことで、'a'を0としたインデックスに変換し、その文字のカウントを1増やします。
    word_num[ord(s)-97] += 1

# word_numリストの中で最大値を持つ要素のインデックスを見つけ、それに97を加えてASCIIコードに戻し、対応する文字に変換して出力します。
print(chr(word_num.index(max(word_num)) + 97))

解き方）

英文字分のカウンターリストを用意するところがポイントです。

  1. カウンターリストの初期化：word_num = [0] * 26 この行で、英小文字（26文字）それぞれの出現回数をカウントするためのリストを0で初期化します。リストの各要素は、'a' から 'z' までの文字に対応しています。
  2. 文字列の各文字に対するループ：入力された文字列 S の各文字 s に対してループを行い、その文字の出現回数をカウントします。
  3. 文字のカウント：word_num[ord(s)-97] += 1 この行で、文字 s のASCIIコードから97を引くことで、'a' を0としたインデックスを計算し、そのインデックスに対応するカウンターを1増やします。
  4. 最も多く出現する文字の特定：chr(word_num.index(max(word_num)) + 97) ここでは、word_num リスト内の最大値を持つ要素のインデックスを見つけ出し（複数ある場合、index 関数は最初に見つかったインデックスを返すため、自動的にアルファベット順で最も早い文字が選ばれます）、それに97を加えることでASCIIコードに戻し、最終的に chr 関数を使用して対応する文字に変換します。

C問題：Leftover Recipes

C – Leftover Recipes

問題

冷蔵庫に N 種類の材料があります。これらを材料 1、…、材料 N と呼びます。材料 i は Qi​グラムあります。

あなたは 2 種類の料理を作れます。料理 A は、1 人分を作るのに各材料 i (1≤i≤N) が Ai​グラム必要です。料理 B は、1 人分を作るのに各材料 i が Bi​ グラム必要です。どちらも整数人分しか作れません。

冷蔵庫にある材料のみを使って、最大で合計何人分の料理を作れますか。

解答

n = int(input())  # 材料の種類数
Q = list(map(int, input().split()))  # 各材料の量
A = list(map(int, input().split()))  # 料理Aに必要な量
B = list(map(int, input().split()))  # 料理Bに必要な量

minA = float('inf')  # 料理Aの最大人数を初期化

# 料理Aの最大人数を計算
for i in range(n):
    if A[i] != 0:
        minA = min(minA, Q[i] // A[i])

ans = 0  # 最終的な最大人数
# 料理Aを0人からminA人まで作る場合を試す
for i in range(minA + 1):
    minB = float('inf')  # 料理Bの最大人数を初期化
    # 料理Bの最大人数を計算
    for k in range(n):
        if B[k] != 0:
            minB = min(minB, (Q[k] - i * A[k]) // B[k])
    ans = max(ans, i + minB)  # 最大人数を更新

print(ans)  # 結果を出力


解き方）

２つの材料に同時に変数として扱ってしまうと、106 x 106 x N と非常に莫大な計算が必要になります。そのため、下記のステップで解いています。

  1. 料理 A の最大人数計算: 全材料に対して、料理 A を作るために必要な量で割り、その最小値を求めます。これは、料理 A を最大何人分作れるかの上限を示します。
  2. 料理 A と B の組み合わせ探索: 0人から minA 人まで料理 A を作った場合に、残りの材料で料理 B を最大何人分作れるかを計算し、その最大値を求めます。
    • このステップでは、料理 A を特定の人数分作った後の残りの材料を考慮して、料理 B を作ることができる人数を計算します。

下記がコードの詳細です。

  1. 入力の受け取り
  2. 料理 A の最大人数の計算
    • 各材料について、料理Aを作るのに必要な量でその材料の量を割り、その商の最小値を求めます。これが、料理Aを作れる最大人数です。
    • ここで、minAを無限大で初期化し、各材料に対して計算した最小人数で更新していきます。
  3. 料理 A と B の組み合わせの探索
    • 0人からminA人まで料理Aを作る各ケースについて、残りの材料で作れる料理Bの最大人数を計算します。
    • 料理Aを特定の人数作ると決めた上で、残った材料を使って料理Bを作るケースを考慮します。この時、各材料から既に使用した分を引いた残量で、料理Bを何人分作れるかを計算し、その最小値を求めます。
    • 各ケースについて、料理AとBの合計人数が最大となる組み合わせを見つけ出し、その最大値をansに保持します。
  4. 結果の出力
    • 計算した最大人数ansを出力します。

感想

今回はB問題までしか解けませんでしたが、A問題では先週覚えたばかりの正規表現を実践できたのが楽しかったです。何か新しいことを学んで、それを実際に使えるというのは本当にワクワクしますね。

B問題では、アルファベットのカウンターリストを使用して解決しました。同じ文字カウントの問題で、アルファベット順を意識する必要があるため、工夫が必要でしたが、無事解決できて満足しています。

C問題に関しては、コンテスト中に二分探索を試みましたが、サンプルは通過できたものの、全てのテストケースで正解には至りませんでした。二分探索に関する深い理解がまだ足りませんでした。上記の回答コードにおいては、AtCoderの解説を参考にしたものの、最小値と最大値をどのように扱うかが重要で、この点でつまずいてしまいました。コードの知識と数学の知識を併せ持ったこのような問題を解けるようになっていきたいです。

2024年に入ってからは少し苦戦しており、順位も523位まで下がってしまいました。しかし、過去に出た似た問題を間違えずに解けるようになることを目標にしています。

それでは、皆さんも競プロライフを楽しんでくださいね！(*＾▽＾)／

コメント

タイトルとURLをコピーしました