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

AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 331

A問題:Tomorrow

A – Tomorrow

問題文

AtCoder 国の暦では、1 年は 1 月から M 月までの M ヶ月からなり、どの月も 1 日から D 日までの D 日からなります。

AtCoder 国の暦で y 年 m 月 d 日の翌日は何年何月何日であるか求めてください。

解答

# 月と日の上限を取得
M, D = map(int, input().split())

# 現在の年月日を取得
y, m, d = map(int, input().split())

# 現在の日付が翌日の月末日を超える場合の処理
if d + 1 > D:
    d = 1  # 日付を1日にリセット

    # 現在の月が翌月を超える場合の処理
    if m + 1 > M:
        m = 1  # 月を1月にリセット
        y += 1  # 年を翌年に増やす
    else:
        m += 1  # 月を翌月に増やす
else:
    d += 1  # 現在の日付が翌日の月末日を超えない場合、日を1日増やす

# 結果を出力
print(y, m, d)

解き方)

  1. 入力の取得:
    • M, D = map(int, input().split()): 月の上限 M と日の上限 D を取得します。
    • y, m, d = map(int, input().split()): 現在の年月日 y, m, d を取得します。
  2. 日付の計算:
    • if d + 1 > D:: 現在の日 d に1を加えた結果が月の上限 D を超える場合の条件分岐です。
      • d = 1: 日を1日にリセットします。
      • if m + 1 > M:: 現在の月 m に1を加えた結果が年の上限 M を超える場合の条件分岐です。
        • m = 1: 月を1月にリセットします。
        • y += 1: 年を翌年に増やします。
      • else:: 月が年の上限を超えない場合、単に月を1月増やします。
    • else:: 現在の日 d に1を加えた結果が月の上限 D を超えない場合、単に日を1日増やします。
  3. 結果の出力:
    • print(y, m, d): 計算された結果を出力します。

B問題:Buy One Carton of Milk

B – Buy One Carton of Milk

問題

スーパーマーケットで卵のパックが売られています。

卵 6 個入りのパックは S 円、卵 8 個入りのパックは M 円、卵 12 個入りのパックは L 円です。

どのパックも何パックでも購入できるとき、N 個以上の卵を買うために必要な最小の金額を求めてください。

解答

# 各卵パックの個数と価格を入力
N, S, M, L = map(int, input().split())

# 初期値として無限大を設定
ans = float('inf')

# 6個、8個、12個入りの卵パックを組み合わせて購入する
for i in range(102//6 + 1):
    for j in range(102//8 + 1):
        for k in range(102//12 + 1):
            # 現在の卵の総数を計算
            egg_cnt = i*6 + j*8 + k*12
            if egg_cnt >= N:
                # 現在の卵の組み合わせにおける金額を計算
                yen = i * S + j * M + k * L
                # 最小の金額を更新
                ans = min(ans, yen)

# 答えを出力
print(ans)

解き方)

  1. 入力の取得:
    • N, S, M, L = map(int, input().split()): 卵の総数 N と各卵パックの価格 S, M, L を取得します。
  2. 卵の組み合わせの計算:
    • 3つのループを使用して、6個入り、8個入り、12個入りの卵パックをそれぞれ i, j, k 個購入する場合を考えます。
    • egg_cnt = i*6 + j*8 + k*12: 各卵パックの個数を合算して、現在の卵の総数を計算します。
  3. 最小金額の計算:
    • if egg_cnt >= N:: 現在の卵の総数が目標個数以上になった場合、金額を計算します。
    • yen = i*S + j*M + k*L: 各卵パックを購入する際の金額を計算します。
  4. 最小金額の更新:
    • ans = min(ans, yen): 現在の金額がこれまでの最小金額よりも小さい場合、ans を更新します。
  5. 結果の出力:
    • print(ans): 最終的な最小金額 ans を出力します。

C問題:Sum of Numbers Greater Than Me

C – Sum of Numbers Greater Than Me

問題

長さ N の数列 A=(A1​,…,AN​) が与えられます。

i=1,…,N のそれぞれについて次の問題を解いてください。

問題:A の要素のうち Ai より大きな要素全ての和を求めよ。

解答

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

# 数列 A を取得
A = list(map(int, input().split()))

# 各要素のインデックスと値を辞書にまとめる
indexed_dict = {index: value for index, value in enumerate(A)}

# 値で降順にソートされた (インデックス, 値) のタプルのリストを取得
sorted_indexed_dict = sorted(indexed_dict.items(), key=lambda x: x[1], reverse=True)

# 答えを格納するリストを初期化
ans = [0] * n

# 一時変数の初期化
tmpV = sorted_indexed_dict[0][1]
tmpSum = 0
accum = 0

# ソートされたリストを順に処理
for i, v in sorted_indexed_dict:
    # 現在の値が一時変数と等しい場合
    if tmpV == v:
        ans[i] = tmpSum
        accum += v
    # 現在の値が一時変数より小さい場合
    elif tmpV > v:
        tmpSum = accum
        ans[i] = tmpSum
        accum += v

    # 一時変数を更新
    tmpV = v

# 答えを出力
print(*ans)


解き方)

  1. 数列の入力:
    • n = int(input()): 数列の長さを取得します。
    • A = list(map(int, input().split())): 数列 A を取得します。
  2. 数列の要素とインデックスを辞書にまとめる:
    • indexed_dict = {index: value for index, value in enumerate(A)}: 各要素のインデックスと値を辞書にまとめます。
  3. 値で降順にソートされた (インデックス, 値) のタプルのリストを作成:
    • sorted_indexed_dict = sorted(indexed_dict.items(), key=lambda x: x[1], reverse=True): 値で降順にソートされた (インデックス, 値) のタプルのリストを作成します。
  4. 各要素について処理:
    • for i, v in sorted_indexed_dict:: ソートされたリストを順に処理します。
    • if tmpV == v:: 現在の値が一時変数と等しい場合、その値を答えのリストに格納し、累積を更新します。
    • elif tmpV > v:: 現在の値が一時変数より小さい場合、一時変数を更新し、その値を答えのリストに格納し、累積を更新します。
  5. 結果の出力:
    • print(*ans): 最終的な答えのリストを出力します。

感想

なんとかC問題まで解けました!B問題で予想外の難しさに苦戦しましたが、最終的には克服できました!^^ !

B問題は、ネスト構造に関する問題でした。最初は範囲を100までで考えてしまい、コーナーケースで不正解(WA)になりました。何が悪いのか理解できず、、、。B問題をきっぱりと後回しにしてC問題に切り替えました。C問題回答後に、範囲を増やして対応することでやっと正解 (AC) になりました。

C問題も難航しました。愚直に解くとTLE(制限時間超過)になることがわかり、インデックスを保持したリストとその並び替えを使うことで、繰り返しの数を減らすことができました。時間はかかりましたが、一発で正解 (AC) を取れました。

B問題が解けずに非常に焦りましたが、問題の順番を変え、深みにハマらずに済んだことで、問題の解き方や習熟度が向上したと感じます。

Ratingは維持できました(554点)。来週も引き続き頑張ります!

それでは、良い競プロライフを~!(*^▽^)/

コメント

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