kmjp's blog

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

Codeforces #320 Div1 E. Walking!

これで通しちゃっていいのかな。
http://codeforces.com/contest/578/problem/E

問題

道に沿ってN個の足跡が順に並んでおり、左右どちらの足の足跡かが与えられる。

基本的にはこの足跡は文字列の先頭から後ろの方向に移動しながら、左右交互につけていく。
(1回で1文字以上移動することもある)

ただ、それだけだと与えられた足跡群が再現できない可能性がある。
そこで何度か逆向きに移動しても良いことにする。
足跡群を再現するのに必要な最小限の逆向き移動回数を求めよ。

解法

逆向きに移動すると考えると難しいので、足跡群を何周もして全足跡を1回ずつたどると考える。
すると、周回数-1が解となる。
先に右足から始める場合と左足から始める場合2通り試して周回数が小さい方を取る。

ここまではEditorialと同じ考え方だが、以下はEditorialとは異なる。
setで右足と左足の未到達な位置の一覧を管理する。
そうすると現在位置とlower_boundを使って、次に使う足の最寄の(未到達の)位置が求められる。

残された足跡群のうち、最も先頭に近いものが例えば左足だとすると、どこか右足を踏んだあと次の周回に入ってその左足を踏まなければならない。
つまり、右足を踏んだ段階で以降で再度右足を踏むアテが無ければ、その時点で戻って左足を踏んだ方が良いことになる。

上記考察より、現在位置と今使った足から、次に反対側の足を踏む位置は以下のように求めればよい。

  • 今の位置より後ろの最寄りの反対の足を置ける場所がないなら、次の周に入って先頭に最寄の反対の足の場所を踏む。
  • 今の位置より後ろの最寄りの反対の足を置ける場所があり:
    • さらにその後ろに今と同じ足を置ける場所があるなら、「最寄りの反対の足を置ける場所」を反対側の足で踏む。
    • そうでない場合、残された足跡全体のうち先頭に近い足跡が今と反対の足なら、戻ってそれを踏む。今と同じ足なら、ひとまずさっき求めた最寄の反対の足の場所を踏む。
int D;
string SS;
int L;
vector<int> R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>SS;
	L=SS.size();
	
	int mi=1<<20;
	
	FOR(i,2) {
		set<int> S[2];
		FOR(j,L) S[(SS[j]=='R')^i].insert(j);
		
		if(S[0].size()<S[1].size()) continue;
		vector<int> v;
		
		int cur=-1, next=0, ret=0;
		while(S[0].size() || S[1].size()) {
			
			if(cur==-1) {
				cur=*S[next].begin();
				S[next].erase(S[next].begin());
				v.push_back(cur+1);
				next ^= 1;
			}
			else {
				auto it=S[next].lower_bound(cur);
				if(it==S[next].end()) {
					ret++;
					cur=-1;
				}
				else {
					auto it2=S[next^1].lower_bound(*it);
					if(it2!=S[next^1].end() || (*S[next].begin()>*S[next^1].begin())) {
						cur=*it;
						S[next].erase(*it);
						v.push_back(cur+1);
						next^=1;
					}
					else {
						ret++;
						cur=-1;
					}
				}
			}
		}
		if(ret<mi) mi=ret, R=v;
	}
	
	cout<<mi<<endl;
	FORR(r,R) cout<<r<<" ";
	cout<<endl;
}

まとめ

戻ると考えるとややこしいが、何周もすると考えると単純になるね。