kmjp's blog

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

Codeforces #378 Div2 E. Sleep in Class

2500ptでもいい気がするけどなぁ。
http://codeforces.com/contest/733/problem/E

問題

N段の階段があり、初期状態で各段上下いずれかの向きが書かれている。
ある段にいるとき、向きに沿って1段移動し、移動元の段の向きを上限反転する。
これを最下段から下に行くか、最上段で上に行くまで繰り返す。

この処理を各段からスタートしたとき、何段移動を繰り返すか。

解法

移動の仕方を考えると、初期位置より上にある下向きの矢印の数と、下にある上向きの矢印の数の少ない方だけ初期位置を跨いで往復を繰り返す。
(初期位置の矢印の向きで±1個程度ずれる)

あとは上下それぞれ段数の累積和をもつことで、各初期位置に対応して往復回数から総移動段数をO(1)で求める事が出来る。

int N;
string S;

vector<ll> Us,Ds;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	Us.push_back(0);
	Ds.push_back(0);
	FOR(i,N) {
		if(S[i]=='U') Us.push_back(Us.back()+i);
		if(S[i]=='D') Ds.push_back(Ds.back()+i);
	}
	int NU=0,ND=Ds.size()-1;
	x=y=0;
	FOR(i,N) {
		if(S[i]=='D') y++;
		int y2=Ds.size()-1-y;
		ll ret;
		if(S[i]=='U') {
			if(y2<=x) {
				ret = 2*((Ds.back()-Ds[y])-1LL*y2*i)+N-i;
				ret += 2*(1LL*i*y2-(Us[x]-Us[x-y2]));
			}
			else {
				ret = 2*((Ds[y+x+1]-Ds[y])-1LL*(x+1)*i);
				ret += 2*(1LL*i*x-Us[x])+i+1;
			}
			x++;
		}
		else {
			ret=-1;
			if(x>y2) {
				ret = 2*((Ds.back()-Ds[y])-1LL*y2*i)+N-i;
				ret += 2*(1LL*i*(y2+1)-(Us[x]-Us[x-(y2+1)]));
			}
			else {
				ret = 2*((Ds[y+x]-Ds[y])-1LL*(x)*i);
				ret += 2*(1LL*i*x-Us[x])+i+1;
			}
			
		}
		
		_P("%I64d ",ret);
	}
	_P("\n");
	
	
}

まとめ

これ系の問題、デバッグ中配列アクセスの1ずれが頻発して辛い。