http://codeforces.com/contest/935/problem/B
N文字の命令列がある。
'U' -> (x,y)から(x,y+1)へ移動
'R' -> (x,y)から(x+1,y)へ移動
y=xのグラフの直線の左側と右側で国が分かれている。
頂点(0,0)から命令に従って移動していく時に国を何回またいだかを答えよ。
境界線上に乗るだけでは国をまたいだとは言わないとする。
解法
http://codeforces.com/contest/935/submission/35480451
シミュレーションしよう。
今、どの国にいるかをcurで表現する。
nxtが移動先の国である。
0なら国が未確定な状態、1なら左の国、2なら右の国とする。
国をまたぐ状況になれば答えをインクリメントする。
int N; string S; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> S; int x = 0, y = 0; int cur = 0; // 0: none // 1: left // 2: right int ans = 0; fore(c, S) { if (c == 'U') y++; else x++; int nxt; if (x == y) nxt = 0; else if (x < y) nxt = 1; else nxt = 2; if (cur == 1 and nxt == 2) ans++; if (cur == 2 and nxt == 1) ans++; if (nxt) cur = nxt; } cout << ans << endl; }