競プロ初心者の復習用記事です。
ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。
A - Beginner
とある競プロサイトでは、回数が少ない人のレーティングは内部レーティングより高めに表示しているらしいです。実際の内部レーティングがいくつかを答える問題です。
回数Nが10以上ならそのまま出力。10未満なら補正値$100\times (10-N)$を加えた値が内部レーティングになります。
N, R = map(int, input().split())
if N < 10:
print(R + 100 * (10-N))
else:
print(R)
B - Digits
数値NをK進法で表記したときに何桁になるかを答える問題です。
最大の桁がどこになるかを考えます。例えば$N=9, K = 2$なら、$2^3$である$1000$が最大の桁となり、$r=4$と求まります。これを数式で言えば、以下を満たす乗数rを求めればいいことになります。
$$ K^{r-1} \leq N < K^{r} $$
これを単純に実装しました。
N, K = map(int, input().split())
r = 1
while not(K**(r-1) <= N and N < K ** r):
r += 1
print(r)
これで問題なく通りましたが、解説を見るとやり方が異なりました。
求める桁数を$D$、各桁の値を$a_{D-1}, \cdots , a_1, a_0$
とすると$$ $$
$$ N = a_{D-1}K^{D-1} + \cdots + a_1 K^1 + a_0 K^0$$
という数式で表されます。
$N$を$K$で割って商をとる操作を繰り返すと、$D$回$K$で割ったところで商が$0$となります。
これを実装してみます。
N, K = map(int, input().split())
D = 0
while N:
N //= K
D += 1
print(D)
計算時間はどちらでも問題ありませんでした。
C - Rally
数直線上に配置された人達の、二乗誤差がもっとも小さくなる地点（整数値）はどこかを答える問題です。
問題文からパッと連想するのは最小二乗法ですが、N, Xがともに1から100までという狭い範囲をとっています。$O(N^2)$が問題なく通るため数学的な技術は必要ないと判断し、シンプルに全探索してみました。
N = int(input())
X = list(map(int, input().split()))
minLoss = 1e6
for i in range(1, 101):
minLoss = min(minLoss, sum([(x - i)**2 for x in X]))
print(minLoss)
これで通りました。
左右の範囲を1から100までじゃなくてXの最小値と最大値にすればもうちょっと効率はいいと思います。
D - Bouquet
N種類の異なる花から取り出す組み合わせは何種類あるでしょうか？ただしa本、b本取り出すことはできません。という問題です。
1からNまでの各本数nについて$_nC_r$で組み合わせを求めようとしたため、TLE。諦めました。
解説を見ました。「全ての本数についての全組み合わせ」というのは、もっとずっと簡単に計算できます。
それぞれの花は「使う」「使わない」の二通りの選択肢しかありません。つまり全ての組み合わせは$2^N$。ただし0本使う組み合わせは除外されているため、正確には$2^N-1$です。
ここからa, bについて$_nC_r$で除外するべき組み合わせを引けば求まります。
from scipy.misc import comb
m = 1000000007
n, a, b = map(int, input().split())
out = 2**n - comb(n, a) - comb(n, b)
print(out%m)
これだとダメでした。2**nや$_nC_a, _nC_b$がそれはもうえげつない数になってしまうのが問題です。
これを何とかするためには
「$10^9+7$で割った余り」という条件を使い、数学的な手法で計算を減らしていく必要があります。
まず、2の乗数について考えます。pythonでは**ではなくpow()を用いて第三引数で割る数を指定し、剰余計算を高速で行うことができます。
print(pow(2, 4, 3)) # 1
次に組み合わせ計算の高速化を考えます。
フェルマーの小定理というものがあります。$p$が素数、$a$と$p$が互いに素であるときに
$$ a^{p-1} \equiv 1~~(\rm{mod}~ p) $$
が成り立つ。つまりaのp-1乗をpで割ると1になる。らしい。知りませんでした。
いまいち実感が沸かなかったので、適当に試してみます。
p = 29
for a in range(3, 29, 5):
print("a: {}, p: {}, a^(p-1)%p: {}".format(a, p, pow(a, p-1, p)))
'''
a: 3, p: 29, a^(p-1)%p: 1
a: 8, p: 29, a^(p-1)%p: 1
a: 13, p: 29, a^(p-1)%p: 1
a: 18, p: 29, a^(p-1)%p: 1
a: 23, p: 29, a^(p-1)%p: 1
a: 28, p: 29, a^(p-1)%p: 1
'''
ほんとだ。へー。証明はここでは触れません。
話を戻します。この条件では$10^9+7$とYは必ず互いに素であるため、以下の式が成立します。
$$ Y^{(10^9+7)-1} \mod 10^9+7 = 1 $$
両辺をYで割って
$$ Y^{(10^9+7)-2} \mod 10^9+7 = {1\over Y} $$
この形なら先ほどと同じように、pow()を用いて高速に計算ができます。組み合わせ計算に出てくる項を分母Xと分子Yに分離し、Yにこの処理をかけます。
m = 1000000007
n, a, b = map(int, input().split())
def comb(n, r, m):
X, Y = 1, 1
for i in range(r):
X *= n-i
Y *= i+1
X %= m
Y %= m
return int(X * pow(Y, m-2, m))
out = pow(2, n, m) - 1 - comb(n, a, m) - comb(n, b, m)
print(out%m)
これで通りました。
E - Roaming
n個の部屋にそれぞれいる人がk回移動したら部屋の状態は何通りありうるでしょうか？という問題です。
解き方の想像もつかず、諦めました。
解説を見ました。
まず、人数が0人となる部屋の組み合わせを考えます。$m$個の部屋が空となっているとします。そうすると、全n部屋からm部屋を選ぶ組み合わせは
$$ _nC_m $$
で求まります。
そこから、元のm部屋の住人が移動した部屋の組み合わせを考えます。考え方はいろいろありますが、シンプルな考え方として$m$人の住人を$n-m-1$個の壁で区切るようにしてみます。住人を〇、壁を|とすると、文字列を並べるパターンの組み合わせを考える問題に変えることができます。
例:5人を2つの壁で分ける方法は？
〇〇|〇|〇〇
みたいな組み合わせができる。
この並べ方は
$$ {7! \over 5!2!}=_7C _2$$
で計算できる。
この計算を今回の状況に当てはめると、以下の式が求まります。
$$ {(m +(n-m-1))!\over m!(n-m-1)!}=_{n-1}C _{m} $$
よって、$_nC_m \times _{n-1}C _{m}$で$m$部屋が0人の時の組み合わせが求まります。この$m$を0から$k$(もしくは$n-1$)まで変化させながら合計をとればいいことになります。
また、組み合わせの計算結果はその次の組み合わせ計算にも流用できます。
$$ _{n}C _{m+1} = _{n}C _{m} \times {n-m\over m+1} $$
$$ _{n-1}C _{m+1} = _{n-1}C _{m} \times {n-m-1\over m+1} $$
これを先ほどの式(以下)も利用しつつ、計算していきます。
$$ Y^{(10^9+7)-2} \mod 10^9+7 = {1\over Y} $$
というわけで実装例です。ほとんど他の人のコード見ながら書いてます。
n, k = map(int, input().split())
c1 = 1
c2 = 1
mod = 10**9+7
ans = 0
for i in range(min(n, k+1)):
ans += c1 * c2
c1 *= (n-i) * pow(i+1, mod-2, mod)
c1 %= mod
c2 *= (n-i-1) * pow(i+1, mod-2, mod)
c2 %= mod
print(ans%mod)
以上で今回の記事はここまでとします。