Fafa and the Gates [Codeforces Round #465 B]

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;
}