Google Code Jam 2021 Round 1B : C. Digit Blocks

意地でも二分探索を出さないという信念を感じる？
https://codingcompetitions.withgoogle.com/codejam/round/0000000000435baf/00000000007ae37b

問題

300個の数字が順に与えられる。

ここから15桁の数値を20個作ることを考える。
数字が1つ与えられるたびに、どこかの数値を選び、下の位から順にその数字を埋めて行くとする。
1つ数字が与えられるたび、その数字を埋める数値を決めないと、次の値が得られない。

20個の数値の総和を極力大きくしたい。
理論値の98%をたたき出すような埋め方を答えよ。

解法

まず、各数値の埋まった桁数のmultisetを状態とし、対応する総和の期待値の最大値を取るDPを考える。
数字が与えられるたび、各数値に埋めた場合の状態遷移のうち最大値を取るものを選べばよいことになる。

ただ、今回だと雑には15^20、ソートしてもH(15,20)通り程度の状態があるので、状態をすべて持つことはできない。
ここで、下の方の桁は総和にほとんど影響を及ぼさないことを考えよう。
そうすると、状態として(最上位桁が開いてる数値の数、上から２桁目が開いてる数値の数、2桁以上開いている数値で空き桁の総和)位まで取るようにすれば十分98%以上をたたき出せる。

int T,N,B;
ll P;

ll memo[21][21][16][21];
ll p10[16];
int D[20];

ll expected(int t) {
	int T14=0;
	int T13=0;
	int L=0;
	int left=0;
	int i;
	D[t]++;
	FOR(i,N) {
		if(D[i]==14) T14++;
		if(D[i]==13) T13++;
		if(D[i]<13&&D[i]>0) L=D[i];
		if(D[i]==0) left++;
	}
	D[t]--;
	return memo[T14][T13][L][left];
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	ZERO(D);
	
	FOR(i,N*B) {
		cin>>x;
		ll ma=-1;
		int tar=0;
		FOR(j,N) {
			ll cur=-1;
			if(D[j]==14) {
				cur=x*p10[14]+expected(j);
			}
			else if(D[j]==13) {
				cur=x*p10[13]+expected(j);
			}
			else if(D[j]<13&&(j==0||D[j-1]>=13)) {
				cur=x*p10[D[j]]+expected(j);
			}
			if(cur>ma) ma=cur, tar=j+1;
		}
		D[tar-1]++;
		cout<<tar<<endl;
		
	}
	
	
}



ll dfs(int T,int T2,int L,int left) {
	ll& ret=memo[T][T2][L][left];
	if(ret>=0) return ret;
	if(T==0&&T2==0&&L==0&&left==0) return memo[T][T2][L][left]=0;
	ret=0;
	int i;
	FOR(i,10) {
		ll ma=0;
		if(T) ma=max(ma,i*p10[14]+dfs(T-1,T2,L,left));
		if(T2) ma=max(ma,i*p10[13]+dfs(T+1,T2-1,L,left));
		if(L) {
			if(L==12) ma=max(ma,i*p10[L]+dfs(T,T2+1,0,left));
			else ma=max(ma,i*p10[L]+dfs(T,T2,L+1,left));
		}
		if(left&&L==0) ma=max(ma,i+dfs(T,T2,1,left-1));
		ret+=ma;
	}
	ret/=10;
	return ret;
	
}

void init() {
	int i;
	p10[0]=1;
	FOR(i,15) p10[i+1]=p10[i]*10;
	
	MINUS(memo);
	dfs(0,0,0,N);
}

まとめ

色々考えるなぁ。