幸い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だけで順に稼いでるなぁ。