この回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; } } } }
まとめ
上の桁から埋めたくなってしまい手間取った。