AtCoder エクサウィザーズ 2019 C - Snuke the Wizard

問題

atcoder.jp

考察と解法

まず、全探索を行う場合を考えます。 1回の呪文ごとにゴーレムの移動をシミュレートするのに最大N体のゴーレムを移動させる必要があり、全部で呪文をQ回唱えるため、最悪時間計算量はとなります。 もちろんなので一生計算が終わりません。 マスをノード、ゴーレムの移動をエッジに見立てたグラフを考えたりもしましたが、あまり良い方法は思いつかなかったので悪あがきはやめて大人しく問題と向き合うことにします。

呪文について考えると、以下の性質がわかります。

1. 呪文ごとに動く方向は異なるが、1回の呪文でゴーレムは1マス分しか移動しない。
2. ある状態で同じマスに滞在しているゴーレムは必ずそれ以降は同じ動きになる。

上の2つの性質から、呪文をどのように唱えてもゴーレムが他のゴーレムを飛び越えられないことがないことがわかります。 つまり、ゴーレムの並び順は呪文をいくら唱えても初期状態から変化しません。 また、考えるのを簡単にするために、マスををに拡張します。 こうすることで、ゴーレムの消滅はiマス目のゴーレムの0かN+1番目のマスへの移動で表現できます。
以上のことから、Q回の呪文を唱える間に

1. iマス目のゴーレムが0番目のマスに移動するならjマス目(0 < j < i)のゴーレムも0番目のマスに移動
2. iマス目のゴーレムがN+1番目のマスに移動するならjマス目(i < j < N + 1)のゴーレムもN+1番目のマスに移動

することがわかります。 これをさらに抽象化して、以下の2つの関数を定義します。

1. : 初期位置xマス目のゴーレムが呪文をQ回唱える間に0番目のマスに移動するなら1そうでないなら0
2. : 初期位置xマス目のゴーレムが呪文をQ回唱える間にN+1番目のマスに移動するなら1そうでないなら0

するとは単調減少、は単調増加であることがわかります。 したがって、これらの関数はxの値で二分探索を行えます。 そこで、二分探索を用いてを満たす最大のxとを満たす最小のxを求め、それぞれをa, bとします。 これは初期位置がのゴーレムが消滅することを意味しているため、最終的な解はa + (N + 1 - b)となります。

実装の工夫

実は上で説明したようにf(x)とg(x)にわけて実装するのは少し面倒くさいです。 理由はf(x)が単調減少、g(x)が単調増加と、2つの関数がそれぞれ異なる性質を持つからです。 これは2パターンの二分探索を実装する必要があります。 そこで、少し楽をするために初期のマスの状態を逆順(ABC → CBA)にしたものと全てのを逆方向にしたもの('L' → 'R')を用意します。 すると、g(x)で求めようとしていた情報をf(x)で同じように求めることができます。 新たに用意したマスと呪文を利用して求めたaは元のマスと呪文を利用して求めた(N + 1 - b)と等しくなります。

計算量

a, bを求めるためにx(0 < x < N + 1)について二分探索を行うため、O()
f(x), g(x)を求めるのは、初期位置がxマス目のゴーレムの1体だけシミュレーションすればよいため、O()

したがって、全体での時間計算量はO()になります。

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// x番目のゴーレムをk番目のマスに移動させられるかシミュレートして確認する
bool checkLeft(int x, int k, string &s, vector<char> &t, vector<char> &d)
{
    for(int i = 0; i < t.size(); ++i)
    {
        if(t[i] == s[x])
        {
            x += (d[i] == 'L' ? -1 : 1);
        }
 
        if(s[x] == '_')
        {
            // マスの端に到達してもx == kが成り立つとは限らないことに注意する
            return x == k;
        }
    }
 
    return false;
}
 
int main()
{
    int n, q;
    string s;
 
    cin >> n >> q;
    cin >> s;
 
    // 消滅判定を簡単にするためにマスの両端に'_'をくっつけておく
    s = "_" + s + "_";
 
    vector<char > t(q);
    vector<vector<char> > d(2, vector<char>(q));
    for(int i = 0; i < q; ++i)
    {
        cin >> t[i] >> d[0][i];
        // マスの配置を反転させると操作も反転することに注意する
        d[1][i] = (d[0][i] == 'L' ? 'R' : 'L');
    }
 
    int golem = n;
    for(int i = 0; i < 2; ++i)
    {
        // 0マス目に到達する最も右のゴーレムの位置を二分探索する
        int lb = 0, m, ub = n + 1;
        while(ub - lb > 1)
        {
            m = (ub + lb) / 2;
            (checkLeft(m, 0, s, t, d[i]) ? lb : ub) = m;
        }

        // lbの位置にいるゴーレムより左にいるゴーレムは消滅する
        golem -= lb; 

        // 列を反転させてからもう一度同じ操作を行う
        reverse(s.begin(), s.end());
    }
 
    cout << golem << endl;
}

感想

初めて500点問題を自力で解くことができました。問題の中で単調増加性を発見した時には感動してため息が出てしまいました。