UTPC 2013 : D - 壊れかけのヒープ

Dまでは何とか本番に解答。
http://utpc2013.contest.atcoder.jp/tasks/utpc2013_04

問題

バイナリヒープを構成する配列の後半部分が与えられる。
ヒープ内の数値がすべて異なるようにする場合、最小のヒープ長を答えよ。

解法

ヒープ長を決めてしまえば、配列要素間の大小関係が求まる。
その大小関係から、配列の前半部分について後ろから順に出来るだけ大きな数字を埋めていけばよい。
全ての値を矛盾なく入れられればok。

あとはその処理をヒープ長を総当たりすればよい。
ヒープ長総当たりがO(N)、1回の数値埋めがO(N logN)なので全体でO(N^2 logN)。

int N;
ll A[3000];
ll B[3000];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N;
	FOR(i,N) cin>>A[i];
	set<int> S;
	FOR(i,N) S.insert(A[i]);
	FOR(i,680) {
		set<int> S2=S;
		int ng=0;
		FOR(x,N) B[i+x]=A[x];
		
		for(x=i+N-1;x>=0;x--) {
			if(x>=i) {
				if(2*x+1<N+i && B[x]>B[2*x+1]) ng=1;
				if(2*x+2<N+i && B[x]>B[2*x+2]) ng=1;
			}
			else {
				if(2*x+1 >= N+i) {
					B[x]=1000000000+10000;
				}
				else {
					B[x]=B[2*x+1]-1;
					if(2*x+2 < N+i) B[x]=min(B[x],B[2*x+2]-1);
					while(S2.find(B[x])!=S2.end()) B[x]--;
					
					if(B[x]<0) ng++;
					S2.insert(B[x]);
				}
			}
		}
		
		if(ng==0) return _P("%d\n",i+N);
	}
	_P("-1\n");
}

まとめ

ここまでは何とか自力。