こんにちは、こんぶちゃ(茶コーダー)です!
初心者視点から競プロAtCoderのABC331のA問題〜C問題の自身の解答と解答説明をしていきます。
まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援&ご助言頂けば嬉しいです。
では早速行ってみましょう!
今回の参加コンテスト(ABC331)
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)
解き方)
- 入力の取得:
M, D = map(int, input().split())
: 月の上限M
と日の上限D
を取得します。y, m, d = map(int, input().split())
: 現在の年月日y, m, d
を取得します。
- 日付の計算:
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日増やします。
- 結果の出力:
print(y, m, d)
: 計算された結果を出力します。
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)
解き方)
- 入力の取得:
N, S, M, L = map(int, input().split())
: 卵の総数N
と各卵パックの価格S, M, L
を取得します。
- 卵の組み合わせの計算:
- 3つのループを使用して、6個入り、8個入り、12個入りの卵パックをそれぞれ
i
,j
,k
個購入する場合を考えます。 egg_cnt = i*6 + j*8 + k*12
: 各卵パックの個数を合算して、現在の卵の総数を計算します。
- 3つのループを使用して、6個入り、8個入り、12個入りの卵パックをそれぞれ
- 最小金額の計算:
if egg_cnt >= N:
: 現在の卵の総数が目標個数以上になった場合、金額を計算します。yen = i*S + j*M + k*L
: 各卵パックを購入する際の金額を計算します。
- 最小金額の更新:
ans = min(ans, yen)
: 現在の金額がこれまでの最小金額よりも小さい場合、ans
を更新します。
- 結果の出力:
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)
解き方)
- 数列の入力:
n = int(input())
: 数列の長さを取得します。A = list(map(int, input().split()))
: 数列 A を取得します。
- 数列の要素とインデックスを辞書にまとめる:
indexed_dict = {index: value for index, value in enumerate(A)}
: 各要素のインデックスと値を辞書にまとめます。
- 値で降順にソートされた (インデックス, 値) のタプルのリストを作成:
sorted_indexed_dict = sorted(indexed_dict.items(), key=lambda x: x[1], reverse=True)
: 値で降順にソートされた (インデックス, 値) のタプルのリストを作成します。
- 各要素について処理:
for i, v in sorted_indexed_dict:
: ソートされたリストを順に処理します。if tmpV == v:
: 現在の値が一時変数と等しい場合、その値を答えのリストに格納し、累積を更新します。elif tmpV > v:
: 現在の値が一時変数より小さい場合、一時変数を更新し、その値を答えのリストに格納し、累積を更新します。
- 結果の出力:
print(*ans)
: 最終的な答えのリストを出力します。
感想
なんとかC問題まで解けました!B問題で予想外の難しさに苦戦しましたが、最終的には克服できました!^^ !
B問題は、ネスト構造に関する問題でした。最初は範囲を100までで考えてしまい、コーナーケースで不正解(WA)になりました。何が悪いのか理解できず、、、。B問題をきっぱりと後回しにしてC問題に切り替えました。C問題回答後に、範囲を増やして対応することでやっと正解 (AC) になりました。
C問題も難航しました。愚直に解くとTLE(制限時間超過)になることがわかり、インデックスを保持したリストとその並び替えを使うことで、繰り返しの数を減らすことができました。時間はかかりましたが、一発で正解 (AC) を取れました。
B問題が解けずに非常に焦りましたが、問題の順番を変え、深みにハマらずに済んだことで、問題の解き方や習熟度が向上したと感じます。
Ratingは維持できました(554点)。来週も引き続き頑張ります!
それでは、良い競プロライフを~!(*^▽^)/
コメント