ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

AtCoderに登録したら解くべき過去問精選10問 #2【Python解答例】

AtCoder Beginners Selectionという初心者向けの問題を今日も取り組みます。

ABC087B - Coins

atcoder.jp

問題文

あなたは、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

atcoder.jp

問題文

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

atcoder.jp

問題文

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



競技プログラミングの学習にはこちらの本もおすすめです。