TPC追いコン : E - 10進数の数列

面白かったし、解けて良かった。
http://oidashi.contest.atcoder.jp/tasks/oidashi_e

問題

N個の整数A[i]が並んでいる。
これらからいくつかを抜き出し、順序を変えず連結する。
ただし元もと隣同士にある整数を両方抜き出すことはできない。
このようにして作成した整数群を、単一の10進数の値として読むことを考える。

元のA[i]に対し、上記手順で生成できない最小の整数値を求めよ。

解法

上記手順を逆に考えると、作りたい整数値が決まっているとき、貪欲にA[i]の頭から近い順に、整数値を構成する各桁の整数を取ってくるのが良い。
そこで、各iに対し、A[i]を抜き出したとき、次に整数d(d=0～9)を抜き出す場合どこから抜き出すのが最適かを求めよう。
すなわち、各dに対し、A[i+2]以降でdが登場する最初の位置P[i][d]を求める。

次に、上記P[i][d]を用いると、A[i]以降最小で後何桁の整数が取れるかを求めることができる。
A[i]の次にd=0～9を抜き出そうとする場合、A[P[i][d]]以降で作れる桁数が最小のものを選べばよい。
(桁数が同着なら当然dが小さい方を選ぶ)

なお、leading zero対策で最初に0を選べない点には注意。
以下のコードでは、Aの頭に２個0を挿入した上、初手でd=0は選べないという例外を加えてこのコーナーケースに対応している。

int N;
int A[101010];
int nex[101010][10];
int dist[101010],sel[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) cin>>A[i+2];
	N+=2;
	
	for(i=N-1;i>=0;i--) {
		dist[i]=10000000;
		FOR(x,10) {
			if(i==0 && x==0) continue;
			if(i>=N-2) nex[i][x]=N;
			else if(A[i+2]==x) nex[i][x]=i+2;
			else nex[i][x]=nex[i+1][x];
			
			if(dist[nex[i][x]]+1<dist[i]) dist[i]=dist[nex[i][x]]+1, sel[i]=x;
		}
	}
	
	x=0;
	while(x<N) {
		_P("%d",sel[x]);
		x=nex[x][sel[x]];
	}
	_P("\n");
}

まとめ

なんか本番すんなり解法が思いついた。