英文だし、題意をちゃんと読み解くのがちょっと大変

問題概要

L と R のみから構成された文字列 $S$ が与えられる。ロボットは最初北方向を向いている。文字列 $S$ を左から順番に読んで次のように処理していく。

L のとき、ロボットは 90 度左回転する
R のとき、ロボットは 90 度右回転する

文字列全体を通して、次の条件を満たす瞬間が何回あるかを数え上げよ。

現在の瞬間に至るまでの過程で、ある時点が存在して、指令 R によって「北」から「東」へと向いた
その時点から現在の瞬間に至るまで、一度も北を向くことはなかった
現在の瞬間、指令 R によって「西」から「北」へと向いた

つまり、北を向いた状態から北へ向いた状態へと一回転する行為が何回行われたかを数え上げよ。

制約

$1 \le |S| \le 1000$

考えたこと

やるだけなのだけど、次のケースでは「1」ではなく「2」と答えなければならない

RRRRLLLLRRRR

つまり「R で +1 して L で -1 して、総和を 4 で割る」は嘘ということになる。代わりに、次のように「状態遷移」を意識すると良さそう。

state 0：下記以外の状態
state 1：state 0 の状態から指令 R によって「東」を向いた瞬間 or state 2 の状態から指令 L によって「東」を向いた瞬間
state 2：state 1 の状態から指令 R によって「南」を向いた瞬間 or state 3 の状態から指令 R によって「南」を向いた瞬間
state 3：state 2 の状態から指令 R によって「西」を向いた瞬間

そして、state 3 から state 0 へ行く瞬間 (指令 R) において、答えに 1 を加算する。コーナーケースとしては、LLLRRR (答えは 0) などが怖い。

計算量は $O(|S|)$ 。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    int res = 0, dir = 0, state = 0;
    for (auto c : S) {
        if (c == 'L') dir = (dir + 3) % 4;
        else dir = (dir + 1) % 4;

        if (state == 0) {
            if (c == 'R' && dir == 1) state = 1;
            else state = 0;
        }
        else if (state == 1) {
            if (c == 'R' && dir == 2) state = 2;
            else state = 0;
        }
        else if (state == 2) {
            if (c == 'R' && dir == 3) state = 3;
            else state = 1;
        }
        else {
            if (c == 'R' && dir == 0) state = 0, ++res;
            else state = 2;
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2904 GuruGuru (JAG 夏合宿 2018 day3-A) (200 点)

問題概要

制約

考えたこと