B. Belted Rooms (Codeforces Raif Round 1 Div. 1 + Div. 2)

というわけで、Cより難しかった？B問題です。

問題

https://codeforces.com/contest/1428/problem/B

問題概要

n個の部屋があり0からn-1の番号が振られている。各部屋はn個のコンベアで環状に繋がれている。それぞれのコンベアは、部屋番号の正方向に進む（n-1から0を含む）、部屋番号の負方向に進む（0からn-1を含む）、停止していてどちらにも進める、の状態のいずれかである。

各部屋からコンベヤを経由して一度別の部屋に出たあとにもとの部屋に戻りたい。それが可能な部屋はn個のうちのいくつあるか？

考察

コンベヤ全体が停止している場合、自由に往来が可能なので答えはnです。停止しているものと正方向に進むものしかない場合、正方向に進み続ければもとの位置に戻れるのでやはり答えはnです。停止しているものと負方向のみの場合も同様に答えはnです。

要するに、正方向と負方向が混在していなければ、常に答えはnです。

では混在していた場合ですが、部屋につながるコンベアのどちらかが停止しているものであれば、それを使って出てすぐ戻ることが可能です。両方が動いているコンベヤの場合、出られない（"><"）または入れない（"<>"）または戻ってこれない（"<<" or ">>" ）となるので、いずれも出戻ることが不可能です。

つまり、答えはつながっているコンベアのどちらかが停止している部屋の数、となります。

上記の出られないまたは入れないケースは自明だと思います。最後の戻ってこれない来れないケースですが、前提条件より最初に部屋を出た方向と逆向きのコンベアがどこかに必ずあり、その間から抜け出せなくなるので戻ってこれないとなります。例えばSをスタートとして"-->---<<S<<---"こういうケースで">---<"の部分に入ると抜け出せません。

#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, (n))
#define REPS(c, s) for (char c : s)
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        bool r = false;
        bool l = false;
        REPS(c, s) if (c == '>') r = true; else if (c == '<') l = true;
        if (!r || !l) {
            cout << n << endl;
            continue;
        }
        int ans = n;
        REP(i, n - 1) if (s[i] != '-' and s[i + 1] != '-') ans--;
        if (s[n - 1] != '-' and s[0] != '-') ans--;
        cout << ans << endl;
    }
}

感想

考察が完了すれば別になんてことはない問題なんですが、問題の意味自体を理解することの方が大変な、ある意味こどふぉっぽい問題だったかもしれません。