AtCoderに登録したら解くべき過去問精選10問 #3【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

今回もAtCoder Beginners Selectionをpythonで解いていきます。

ABC085B - Kagami Mochi

問題文

X段重ねの鏡餅 (X≥1)とは、X枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。
例えば、直径 10、8、6センチメートルの餅をこの順に下から積み重ねると3段重ねの鏡餅になり、餅を一枚だけ置くと1段重ねの鏡餅になります。
ダックスフンドのルンルンは N枚の円形の餅を持っていて、そのうち i枚目の餅の直径はdiセンチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約

・1≤N≤100
・1≤di≤100入力値はすべて整数である。

解答例

# coding:utf-8
 
n = int(input())

s = [int(input()) for i in range(n)]

s.sort(reverse=True)

count = 1
d_now = s[0]

for i in range(n):
    if s[i] < d_now:
        d_now = s[i]
        count += 1

print(count)

解説

これも意味がわかりにくい問題でしたが、
直径の順にもちを重ねていくと（同じ直径のもちは除く）何段重ねになるかを求めました。
入力をリストsに格納しソートします。
一番大きなもち（s[0]）を初期値としてs[i]が現在のもちの直径（d_now）より小さければd_nowを更新し、count変数を1増加させました。

ABC085C - Otoshidama

atcoder.jp

問題文

日本でよく使われる紙幣は、10000円札、5000円札、1000円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N枚入っていて、合計でY円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約

・1≤N≤2000
・1000≤Y≤2×10^7
・Nは整数である。
・Yは1000の倍数である。

解答例

#python
# coding:utf-8
 
n,y = map(int,input().split(" "))

res10000 = -1
res5000 = -1
res1000 = -1

for a in range(n+1):
    for b in range(n-a+1):
        c = n - a - b
        total = 10000*a + 5000*b + 1000*c
        if total == y:
            res10000 = a
            res5000 = b
            res1000 = c

print(str(res10000) + " " + str(res5000) + " " + str(res1000))

解説

この問題も3重ループを使うと時間切れになるため、
問題文から千円札の枚数cは一万円札の枚数aと五千円札の枚数bが決まれば（成立するかは置いといて）求まります。
これで2重ループにすることで時間切れにならずに問題を解くことができます。

問題の難度があがるとプログラミングの技術はもちろんですが、
数学的に簡単に問題を解くことが要求されます。
いろいろな勉強を行うことがいい成績を残すうえで大事だと思いました。

精選10問のあとはこちらもおすすめ
ebisuke33.hatenablog.com

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

リンク