はまやんはまやんはまやん

hamayanhamayan's blog

XX to XXX [AtCoder Beginner Contest 259 C]

競技プログラミング

https://atcoder.jp/contests/abc259/tasks/abc259_c

あるといい知識

  • （自分の解法では）ランレングス圧縮

解説

https://atcoder.jp/contests/abc259/submissions/33113322

ランレングス圧縮というものを知っていると少し解きやすかったかもしれない。

性質を探る

どうやったらSに変換処理を加えていってTにできるかを考えてみる。
簡単な性質から考えてみよう。

変換処理では2つ以上同じ文字が並んでいるときに、その文字を増やすような処理ができる。
既にある文字しか増やせないし、かつ、その同じ文字の隣にしか増やせない。
つまり、どのように変換しても存在しない文字は生み出せないし、変換によって文字の種類の順番を入れ替えることはできない。
ここから重要な性質として言えるのが
「Sに含まれる同じ文字をグループ化したときに同じような文字種構成になっていないといけない」
ことが分かる。

入力例1で考えてみる

abbaac
abbbbaaac

同じ文字をグループ化してみよう

[a][b][a][c]
[a][b][a][c]

同じような見た目になった。
このようなグループ化を行った場合にTが[a][b][c]や[a][b][a][b]のようになった場合は変換できない。
同じ見た目であれば、必ず変換可能だろうか？

更に性質を探る

入力例2がちょうどいい。

xyzz
xyyzz

同じ文字をグループ化してみよう

[x][y][z]
[x][y][z]

同じ見た目になったが、答えはNoが正しい。
これはSのyは1つなので、変換ルールを使って2つ以上に増やすことができないためである。
このような個数にまつわるルールがありそうだが、この変換ではそれを評価することはできない。グループ時に個数も保持することにしよう。

[x1][y1][z2]
[x1][y2][z2]

こうやって見てみると、個数が同じものは変換が必要ないので無視できて、yだけを評価すればいいが、
Sのyが1個なので、2個に増やすことができないので変換できないとなった。
この形式であれば適切な評価ができそうだ。

ルールをまとめる

まずは、S,Tに対して、同じ文字について個数をまとめる変換をしよう。xyyzz -> [x1][y2][z2]
グループの個数が同じで、かつ、出てくる文字の種類と順番が等しければ、大きなまとまり的にはOK。
各グループが変換できるかを考えると、

  • [x1] -> [x1] は何もしないからOK
  • でも、[x1] -> x[2]は1個しかないので無理
  • [x2] -> [x4] のように元々2個以上あれば、元々あった個数以上に増やすことは可能
  • 逆に[x2] -> [x1]のように元々あった個数以上に増やすことは無理

といった感じになるので、「1->1」、もしくは、「2以上->元々の個数以上」であればOKということになる。
これらを全てチェックして問題なければYes, 1つでもダメならNoを返すと答えになる。

実装は？

実装で躓いた人もいるかもしれない。
この文字種でグループ化して個数と共に保持するという変換方式は「ランレングス圧縮」と呼ばれる圧縮方法となる。
ランレングス圧縮のアルゴリズムについては、恐らく検索してもらった方が記事の質もいいし、早いので
「ランレングス圧縮 競プロ」あたりで検索して勉強するといいと思う。

自分の実装ではランレングス圧縮したら {文字,個数} の配列が圧縮結果として出力される関数を用意して
全体の実装を行った。
main関数だけ追ってもらえれば、全体の雰囲気が分かるかもしれない。

vector<pair<char, int>> runLengthEncoding(string s) {
    int n = s.length();

    vector<pair<char, int>> res;
    char pre = s[0];
    int cnt = 1;
    rep(i, 1, n) {
        if (pre != s[i]) {
            res.push_back({ pre, cnt });
            pre = s[i];
            cnt = 1;
        }
        else cnt++;
    }

    res.push_back({ pre, cnt });
    return res;
}







string S, T;

#define YES "Yes"
#define NO "No"
string solve() {
    auto vs = runLengthEncoding(S);
    auto vt = runLengthEncoding(T);

    if (vs.size() != vt.size()) return NO;
    
    int N = vs.size();
    rep(i, 0, N) {
        if (vs[i].first != vt[i].first) return NO;
        if (vs[i].second > vt[i].second) return NO;
        if (vs[i].second == 1 && 1 < vt[i].second) return NO;
    }

    return YES;
}

void _main() {
    cin >> S >> T;
    cout << solve() << endl;
}