AtCoderに登録したら解くべき過去問精選10問 #2【Python解答例】
AtCoder Beginners Selectionという初心者向けの問題を今日も取り組みます。
ABC087B - Coins
問題文
あなたは、500円玉をA枚、100円玉をB枚、50円玉をC枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。
制約
・0≤A,B,C≤50
・A+B+C≥1
・50≤X≤20,000
・A,B,Cは整数である
・Xは50の倍数である
解答例
# coding:utf-8 a = int(input()) b = int(input()) c = int(input()) x = int(input()) counter = 0 for i in range(a+1): for j in range(b+1): for k in range(c+1): if 500 * i + 100 * j + 50 * k == x: counter += 1 print(counter)
解説
目標とするx円になる硬貨の組み合わせを求める問題です。
3重ループで3種類の硬貨の組み合わせを試し、xと一致すればcounter変数を増加させています。
初心者ゆえにfor分の範囲が(a+1)のように1を足さなければならないことがわからず、
めちゃくちゃ時間をかけて悩んでしまいました。
理論的にはあっているのに間違っている場合は、こんなミスがあったことを思い出したいです。
ABC083B - Some Sums
問題文
1以上 N以下の整数のうち、10進法での各桁の和が A以上 B以下であるものの総和を求めてください。
制約
・1≤N≤10^4
・1≤A≤B≤36
・入力はすべて整数である
解答例
# coding:utf-8 n,a,b = map(int, input().split(" ")) all_sum = 0 for i in range(n + 1): k = i total = 0 while k > 0: total += k % 10 k = k // 10 if total >= a and total <= b: all_sum += i print(all_sum)
解説
このあたりから変数の使い方がぐちゃぐちゃになってきました。
all_sumが求める答えで、totalが各桁の和です。
while文による各桁の和の求め方が勉強になりました。
ABC088B - Card Game for Two
問題文
N枚のカードがあります. i枚目のカードには, aiという数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.
制約
・Nは 1以上 100以下の整数
・ai (1≤i≤N)は 1以上 100以下の整数
解答例
# coding:utf-8 n = int(input()) a = list(map(int, input().split(" "))) a.sort(reverse=True) alice = 0 bob = 0 for i in range(n): if i % 2 == 0: alice += a[i] else: bob += a[i] print(alice - bob)
解説
問題文の意味を理解することが大変でしたが、
アリスから順番に場にある一番大きな数字が書かれたカードをとっていき、
最後にその得点差を競うゲームのようです。
sortを用いてリストを大きい数字の順に並び替え、
順番にアリスとボブに点数を足していきました。
徐々に難しい問題になると頭がこんがらがり、何をどうすればよいかわからなくなることがありました。
落ち着いて問題が解けるよう練習を続けたいです。
関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
精選10問のあとはこちらもおすすめ
ebisuke33.hatenablog.com
競技プログラミングの学習にはこちらの本もおすすめです。