Exawizards 2019 C. Snuke the Wizard

atcoder.jp

考察

• 青diffだが全然わからなくてかなり苦戦した。あることに気づけばあとは簡単。
• 各ゴーレムはあるゴーレムよりも向こう側に行こうと思うと、そのゴーレムと一緒に行動するしかない。すなわち、消滅するゴーレムは左右の端の連続した区間となる。
• この単調性に気づけばあとは二分探索するだけ

感想

• 軽く1時間は溶かしたと思う。なかなか解けないときは対象(今回ならば消える/残るゴーレム)一つ一つの性質ではなく集合全体の性質を考えてみる、というのを意識したい。
• 何かしらの単調性というのが鍵に成る問題は多い。特に1次元上の問題では今回のような性質を真っ先に疑えるような感覚を養っていけると理想。

Submission

void solve() {
  int N, Q;
  cin >> N >> Q;
  string s;
  cin >> s;
  vector<char> t(Q), d(Q);
  for (int i = 0; i < Q; i++) { cin >> t[i] >> d[i]; }
  auto check = [&](int x) {
    int pos = x;
    for (int i = 0; i < Q; i++) {
      if (s[pos] == t[i]) {
        if (d[i] == 'L')
          pos--;
        else
          pos++;
      }
      if (pos < 0) return -1;
      if (pos >= s.size()) return 1;
    }
    return 0;
  };
  int L, R;
  {
    int l = -1, r = s.size();
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (check(mid) < 0)
        l = mid;
      else
        r = mid;
    }
    L = r;
  }
  {
    int l = -1, r = s.size();
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (check(mid) > 0)
        r = mid;
      else
        l = mid;
    }
    R = l;
  }
  cout << R - L + 1 << endl;
  return;
}