【AtCoder】ABC209をPython3で解説

ABC209の解説。

A - Counting

解説

$A$以上かつ$B$以下の整数はいくつあるか。

そもそも$A$が$B$よりも大きかったら、満たされる数がないので$0$を出力。

$A$以上かつ$B$以下なら、整数の個数は、$B$から$A$を引いて$1$を引いた数。

コード

a, b = map(int, input().split())

if a > b:
    print(0)
else:
    print(b-a+1)

B - Can you buy them all?

解説

所持金$X$円で、$N$個の商品を買うことができるか。なお、$A_i$で$i$が偶数のときは、1円引きで商品が買えるものとする。

偶数のときに1円引きされるので、$N$個の商品の合計金額から、偶数の数ぶん1円引いてやれば良い。

コード

n, x = map(int, input().split())

alist = list(map(int, input().split()))

if sum(alist) - n // 2 <= x:
    print('Yes')
else:
    print('No')

C - Not Equal

解説

条件を満たす長さ$N$の整数列$A$の個数を求める。条件は、

条件1$1： \leq A_i \leq C_i$→整数$A_i$は1以上$C_i$以下

条件2：$A_i \neq A_j$→整数列Aのなかに同じ数字を含んではならない

入力例1でみていく。1 3の入力でこの条件を満たすようにするにはどうすればよいか。まず、条件1だが、1の選択肢は、1のみ。3の選択肢は、1, 2, 3となる。条件2を見ると、$A_i$が同じ数になってはいけないことがわかる。つまり、1, 2, 3のうち1は棄却される。

つまり、答えの整数列は(1, 2)と(1, 3)の2とおりとなる。

入力例2でみていく。3 3 4 4の入力だ。まず、条件1だが、3の選択肢は、1, 2, 3、4の選択肢は、1, 2, 3, 4となる。条件2を見ると、同じ数になってはいけないので、1, 2, 3のうち1つを選ぶと、次の3では、選択肢が1つなくなる。同様に4でも選択肢が1つなくなり、結果できる整数列の個数は、$(3-0) \times (3-1) \times (4-2) \times (4-3)$となる。

つまり、sortした整数列をインデックス番号を引きながら、乗算していくと答えを導き出せるということがわかる。

なお、そのまま計算するとオーバーフローしてしまう恐れがあるので、適宜$MOD = 10^9 + 7$ で割った余りを出す必要がある。

これの説明についてはこちら。
→https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

コード

n = int(input())
clist = list(map(int, input().split()))
MOD = (10**9 + 7)

clist.sort()

ans = 1

for i in range(n):
    ans = ans * (clist[i] - i) % MOD
    
print(ans)

編集後記

灰灰灰のコンテスト多くないか...?