kmjp's blog

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

AtCoder ARC #041 : C - ウサギ跳び

幸いFAでした。
http://arc041.contest.atcoder.jp/tasks/arc041_c

問題

1~NのNマスが左右1列に並んでいる。
一部のマスには、左右どちらかを向いたウサギがいる。
各ウサギは、向いた向きにマスが存在し、かつ他のウサギがいないなら1つマスを進めることができる。

各ウサギを最適な順で動かす場合、最大何回ウサギを動かせるか。

解法

各ウサギは、基本的に前方に進めるだけ進むのが良い。

問題は、右向きのウサギと左向きのウサギが向かい合っている場合、どちらを進ませるかである。
ここは、後ろにいる同じ向きのウサギが多い方を優先的に動かすことで、移動回数を最大化できる。

int N,L;
int X[101010];
int T[101010];
int LL[101010], RR[101010];
string D[101010];
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	
	FOR(i,N) cin>>X[i]>>D[i];
	FOR(i,N) if(D[i]=="R") LL[i]=((i>0)?(LL[i-1]):0)+1;
	for(i=N-1;i>=0;i--) if(D[i]=="L") RR[i]=((i<N-1)?(RR[i+1]):0)+1;
	
	MINUS(T);
	FOR(i,N) {
		if(i==0 && D[i]=="L") T[i]=1;
		if(i==N-1 && D[i]=="R") T[i]=L;
		if(i<N-1 && D[i]=="R" && D[i+1]=="L") {
			if(LL[i]>=RR[i+1]) {
				T[i]=X[i+1]-1;
				T[i+1]=X[i+1];
			}
			else {
				T[i]=X[i];
				T[i+1]=X[i]+1;
			}
			i++;
		}
	}
	
	FOR(i,N) {
		if(D[i]=="L") {
			if(T[i]==-1) T[i]=T[i-1]+1;
			ret +=X[i]-T[i];
		}
	}
	for(i=N-1;i>=0;i--) {
		if(D[i]=="R") {
			if(T[i]==-1) T[i]=T[i+1]-1;
			ret +=T[i]-X[i];
		}
	}
	cout<<ret<<endl;
	
	
}

まとめ

BCのFAだけで順に稼いでるなぁ。