AtCoder Beginner Contest 156(ABC156) A～E解説

AtCoder Beginner Contest 156(ABC156)のA～Eまでの解説です。
コンテスト中はA～Dの4完(25:38)、その後Eも解きました(久々のコンテストだったのでレートを伸ばしたかったのですが、Eの方針が立たずレートが1下がってしまいました)。
問題のアドレスは以下になります↓
https://atcoder.jp/contests/abc156
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/abc156/editorial.pdf

A問題:

少し条件が複雑ですが、問題文の通りに実装すればよいです。
min関数を使ってmin(100*(10-K),0)と書き、K>10のときに100*(10-K)の値が負にならないように補正してあげると、if文による条件分岐を書く必要がなくなります。

B問題:

整数NをK進数で表したときの桁数は、K進数の定義よりN/K^i>=1となる最大の指数iを用いて(i+1)桁と表すことができます。
また、制約より指数iとしてあり得る数の範囲は最大でもlog2(10^9)<30となるので、for文を用いてN<K^iを満たす最小のiを求め、それを出力すればよいです(条件式はN/K^i>=1を満たす最大の指数iについてK^i<=N<K^(i+1)が成り立つことから得られます)。

C問題:

制約よりXiの範囲が1<=Xi<=100であることから、Pとして考えるべき範囲は1<=P<=100に収まります(∵P<1なるPに対してはP=1を、P>100なるPに対してはP=100を取ることで消費する体力の総和を真に小さくできます)。
また制約よりN<=100なので、上記の範囲のPすべてについて消費する体力の総和を求め、その最小値を答えればよいです(体力の総和を1回求める計算量がO(N)であり、Pの範囲よりこれを100回行えばよく、Nの制約より計算量のオーダーは高々10^4となるのでこの問題を解くことができました)。

サンプルコード(Python):
https://atcoder.jp/contests/abc156/submissions/10295286

n=int(input())
arr=list(map(int,input().split()))
ans=10**18 #最小値を求めるので初期化しておく
for i in range(1,101): #1<=P<=100の範囲について消費する体力の総和を計算
 tmp=0
 for num in arr:
   tmp+=(i-num)**2
 ans=min(ans,tmp) #消費する体力の総和の最小値が答えとなる
print(ans)

D問題:

まず、n種類の花を1本以上使って作ることのできる花束の総数は2^n-1で求められます(これはn種類の花それぞれについて選ぶか選ばないかを考え、最後に1つも選ばなかった場合の1通りを除くことで得られます)。
2^n-1を普通に計算しようとすると計算量はO(N)となりますが、いま制約よりN<=10^9なので最大10^9回の計算を行うことになり制限時間に間に合いません。
そこで2^n-1を高速に求める方法を考えます。
これには繰り返し2乗法という方法を用いることができ、繰り返し2乗法ではnを2進数展開したときのi番目(0-indexed)のbitと2^(2^i)を対応させて下のbitから順に計算します。
この方法を用いることで計算量が高々O(logN)となるので2^n-1を高速に計算することができました。
次に、a本の花を使う花束の作り方の総数について考えます(b本の場合についても同様に計算できるのでa本の場合のみ考えます)。
これはn種類の花からa種類の花を取る総数に等しく、nCaとして表すことができます。
nCaはn!/a!(n-a)!と表すことができ、多くの場合はこの形で計算をするのですが、今回は制約よりN<=10^9なので(n-a)!の計算量がO(N)となり、2^n-1を求める場合と同様の理由で制限時間に間に合わなくなります。
ここで制約に注目すると、a<b<=min(N,2*10^5)とあり、これとn!/(n-a)!はn*(n-1)*…*(n-a+1)と表せることから、nCaをn*(n-1)*…*(n-a+1)/a!として表して計算することにすると、計算量が10^5のオーダーになり制限時間内に計算できることが分かります。
ここで1/a!の部分の計算方法について、剰余の元では足し算・引き算・掛け算は剰余を取る順番によらず計算できるのですが、割り算に関しては正しく計算ができるとは限らないので、割り算を割る数の逆数を用いた掛け算に変換することで計算を行います。
剰余が整数のとき逆数を求めるのは簡単ではありませんが、剰余pが素数のときには、フェルマーの小定理によりk^(p-1)≡1 (mod p)が成り立つので、これからk^(p-2)=k^(-1) (mod p)が得られ、kの逆数としてk^(p-2)を用いることができることが分かります。
k^(p-2)は繰り返し2乗法によりO(logk)で求めることができるので、これから1/a!を1からaまでの各数kについてk^(p-2)を求めそれらを掛け合わせることで求めることができ、O(NlogN)でnCaの値を求めることができます。
以上より答えは2^n-1-(nCa+nCb)で求めることができ、この計算量はO(NlogN)となり制限時間内にこの問題を解くことができました。

サンプルコード(Python):
https://atcoder.jp/contests/abc156/submissions/10296201

#powは繰り返し2乗法により指数計算を行う関数
mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り
comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
 comb1*=i
 comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
 comb1*=pow(i,mod-2,mod)
 comb1%=mod
comb2=1
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
 comb2*=i
 comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
 comb2*=pow(i,mod-2,mod)
 comb2%=mod
ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)

E問題:

まず、問題文の操作を行うことで状態がどのように変化していくかを観察してみます。
0回操作を行うと、すべての部屋に1人がいることになります(初期状態です)。
1回操作を行うと、ある部屋から1人を移動させるので0人の部屋が1つある状態が増えます。
2回操作を行うと、0人の部屋が2つある状態が増えます。
3回操作を行うと、0人の部屋が3つある状態が増えます。
同様に、N-1回操作を行うと、0人の部屋がN-1つある状態が増えます。
さらに、K回の操作で、0〜K-1回操作を行った状態も作りだすことができます。
以下これを示します。
K回の操作でK-1回操作を行ったときの状態を作り出すためには、K-2回操作を行ったあとの最後の1回の操作を2回に分けて行えばよいです。
この操作は制約よりN>=3であることから必ず存在し(∵部屋xからyへの移動を部屋zを経由してx→z→yとすればよいです)、これと任意の2部屋を往復させることで状態を変化させずに操作回数を2回増やせることから、K-2～0回操作を行ったときの状態も同様に作り出せることが言えます。
また、操作回数がN以上のとき状態数が増えることはない(∵0人の部屋は高々N-1個しか存在しない)ので、N-1回までの操作を考えれば十分です。
以下、0人の部屋がK個ある状態について、その場合の数を求める方法を考えます。
まず、0人の部屋がK個あるような部屋の組み合わせはNCK通りあります。
さらに、N-K個の1人以上の部屋の人の割り振り方を、まずN-K個の部屋に1人を割り振り、残るK人をN-K個の部屋に割り振るというふうに考えて計算します。
この場合の数はK人をN-K-1個の仕切りで区切るような場合の数(重複組み合わせ)を考えると、(K+(N-K-1))CKとなり結局(N-1)CK通りとなります。
あとはNCKと(N-1)CKを求める方法を考えればよいです。
aCbについて、aC(b+1)をaCb*(a-b)/(b+1)で求めることができ、1/(b+1)の逆数はフェルマーの小定理より(b+1)^(p-2) (pは素数)で得られるので、初期値をNC0と(N-1)C0として、下から順にNCmin(K,N-1)、(N-1)Cmin(K,N-1)まで計算していくと、求める状態の総和をO(NlogN)で求めることができます。

サンプルコード(Python):
https://atcoder.jp/contests/abc156/submissions/10296688

mod=10**9+7
n,k=map(int,input().split())
ans=0
comb1=1 #初期値はNC0=1
comb2=1 #初期値は(N-1)C0=1
for i in range(min(k+1,n)): #0人の部屋は高々N-1個しか存在しないので操作回数は高々min(K,N-1)回となる
 ans+=comb1*comb2 #0人の部屋がi個のときの場合の数はNCi*(N-1)Ci
 ans%=mod
 comb1*=(n-i)*pow(i+1,mod-2,mod) #NC(i+1)はNCi*(N-i)/(i+1)で求められる
 comb1%=mod
 comb2*=(n-1-i)*pow(i+1,mod-2,mod) #(N-1)C(i+1)は(N-1)Ci*((N-1)-i)/(i+1)で求められる
 comb2%=mod
print(ans)