kmjp's blog

競技プログラミング参加記です

AtCoder ARC #123 : C - 1, 2, 3 - Decomposition

この回Fがかなり難しかった。
https://atcoder.jp/contests/arc123/tasks/arc123_c

問題

正整数Nが与えられる。
各桁1,2,3しか使えない整数値をいくつか準備し、総和がNとなるようにしたい。
最少何個の整数値で条件を満たせるか。

解法

k個で条件を満たせるかどうか、というのをkの小さい順に試していこう。
まぁ大体kが10以下で条件を満たせそうなのは想像がつく。

f(d,a,c) := 下からd桁目まで決めたとき、d桁目に1,2,3の数値を入れられるのがa個以下で、下から繰り上がりがc個あるとき、そのような条件を満たせるかどうかの真偽値

を考える。f(0,k,0)から初めて、f(inf,0,0)=trueになるか判定すればよい。
状態遷移としては、0≦b≦a個(d+1)桁目に値を埋めるとなると、その桁に合計b≦e≦3bの数字を埋め込める。
よってf(d+1,b,(e+c)/10) := f(d,a,c)かつ(e+c)%10がNのd桁目と一致するならtrue
としてDPを行える。

int T;
ll N;

int D[20];

int dp[20][40][11];

int ok(int num) {
	ZERO(dp);
	dp[0][0][num]=1;
	int d;
	FOR(d,19) {
		int c,n;
		for(n=num;n>=0;n--) {
			FOR(c,40) if(dp[d][c][n]) {
				if(n) dp[d][c][n-1]=1;
				
				for(int p=c+n*1;p<=c+n*3;p++) {
					if(D[d]!=p%10) continue;
					int nc=p/10;
					dp[d+1][nc][n]=1;
				}
				
			}
		}
	}
	return dp[19][0][0];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		FOR(i,20) {
			D[i]=N%10;
			N/=10;
		}
		
		for(i=1;i<=10;i++) {
			if(ok(i)) {
				cout<<i<<endl;
				break;
			}
		}
		
		
	}
}

まとめ

上の桁から埋めたくなってしまい手間取った。