kmjp's blog

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

Codeforces #298 Div2 E. Berland Local Positioning System

Codeforces

途中色々混乱もしたが、最終的には割とシンプル。
http://codeforces.com/contest/534/problem/E

問題

1～Nのバス停が一直線の道路上にあり、各位置はA[i]である。
バスがあるバス停から出発し、バス停1とNの間を往復した。
その際経由したM個のバス停の番号が、到達順でなく番号順に与えられる。

ここからバスの移動距離を求めよ。一意に求まらない場合はそう答えよ。
なお、与えられる通過したバス停情報は、実現可能なパターンしか与えられない。

解法


バスの周期Pはバス停2(N-1)個分である。
もしM%P==1の場合、バスは正確にM/P周したのでその距離を答えればよい。

以後、M%P≠1の場合を前提とする。
まず各バス停の通過回数Q[i]を数え上げてしまう。
次に周回分は先に処理してしまおう。すなわち何処をどう走ってもM/P周分は走るので、距離M/P*(A[N]-A[1])分は無条件で走るし、その過程で1番とN番はM/P回、2～(N-1)番はM/P*2回は通る。
その分を通過回数を減らしてしまおう。

後は1番とN番の通過回数により以下のように場合分けすると良い。

  • 1番もN番も通ってない：
    • Q[s]=1となる最小のsとQ[t]=1となる最大のtを求める。s→tに移動したと考えて(先の周回分に加え)A[t]-A[s]が解。
  • 1番は通ったがN番は通ってない
    • Q[s]==2となる最大のsとQ[t]>=1となる最大のtを求める。s→1→tに移動したと考えて(先の周回分に加え)(A[t]-A[1]+A[s]-A[1])が解。
  • N番は通ったが1N番は通ってない
    • 上記を左右反転して考えればよい。
  • 1番もN番も通った場合。
    • s→1→(N-1)→tと折り返したと考える。
    • sはQ[s+1]=1となる最少のs、QはA[t-1]=1となる最少のtと考えると、解は(先の周回分に加え)(A[s]-A[1] + A[N-1]-A[t])
    • 注意点として、Q[2]～Q[N-2]が全て2の場合、どこがs,tが確定できない。その場合全パターン計算し、解が一意かチェックする。
int N,M,B[505050];
int num[303030];
ll A[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	cin>>M;
	FOR(i,M) cin>>x,num[x-1]++;
	
	if(M%(2*(N-1))==1) {
		cout<< M/(2*(N-1))*2*(A[N-1]-A[0]) << endl;
		return;
	}
	
	ll per=M/(2*(N-1));
	M%=(2*(N-1));
	if(M==0) per--, M+=2*(N-1);
	
	ll ret=per*2*(A[N-1]-A[0]);
	num[0]-=per;
	num[N-1]-=per;
	for(i=1;i<=N-2;i++) num[i]-=2*per;
	
	if(num[0]==0 && num[N-1]==0) {
		l=N,r=0;
		for(i=1;i<=N-2;i++) if(num[i]) l=min(l,i), r=max(r,i);
		ret += A[r]-A[l];
	}
	else if(num[0]==0 && num[N-1]) {
		for(i=1;i<=N-2;i++) while(num[i]) {
			ret += A[N-1]-A[i];
			for(x=i;x<=N-2;x++) num[x]--;
		}
	}
	else if(num[0] && num[N-1]==0) {
		for(i=N-2;i>=1;i--) while(num[i]) {
			ret += A[i]-A[0];
			for(x=1;x<=i;x++) num[x]--;
		}
	}
	else if(num[0] && num[N-1]) {
		for(i=1;i<=N-2;i++) if(num[i]!=2) {
			ret += A[i-1]-A[0];
			break;
		}
		if(i==N-1) {
			FOR(i,N-1) if(A[i+1]-A[i] != A[1]-A[0]) return _P("-1\n");
			cout<< ret + 2*(A[N-1]-A[0])-(A[1]-A[0]) << endl;
			return;
		}
		
		ret += A[N-1]-A[0];
		for(i=N-2;i>=1;i--) if(num[i]!=2) {
			ret += A[N-1]-A[i+1];
			break;
		}
	}
	
	cout<<ret<<endl;
}

まとめ

バス停経路として、validじゃないものも許可すると面白かったかも。
その場合、各バス停を始点として(M-1)回移動したと仮定した場合、Q[i]がそれぞれ矛盾しないかRange Minimum/Maximum Queryを用いて判定できるね。