mayoko’s diary

プロコンとかいろいろ。

JAG Practice Contest for ACM-ICPC Asia Regional 2015 D - Line Gimmick

解法

各場所よりも右にある "<" の数および左にある ">" の数を数えると, 最終的にどちら側にたどり着くかがわかります。
例えば >><<>> という文字列を考えた時, 左から 4 番目にある文字 "<" からスタートすることを考えたとすると, これより左側にある ">" の数は 2 つで, これより右側にある "<" の数は 0 なので, 一回左に進んだ後右に進んでいって終わり, ということになります。
こんな感じで, 最初に乗る記号, それより左にある ">" の数, 右にある "<" の数がわかれば, 結局 それぞれの記号をどれだけ消費してどこに到着するのかがわかります。

ということで, 累積和を取って 左側にある ">" の数, 右側にある "<" の数をメモして, あと それぞれの ">", "<" がどこにあるかをメモしておけば, 理論上答えを求めることが出来ます。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> toRsum(n+1), toLsum(n+1);
    for (int i = 1; i <= n; i++) {
        toRsum[i] = toRsum[i-1] + (s[i-1] == '>');
    }
    for (int i = n-1; i >= 0; i--) {
        toLsum[i] = toLsum[i+1] + (s[i] == '<');
    }
    vector<int> toR(n+1), toL(n+1);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '>') toR[cnt++] = i;
    }
    cnt = 0;
    for (int i = n-1; i >= 0; i--) {
        if (s[i] == '<') toL[cnt++] = i+1;
    }
    int ans = 1;
    for (int i = 0; i < n; i++) {
        int tl = toLsum[i+1], tr = toRsum[i];
        int tmp;
        if (s[i] == '<') {
            if (tl >= tr) tmp = toL[tl-tr];
            else tmp = n-toR[tr-tl-1];
        } else {
            if (tr >= tl) tmp = n-toR[tr-tl];
            else tmp = toL[tl-tr-1];
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

僕は非常に混乱しました。