ABC208参戦記

前回のABC207はAB2完で終わってしまい、悔しい思いをしました。
今回はCまでを素早く解いて、D問題に着手できるとよいな。と思い臨んだABC208の参加記録です。

使用言語はPython3です。レート帯は茶色中位です。

A – Rolling Dice

標準入出力と条件分岐が書けるかが問われる問題。

標準入力は、1行に2変数が書かれているのを受け取るのは、map() を利用するのが良いですね。

あとは、A回振ってBになる可能性は、BがA*6以下であれば、”Yes”、それ以外であれば”No”を出力したらOKですね。と思って提出するとWAになりました。
Bが、Aよりも小さい時も”No”を出力するケースが考えられていないためでした。

これら二つの条件を整理すると、”Yes”を出力する条件は、A<=B<=6*Aです。

# AtCoder Beginner Contest 208
# A - Rolling Dice

A,B=map(int,input().split())
if A<=B<=6*A:
    print("Yes")
else:
    print("No")

B – Factorial Yen Coin

貪欲法を知っていますか？私は知っていますが、よく理解していません。

価値の高い硬貨から順番に使用していけばACします。

詳細な証明については、公式の解説などを参照していただくとして、階乗円硬貨は一つ上の硬貨になるにつれて、下位の硬貨の数倍の値段を支払うことができます。また、端数はより下位の硬貨でしか支払えないですが、わざわざ高い価値の硬貨で支払える分まで下位の硬貨で支払うと支払い枚数が増えるだけになります。

あとは、価値の高い硬貨から順に使用する枚数を決めて、答え用の変数に加えていけばOKでした。

私は階乗円硬貨は事前に計算して、値として保持しておきました。

# AtCoder Beginner Contest 208
# B - Factorial Yen Coin

P=int(input())

C1=1
C2=2
C3=6
C4=24
C5=120
C6=720
C7=5040
C8=40320
C9=362880
C10=3628800

coins=[C10,C9,C8,C7,C6,C5,C4,C3,C2,C1]

ans=0

for coin in coins:
    if P>=coin:
        num=P//coin
        ans+=num
        P=P%(coin*num)

print(ans)

C – Fair Candy Distribution

数列の順番を保持しながら、小さいほうから数えて何番目かを判定する問題。

私は、受け取った配列aのほかに、二つの配列を用意しました。
ソートしたaの配列と、答えの個数を格納していく配列です。

まずはお菓子の数を国民の数で割って、余りが出ないなら、均等になるため、N回均等な数を出力します。
余りが出た場合は、国民番号の若い順に並べて、余った個数以下のインデックスであれば追加分を含めた個数を答え用の配列に格納して、余った個数より後のインデックスの場合は、均等に分けた分の数を答え用の配列に格納していきました。
インデックスの判定には、ソートしたaの配列に対して bisect モジュールの bisect.bisect_right() を利用しました。

# AtCoder Beginner Contest 208
# C - Fair Candy Distribution

import bisect

N,K=map(int,input().split())
a=list(map(int,input().split()))

sorteda=sorted(a)

answer=[]

d,m=divmod(K,N)

if m==0:
    for i in range (N):
        print(d)


else:
    for i in range (N):
        t=a[i]
        b=bisect.bisect_right(sorteda,t)
        if b<=m:
            answer.append(d+1)
        else:
            answer.append(d)

for ans in answer:
    print(ans)