Autumn Fest 2012 : F Vinculum

さて次の問題。
こちらも本番中はsmallのみ解けた。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_06

まずSmallから。
上からA[0]、A[1]、…、A[N-1]の数値がある場合、一番長い括線を入れる場所を再帰的に求める。
一番長い括線をA[k]とA[k-1]の間に入れた場合、A[0]～A[k]からなる数値の最大値からA[k+1]～A[N-1]からなる数値の最小値を求めて割ればよい。
よってこの処理は、A[i]～A[j]までの最大値・最小値を求める処理が再帰的に実行されるので呼び出し回数はO(N^2)。
さらに個々の関数では括線の入れる箇所を(j-i-1)箇所から探すので、併せて計算量はO(N^3)。

Smallならこれで通る。

int N;
int flag;
double A[10001];
int len[10001];
int mal[51][51],mil[51][51];
double ma[51][51],mi[51][51];


void dfs(int s,int t,int flag,int dep) {
	if(s+1==t) {
		return;
	}
	if(s+2==t) {
		len[s+1]=dep;
		return;
	}
	
	if(flag) {
		len[mil[s][t]]=dep;
		dfs(s,mil[s][t],1,dep+1);
		dfs(mil[s][t],t,0,dep+1);
	}
	else {
		len[mal[s][t]]=dep;
		dfs(s,mal[s][t],0,dep+1);
		dfs(mal[s][t],t,1,dep+1);
	}
}

double calc(int s,int t,int flag, int dep) {
	int tar,best;
	double da,r;
	if(s+1==t) { return A[s];}
	if(s+2==t) { 
		mal[s][t]=mil[s][t]=s+1;
		return A[s]/A[s+1];
	}
		
	
	
	da=0;
	if(flag) {
		//min
		if(mil[s][t]==0) {
			best=-1;
			for(tar=s+1;tar<t;tar++) {
				r = calc(s,tar, 1, dep+1) / calc(tar,t, 0, dep+1);
				if(best==-1 || r<da) {
					da=r;
					best=tar;
				}
			}
			mil[s][t]=best;
			mi[s][t]=da;
		}
		return mi[s][t];
	}
	else {
		if(mal[s][t]==0) {
			best=-1;
			for(tar=s+1;tar<t;tar++) {
				r = calc(s,tar, 0, dep+1) / calc(tar,t, 1, dep+1);
				if(best==-1 || r>da) {
					da=r;
					best=tar;
				}
			}
			mal[s][t]=best;
			ma[s][t]=da;
		}
		return ma[s][t];
	}
}

void solve() {
	int x,y,i,j,p,rr,TM,TTC;
	
	flag=0;
	N=GETi();
	FOR(i,N) {
		scanf("%lf",&A[i]);
		if(A[i]<0){ flag = 1-flag; A[i]=-A[i];};
	}
	
	ZERO(mal);
	ZERO(mil);
	if(N>=51) return;
	calc(0,N,flag,1);
	ZERO(len);
	dfs(0,N,flag,1);
	
	vector<pair<int,int> > num;
	FOR(i,N-1) {
		num.push_back(make_pair(10000-len[i+1],i));
	}
	sort(num.begin(),num.end());
	int resa[10001];
	FOR(i,N-1) {
		resa[num[i].second]=i+1;
	}
	FOR(i,N-1) {
		_P("%d\n",resa[i]);
	}
	
	
	return;
}

さてLarge。
先の方法はO(N^3)なので、N=10000では全然足りない。
また、10000回も除算をしているとdouble型に収まらない可能性がある。
よってもっと簡単な方法が必要。

今A[0]～A[M-1]の最大値が求まっており、最大の割線に対する分子をB、分母をCと置く。
（つまりA[0]～A[M-1]の最大値はである)
ここにA[M]を追加する場合、A[M]<1なら先の最大値をA[M]で割るとさらに大きな値を得られる()。
A[M]>1の場合、分母を割って分母を小さくしてやれば、さらに大きな値を得られる。()。

結局、これを再帰的に行うだけで良い。

• A[M]>=1ならA[M-1]とA[M]の間の長さを最長(M)にする。
• A[M]<=1ならA[M-1]とA[M]の間の長さを最長-1(M-1)にし、もともと最長だったところをM-1からMにする

これだとO(N)で処理が終わるし、実際にB,Cを求める必要が無いので桁あふれも気にしなくて良い。

なお、最初に全数値の符号をチェックして、全体が負になるなら絶対値を最小にしたいので、上の処理を大小逆にすればよい。

int N;
int flag;
double A[10001];
int len[10001];

void solve() {
	int x,y,i,j,p,rr,maxl;
	
	flag=0;
	N=GETi();
	FOR(i,N) {
		scanf("%lf",&A[i]);
		if(A[i]<0){ flag = 1-flag; A[i]=-A[i];};
	}
	
	ZERO(len);
	len[0]=1;
	maxl=0;
	
	for(i=1;i<N-1;i++) {
		if((A[i+1]>=1.0&&!flag) || (A[i+1]<=1.0&&flag)) {
			len[i]=len[maxl];
			len[maxl]=i+1;
		}
		else {
			len[i]=i+1;
			maxl=i;
		}
	}
	
	FOR(i,N-1) _P("%d\n",len[i]);
	
	return;
}

まとめ

なかなか面白い問題。
本番中にO(N^3)でsmallを解いた後、O(N^2)でも時間間に合わないし、O(N logN)位の手法を考えようとして頭抱えてたけど、ちゃんと考えるとO(N)で終わるんだね。