CODE FESTIVAL 2018 Qual A : C - 半分

ABCDまで最速でした。Eは解いてる最中に離脱したけど、最後までいても解けなかったかな。
https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_c

問題

N要素の整数列Aが与えられる。
任意の要素を選択し、２で割って小数点以下は切り落とす、という作業をK回行う。
得られる数列は何通りか。

解法

要素A[i]は、(floor(log(A[i]))+1)回までは処理を行うたび値が変わり、以降は値が変わらない。
一旦(floor(log(A[i]))+1)回処理をしてしまえば、あとは値が変わらないので、数列全体の値を変えずに処理回数を消費できる。

そこで、
dp(i,k,b) := A[0..i]までに計k回処理を行い、かつbは0にしてしまった要素があるかどうかを示す真偽値としたとき、そのような操作手順の数
としてDPしていこう。
解はdp(N,K,false) + dp(N,0,true)+dp(N,1,true)+...+dp(N,K,true)となる。

int N;
ll A[51],C[51];
int K;

ll from[3100][2];
ll to[3100][2];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	if(K==0) return _P("1\n");
	
	from[0][0]=1;
	FOR(i,N) {
		cin>>A[i];
		while(A[i]) {
			A[i]/=2;
			C[i]++;
		}
		ZERO(to);
		FOR(j,3001) {
			FOR(x,C[i]+1) {
				if(x==C[i]) {
					(to[j+x][1]+=from[j][0])%=mo;
				}
				else {
					(to[j+x][0]+=from[j][0])%=mo;
				}
				(to[j+x][1]+=from[j][1])%=mo;
			}
		}
		swap(from,to);
	}
	
	ll ret=0;
	if(K<=3080) ret+=from[K][0];
	FOR(i,min(K+1,3080)) ret+=from[i][1];
	cout<<ret%mo<<endl;
}

まとめ

これはまぁすんなり。