AtCoder Regular Contest 041 C - ウサギ跳び

問題

　個のマスが横一列に並んでおり、マスの上には匹のウサギが右か左を向いている。ウサギは向いている方向の一つ前のマスに他のウサギがいなければジャンプしてそのマスへ移動できる。ウサギがジャンプする順番を自由に選べるとき、ジャンプの総回数の最大値を求めよ。

解法

　二匹のウサギが向き合っているとき、後ろに連続して同じ向きで待っているウサギがいる数の多い方のみがジャンプするのが最善となる。その数を数えて貪欲に動かせばでこの問題が解ける。

反省

　19分59秒(0WA)でAC。理屈から言って解けそうなのはすぐわかったが、何に注目して考えると考えやすい/実装しやすいかというのがちょっとわからなかった。結局番目のウサギが動くべきかどうかというのを全部最初に求めてしまうのがわかりやすいかと思ったが、コードは結構長くなってしまった。解説スライドでは区間に分けて考えるとあり、これはなかなか実践的な思考法なんだろうなと感じた。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, L;
    cin >> N >> L;

    struct Usagi {
        ll x, follow_num;
        char d;
        bool move;
    };
    vector<Usagi> usa(N);
    for (ll i = 0; i < N; i++) {
        cin >> usa[i].x >> usa[i].d;
        usa[i].move = true;
    }
    

    //右向きウサギについて数える
    ll num = 0;
    for (ll i = 0; i < N; i++) {
        if (usa[i].d == 'R') {
            usa[i].follow_num = num++;
        } else {
            num = 0;
        }
    }

    //左向きウサギについて数える
    num = 0;
    for (ll i = N - 1; i >= 0; i--) {
        if (usa[i].d == 'L') {
            usa[i].follow_num = num++;
        } else {
            num = 0;
        }
    }

    //i番目のウサギが動くかどうかについて考える
    //前にいるウサギがこちらを向いており
    //向こうの方が後ろに続くウサギが多かったらこっちは動かない
    for (ll i = 0; i < N - 1; i++) {
        if (usa[i].d == 'R' && usa[i + 1].d == 'L') {
            if (usa[i].follow_num < usa[i + 1].follow_num) {
                usa[i].move = false;
            } else {
                usa[i + 1].move = false;
            }
            i++;
        }
    }

    ll ans = 0;

    //右向きウサギを限界まで動かす
    //行ける一番右のマス
    ll limit = L;
    for (ll i = N - 1; i >= 0; i--) {
        if (usa[i].d == 'L' || !usa[i].move) {
            limit = usa[i].x - 1;
        } else {
            ans += limit - usa[i].x;
            usa[i].x = limit;
            limit--;
        }
    }

    //左向きウサギを限界まで動かす
    limit = 1;
    for (ll i = 0; i < N; i++) {
        if (usa[i].d == 'R' || !usa[i].move) {
            limit = usa[i].x + 1;
        } else {
            ans += usa[i].x - limit;
            usa[i].x = limit;
            limit++;
        }
    }

    cout << ans << endl;
}