kojingharangの日記

SRM 557 Div1 250 FoxAndMountainEasy

19:49 |

• １歩上か下に N 回移動する。最初の高さは H0 で最後の高さは HN であることがわかっている。途中、高さは0未満にはならない。
• 'U' or 'D' からなる文字列 S が与えられるので途中の上下動のパターンとしてありうるかどうかを答える。
• N≦100000, |S|≦50

• H0, HN の高さの差が N 回より大きい時は無理
• 全部上 or 全部下にいって余った分は上下の組になんないといけないので N-|H0-HN| は 2 で割り切れないとだめ
• H0, HN から上下それぞれの回数 U, D が決まる。H0＜HN なら上が HN-H0 回、に加えて上下の組が N-|H0-HN| コ。逆も同様。
• 文字列内の上下の回数 u, d が U, D に収まってないと無理
• 一時的にでも高さが 0 未満になっちゃだめなので、文字列内で一番下がる位置を覚えておいて
• 文字列の先頭としてありうる一番高い地点から始めて 0 未満になるならだめ
• だめじゃなければOK

• が！一番高いとこは H0 か HN の高い方だろうと早とちりして failed system test.

• 一番高くするには文字列の左にできるだけ上を置いて文字列の後にできるだけ下を置けばいいので
• 一番高いとこは H0 + U - u

↓あとで (accepted in practice)

class FoxAndMountainEasy {
	public:
	string possible(int n, int h0, int hn, string HI) {
		if(abs(h0-hn)>n) return "NO";
		if( (n-abs(h0-hn))%2 != 0 ) return "NO";
		int U=0, D=0, UD=0;
		if(h0<hn) U=abs(h0-hn);
		else      D=abs(h0-hn);
		UD = n-abs(h0-hn);
		U += UD/2;
		D += UD/2;
		int u=count(ALL(HI), 'U');
		int d=count(ALL(HI), 'D');
		if(U<u || D<d) return "NO";
		int Min=0;
		int pos=0;
		FOR(e, HI) {
			if(*e=='D') pos--;
			if(*e=='U') pos++;
			Min = min(Min, pos);
		}
		//if(abs(Min) > max(h0, hn)) return "NO";     // だめ
		if(abs(Min) > h0+U-u) return "NO";            // OK
		return "YES";
	}
};

ツイートする