A - Fifty-Fifty
問題ページ : A - Fifty-Fifty
考察
標準入力、条件分岐、出力。
条件分岐が少し難しいですが、文字列Sに含まれる各文字sの数をS.count(s)でカウントし全て2個であれば"Yes"、それ以外の数字があらわれば"No"となります。
コード
S = list(input())
ans = "Yes"
for s in S:
if S.count(s) != 2:
ans = "No"
print(ans)
B - Ordinary Number
問題ページ : B - Ordinary Number
考察
nが小さいので全探索でとけます。
$p[i]$が2番目に小さいという条件は、$p[i-1] < p[i] < p[i+1] or p[i-1] > p[i] > p[i+1]$であらわせます。
コード
n = int(input())
P = list(map(int, input().split()))
ans = 0
for i in range(1,n-1):
if P[i-1] < P[i] < P[i+1] or P[i-1] > P[i] > P[i+1]:
ans += 1
print(ans)
C - Divide the Problems
問題ページ : C - Divide the Problems
考察
Nが必ず整数なので、難易度$d_i$を小さい順にソートし、$\frac{N}{2}$番目より大きく、$\frac{N}{2} + 1$番目以下の難易度数の数が答えとなります。
コード
N = int(input())
D = list(map(int, input().split()))
D.sort()
print(D[N // 2] - D[N // 2- 1])
D - Blue and Red Balls
問題ページ : D - Blue and Red Balls
考察
問題文からいきなりコードをかくのは難しいので具体例を設定して考えてみます。
具体例
- 青いボール 9個（$K=9$）
- 赤いビール 11個（$N=20,\ N-K=11$）
- 3回の操作で青いボールを回収（$i=3$）
左から右に連続しボールのうち、連続した青いボールを一つ青い箱へ、連続した赤いボールを一つの赤い箱へ入っていると考えます。
このようなイメージで考えると具体例における問題は、9個の区別のない青いボールの3個の区別ある箱への分け方と、11個の区別のない赤いボールの4個の区別のある箱への分け方、との組み合わせになります。
ただし、ピッタリ3回の操作とするためには、両端の2箱は空でも良いが、真ん中の5箱は空であってはならないという制約があります。空でもいい箱と空であってはならないという制約が混在すると面倒ですので予め
空であってはならない箱にはあらかじめ一つのボールを入れておくこととします。
すると、6個の区別のない青いボールの3個の区別ある箱への分け方（受けるボールが0であっても良い）と、9個の区別のない赤いボールの4個の区別のある箱への分け方（受けるボールが0であっても良い）、との組み合わせとなります。
前者及び後者とも重複組み合わせ（n個のボールをr個の箱に分ける組み合わせ数は$\binom{n+k-1}{k-1}$となる）で考えればよく、
$$\binom{6+3-1}{3-1}\ \times\ \binom{9+4-1}{4-1}$$
となります。
一般化すると、
$$\binom{(K-i)+i-1}{i-1}\ \times\ \binom{ (N-K-(i-1)) + (i+1) -1}{(i+1)-1}$$
整理して
$$\binom{K-1}{i-1}\ \times\ \binom{N-K+1}{i}$$
となり、$\binom{n}{k}$はpythonでは$math.comb(n,k)$で求めることが可能ですのでコーディングが可能となりました。
コード
mod = 10 ** 9 + 7
from math import comb
N,K = map(int, input().split())
for i in range(1, K + 1):
b_num = comb(K - 1, i - 1)
r_num = comb(N - K + 1, i)
ans = (b_num * r_num) % mod
print(ans)
考察での、途中計算もコード上で実施した方がミスを減らしやすいかもしれません。実際にいきなり上記コードを書くよりも下記のようなコードの方が現実的かもしれません。
mod = 10 ** 9 + 7
from math import comb
N,K = map(int, input().split())
blue = K
red = N - blue
for i in range(1,K+1):
available_blue = blue - i
available_red = red - (i-1)
b_num = comb(available_blue + i - 1, i - 1)
r_num = comb(available_red + (i + 1) - 1,(i + 1) - 1)
ans = (b_num * r_num) % mod
print(ans)
E - Hopscotch Addict
問題ページ : E - Hopscotch Addict
F - Small Products
問題ページ : F - Small Products
青色diff以上は後日挑戦