Atcoder Beginners Selection コード解説[2]

記事の目的

　Atcoderの初心者向けの課題である「Atcoder Beginners Selection」のB問題のコードを解説していきます。　より良い解法など、コメントお待ちしております。

ABC081B - Shift only

問題文

黒板に N 個の正の整数 A1, ..., AN が書かれています．すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．黒板に書かれている整数すべてを，2 で割ったものに置き換える．すぬけ君は最大で何回操作を行うことができるかを求めてください．

　つまり与えられた整数すべてが偶数なら、それらを２で割るのを繰り返していき、それが何回までできるか、ということですね。

n = int(input())
list_a = input().split(" ")
int_list_a = list(map(int, list_a))
cnt = 0
flag = True
while flag == True:
    for i in range(len(int_list_a)):
        if int_list_a[i] % 2 != 0:
            flag = False
        else:
            int_list_a[i] = int_list_a[i] / 2
    if flag == True:
        cnt += 1
print(cnt)

　コードはこうなりました。（自分でも正直もっと冴えたやり方がありそうだと感じてる…）　まずすべての整数に対して2で割れるかどうかの判定をして、可能であれば２で割った後にその回数をカウントしています。

ABC087B - Coins

問題文

あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。　　各効果の組み合わせを全探索して、条件に一致した回数をカウントしました。今回は効果の種類が３種類なので３重ループになりましたが、テストケースによっては計算量の関係でタイムアウトする可能性もありますね…。

a = int(input())
b = int(input())
c = int(input())
x = int(input())
cnt = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if x == 500*i + 100*j + 50*k:
                cnt += 1
print(cnt)

　コードはシンプルに書けました。

ABC083B - Some Sums

問題文

1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。

　1以上N以下のすべての整数について、各桁の和を計算して、それがA以上B以下であるものの個数をカウントする、という流れで進めていきます。

n, a, b = map(int, input().split(" "))
cnt = 0
for i in range(1, n+1):
    i_list = [int(a) for a in str(i)]
    if sum(i_list) >= a and sum(i_list) <= b:
        cnt += i
print(cnt)

　list()メソッドで文字列を簡単に分割できるので、pythonですっきり実装できましたね。

ABC088B - Card Game for Two

問題文

N 枚のカードがあります. i 枚目のカードには, aiという数が書かれています. Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります. 2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

　「最適な戦略」というのが難しく聞こえますが、要は数字の大きいカードを交互に取っていくだけです。

n = int(input())
a_list = list(map(int, input().split(" ")))
 
now_turn = "Alice"
alice_point = 0
bob_point = 0
 
while True:
    if max(a_list) == -1:
        break
    
    if now_turn == "Alice":
        alice_point += max(a_list)
        a_list[a_list.index(max(a_list))] = -1
        now_turn = "Bob"
    elif now_turn == "Bob":
        bob_point += max(a_list)
        a_list[a_list.index(max(a_list))] = -1
        now_turn = "Alice"
 
print(alice_point - bob_point)

　交互にプレイヤーのターンを入れ替えて、リスト内の最も大きい数字を自分のポイントに加算しています。

ABC085B - Kagami Mochi

問題文

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

　ダックスフンドのルンルンが餅を積み重ねて鏡餅を作る、という~~よくわからない~~設定ですが、入力から重複している値を除くだけで鏡餅の最大重ね数がわかります。

n = int(input())
d = []
for i in range(n):
    d.append(int(input()))
d = list(set(d))
d.sort()
 
print(len(d))

　pythonはset()メソッドで数学の集合を扱えるため、自動で重複を取り除いてくれます。sort()してるのは、下から餅を大きい順に重ねるためですが、今回は最大の段数だけが知りたいので、必要なかったですね。

終わりに

　　今回はABSのB問題を解説していきました。自分のコードに納得できない箇所がいくつかあったので、要勉強ですね。　次回はC問題を解説しようと思います。

中百舌鳥雑記組

競技プログラミングを始めてみました。過去問や勉強したことをまとめていきます。