[Codeforces] Educational Codeforces Round 68 (Div. 2) C. From S To T

2019年7月15日2020年9月8日

問題

方針

題意

文字列 \( s \) に \( p\) に含まれる文字の数だけ任意の場所に挿入して、文字列 \(t\) を作ることができるか調べます。

文字が現れる頻度を計算する

各文字列についてどの文字の頻度を計算します。もし、 \( s \) のある文字の頻度が \( t \) よりも大きい場合、作ることはできません。また、\( s \) と \( p \) のある文字の頻度の合計が、\( t \) のものよりも小さい時、作ることはできません。

実際に文字列を作れるか調べる

上記の計算をクリアした文字列について実際に \( t \) を作れるかどうかを調べます。\( s \) と \( t \) の先頭の文字から調べていき、それぞれに対応するインデックスを \( i_s \), \( i_t\) とします。

1. \( i_s = |s| \) のとき、\(s \) の最後尾に文字を追加して \( t \) を作れるかどうかを調べます。
2. \( i_s < |s| \) のとき、\( s(i_s) = t(i_t) \) ならば、\(i_s\) と \(i_t\) をインクリメントします。\( s(i_s) \neq t(i_t) \) ならば、\(s(i_s) = t(i_t) \) となるように、\( p \) から文字を持ってきます。そして、\( i_t\) をインクリメントします。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s, t, p;
void count(string s, int cnt[]) {
  for (char c : s) {
    cnt[c - 'a']++;
  }
}
bool can_add(int a[], int b[], int c[], int k) {
  if (a[k] >= b[k]) return false;
  if (c[k] == 0) return false;
  a[k]++;
  c[k]--;
  return true;
}
bool check(int a[], int b[], int c[]) {
  int idx = 0;
  for (int i = 0; i < t.length(); i++) {
    int k = t[i] - 'a';
    if (idx == s.length()) {
      if (!can_add(a, b, c, k)) return false;
    } else {
      if (t[i] == s[idx]) {
        idx++;
      } else {
        if (!can_add(a, b, c, k)) return false;
      }
    }
  }
  return true;
}
int main() {
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> s >> t >> p;
    int cs[26]{}, ct[26]{}, cp[26]{};
    count(s, cs);
    count(t, ct);
    count(p, cp);
    for (int i = 0; i < 26; i++) {
      if (cs[i] > ct[i] || cs[i] + cp[i] < ct[i]) {
        cout << "NO\n";
        goto loop;
      }
    }
    if (check(cs, ct, cp)) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
    
    loop: {}
  }
  return 0;
}