yukicoder : No.808 Kaiten Sushi?

最初問題の趣旨を間違えてこんなん解けないだろ…となりかけた。
https://yukicoder.me/problems/no/808

問題

回転する長さLのテーブル上にN個の寿司とN個のお茶があり、現在位置からの距離が与えられる。
時刻1毎にテーブルが1回転するので、自分の目の前に寿司かお茶があるとき、それを取ってもよいし取らなくてもよい。
取った寿司・お茶はその場でなくなる。

寿司→お茶→寿司→…と交互に取っていって最終的に全部取り切るには、最短でどの程度の時間がかかるか。

解法

まず最寄りの寿司を取ろう。
以降、以下の手順でとっていく。

• 次に取る寿司は、１個以上お茶がきた後の最寄りの寿司である。
• 一方、お茶は上記寿司より手前であれば(後の周回を速く終えるために)できるだけ後ろの位置にあるものを取るのが望ましい。

よって寿司とお茶の位置をsetで持っておき、最寄りのお茶以降の最寄の寿司の位置を求め、その直前のお茶を取る、ということを繰り返せばよい。

int N;
ll L;
set<ll> A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	FOR(i,N) {
		cin>>x;
		FOR(j,4) A.insert(L*j+x);
	}
	FOR(i,N) {
		cin>>x;
		FOR(j,4) B.insert(L*j+x);
	}
	
	ll cur=0;
	ll ret=0;
	while(A.size()) {
		cur%=L;
		// 次の寿司
		auto it=A.lower_bound(cur);
		ret+=*it-cur;
		cur=*it%L;
		FOR(j,4) A.erase(L*j+cur);
		
		if(A.empty()) {
			ret+=*B.lower_bound(cur)-cur;
		}
		else {
			ll nexB=*B.lower_bound(cur);
			ll nexA=*A.lower_bound(nexB);
			auto it=B.lower_bound(nexA);
			it--;
			ret+=*it-cur;
			cur=*it%L;
			FOR(j,4) A.erase(B*j+cur);
		}
	}
	
	cout<<ret<<endl;
}

まとめ

最初開始位置も任意かと思って手間取った。