kmjp's blog

競技プログラミング参加記です

Codeforces #614 Div1 B. Aroma's Search

この回なんかのアニメが元ネタなのかな。
https://codeforces.com/contest/1292/problem/B

問題

2次元座標上で無限個の点が与えられる。
ただ、この点の座標は初期値と漸化式の形で表現される。

また、別の初期位置が与えられる。
初期位置から、上下左右のみの移動を行い、最初の無限点のうちできるだけ多くの点を経由したい。
移動距離T以内で最大いくつの点を経由できるか。

解法

無限個の点といいつつ、漸化式の形から座標は点ごとに倍々以上のペースで増えるため、高々O(logT)個しか考えなくてよい。
また、経由する点は点の区間になる。

そこで、まず最初に到達する点を総当たりし、その後座標の昇順にいくつかたどって戻る場合と、逆に降順にたどってまた戻る場合を総当たりしよう。
対象の頂点数が少ないので、最初の到達点と折り返し位置を総当たりしてO(log^3(T))かかっても十分間に合う。

int N=0;
ll X[100],Y[100];
ll AX,AY,BX,BY;
ll SX,SY,T;
int num[100][100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X[0]>>Y[0]>>AX>>AY>>BX>>BY;
	cin>>SX>>SY>>T;
	for(;;N++) {
		X[N+1]=X[N]*AX+BX;
		Y[N+1]=Y[N]*AY+BY;
		//cout<<N+1<<" "<<X[N+1]<<" "<<Y[N+1]<<endl;
		
		if(X[N+1]>2LL*10000000000000000) break;
		if(Y[N+1]>2LL*10000000000000000) break;
	}
	N++;
	int ma=0;
	FOR(i,N) {
		ll lef=T-abs(SX-X[i])-abs(SY-Y[i]);
		int num=0;
		for(x=i;x<N;x++) {
			if(x>i) lef-=abs(X[x-1]-X[x])+abs(Y[x-1]-Y[x]);
			if(lef<0) break;
			num++;
			ma=max(ma,num);
			int cur=num;
			ll clef=lef;
			for(y=i-1;y>=0;y--) {
				if(y==i-1) clef-=abs(X[x]-X[y])+abs(Y[x]-Y[y]);
				else clef-=abs(X[y+1]-X[y])+abs(Y[y+1]-Y[y]);
				if(clef<0) break;
				cur++;
				ma=max(ma,cur);
			}
		}
		num=0;
		lef=T-abs(SX-X[i])-abs(SY-Y[i]);
		for(x=i;x>=0;x--) {
			if(x<i) lef-=abs(X[x+1]-X[x])+abs(Y[x+1]-Y[x]);
			if(lef<0) break;
			num++;
			ma=max(ma,num);
			int cur=num;
			ll clef=lef;
			for(y=i+1;y<N;y++) {
				if(y==i+1) clef-=abs(X[x]-X[y])+abs(Y[x]-Y[y]);
				else clef-=abs(X[y-1]-X[y])+abs(Y[y-1]-Y[y]);
				if(clef<0) break;
				cur++;
				ma=max(ma,cur);
			}
		}
		
	}
	cout<<ma<<endl;
	
}

まとめ

いまいち狙いのわからない問題。