Codeforces #279 Div2 E. Restoring Increasing Sequence

これは割とすんなり。
http://codeforces.com/contest/490/problem/E

問題

N要素の整数列A[i]が与えられる。
ただしA[i]は一部の桁が'?'で伏せられている。

'?'に0-9の数字を入れ、A[i]を単調増加な数列に出来るか。
出来るならA[i]の例を答えよ。
ただしleading zeroは含んではいけない。

解法

A[i]について、A[i-1]+1以上のうちあり得る最小値を取るよう'?'の中身を決めていけば良い。

A[i]の値を決める際は、上の桁の'?'から決める。
'?'に0-9に順に値を入れ、その際より下の桁の'?'にすべて9を入れた場合、A[i]がA[i-1]+1以上になるなら最小の数値を'?'の値とする。
この処理を各桁に繰り返すことでA[i]の値を確定できる。

int N;
int V[100005];
int p10[10];

int more(string s,int v) {
	int q[10];
	int L=s.size();
	int i,j;
	while(1) {
		
		int val=0, tq=-1;
		FOR(i,L) if(s[i]=='?' && tq<0) tq=i;
		FOR(i,L) if(s[i]!='?') val += p10[L-1-i]*(s[i]-'0');
		
		if(tq==-1) {
			if(val>v) return val;
			else return -1;
		}
		
		FOR(i,L) if(s[i]=='?' && i>tq) val += p10[L-1-i]*9;
		FOR(j,10) {
			s[tq]='0'+j;
			if(tq==0 && j==0) continue;
			if(val + j*p10[L-1-tq] > v) break;
		}
		if(j==-1) return -1;
	}
	return -1;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=1;
	FOR(i,8) p10[i+1]=p10[i]*10;
	
	cin>>N;
	FOR(i,N) {
		cin>>s;
		V[i+1]=more(s,V[i]);
		if(V[i+1]<0) return _P("NO\n");
	}
	
	_P("YES\n");
	FOR(i,N) _P("%d\n",V[i+1]);
	
}

まとめ

難易度は控えめだけど、割とシンプルで良い問題。