エクサウィザーズ 2019 C - Snuke the Wizard (青色, 500 点)

頭の整理が大変！！！

問題へのリンク

問題概要

左から右に向かって 1 から N の番号がついた N 個のマスがあります。 各マスには文字が書かれており、マス i には文字 si が書かれています。また、各マスにははじめ 1 体のゴーレムがいます。

すぬけ君は Q 回呪文を唱え、ゴーレムたちを移動させました。

i 番目の呪文は文字 ti と di からなり、di は L か R のいずれかです。 すぬけ君がこの呪文を唱えると、ti が書かれた全てのマスについて、そのマスにいる全てのゴーレムが隣接するマスに移動します。移動する方向は di が L ならば左、R ならば右です。

ただし、マス 1 から左に移動しようとしたゴーレムと、マス N から右に移動しようとしたゴーレムは消滅します。

Q 回の呪文詠唱後に消滅していないゴーレムの総数を求めてください。

制約

• 

考えたこと

落ちるゴーレムは下図のように、一般に

• 左側の連続した区間
• 右側の連続した区間

になることがわかる。

よって、

• 左側の落ちる区間と、落ちない区間の境目
• 右側の落ちる区間と、落ちない区間の境目

をそれぞれ二分探索で求めることで問題を解くことができる。二分探索の判定関数部分は、

• 二分探索の区間 [low, high) の中点 mid に対して、スタート位置が mid であるようなゴーレムが左側に落ちたり、右側に落ちたりするかどうか

をシミュレーションすることで実装できる。シミュレーションには の時間を要するが、シミュレーションを行う回数が に抑えられるので、全体として で解くことができる。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
using pchar = pair<char,char>;

int simulate(const string &s, const vector<pchar> &td, int pos) {
    for (auto c : td) {
        if (s[pos] != c.first) continue;
        if (c.second == 'L') --pos;
        else ++pos;
        if (pos < 0) return -1; // 左に落ちる
        if (pos >= (int)s.size()) return 1; // 右に落ちる
    }
    return 0;
}

int solve(int N, const string &s, const vector<pchar> &td) {
    // 左側の境目
    int low = -1, high = N;
    while (high - low > 1) {
        int mid = (low + high) / 2;
        if (simulate(s, td, mid) == -1) low = mid;
        else high = mid;
    }
    int left_fall = high;

    // 右側の境目
    low = -1, high = N;
    while (high - low > 1) {
        int mid = (low + high) / 2;
        if (simulate(s, td, mid) == 1) high = mid;
        else low = mid;
    }
    int right_fall = N-1-low;

    return N - (left_fall + right_fall);
}

int main() {
    int N, Q; string s; cin >> N >> Q >> s;
    vector<pchar> td(Q);
    for (int i = 0; i < Q; ++i) cin >> td[i].first >> td[i].second;
    cout << solve(N, s, td) << endl;
}

別解

例えば

• 左側に落ちるゴーレムと、落ちないゴーレムの境目

は二分探索で求められるが、これは実は操作列を逆にシミュレートする方法でも解くことができる。具体的には

• 最後に左側に落ちるゴーレムがどういう軌跡をたどるのかを逆シミュレートする

という方法で実装することができる。