Zenn
📑

【ABC259】「C - XX to XXX」のメモ

2022/07/18に公開
AtCoder
競プロ
tech

概要

AtCoder Beginner Contest 259のC問題が解けなかったので、解説を見て得られた知見などを書いてみます。
https://atcoder.jp/contests/abc259/tasks/abc259_c

コンテスト中に書いたコード

コンテスト中にコードは書けませんでした。なんで解けなかったのかわからないレベルなのですが、今後の戒めとして恥を晒します。

解説を見て

「ランレングス圧縮」というキーワードが見えてがっくりしました。これだけで全てわかったので、解説や模範解答のコードはちゃんと見てないです。

書いたコードはこちらです。

#include <bits/stdc++.h>
using namespace std;

vector<pair<char, int>> rle(string s) {
    int size = s.size();
    vector<pair<char, int>> v;
    char c;
    int num = 0;
    for(int i = 0; i < size; i++) {
        if(i == 0) {
            c = s.at(i);
            num++;
            continue;
        }

        if(c != s.at(i)) {
            v.push_back({c, num});
            c = s.at(i);
            num = 1;
        } else {
            num++;
        }

        if(i == size - 1) {
            v.push_back({c, num});
        }
    }
    return v;
}

int main() {
    string s, t;
    cin >> s >> t;

    auto rle_s = rle(s);
    auto rle_t = rle(t);

    if(rle_s.size() != rle_t.size()) {
        cout << "No" << endl;
        return 0;
    }

    int size = rle_s.size();
    for(int i = 0; i < size; i++) {
        char sc = rle_s.at(i).first;
        char tc = rle_t.at(i).first;
        int sn = rle_s.at(i).second;
        int tn = rle_t.at(i).second;

        if(sc != tc) {
            cout << "No" << endl;
            return 0;
        }

        if(tn < sn) {
            cout << "No" << endl;
            return 0;
        }

        if(sn == 1 && tn != 1) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

ランレングス圧縮は、連続する文字列について、文字とその個数の情報に変換することで圧縮できるというものです。aaaaaならa5みたいな感じで表せます。今回は圧縮が目的ではなく、このように表せば比較しやすいということです。

問題文の意味は要するに「Sについては同じ文字が2文字以上連続している場合は、その部分を任意の文字数まで増やせる」ということです。
なので双方をランレングス圧縮した上で

  • 要素数が同じ
  • 個々の文字が同じ
  • 数値が以下のいずれか
    • 数値が同じ
    • Tの数値のほうが大きい、かつSの数値が1でない

を全て満たせばOKということになります。実装上の書き方は違いますが、意味的に同じように実装したのが上記になります。

教訓

ランレングス圧縮がそのまま出るようなケースはあまりないでしょうし、そもそも知らなかったとしても導出できるレベルだと思うので、汲み取るほどの教訓はあまりないかもしれません…
強いて言えば、どこかで「C問題はどうせ解けない」と思っている節があり、実際以上に難しく感じてしまうというか、本当は解けるのに諦めてしまっているというようなところがあります。
しかし今回の問題は明らかに現状の自分でも難なく解けるはずのレベルだったので、C問題は解けないとは必ずしも言えない、解けるかもしれないと考えを転換する必要があると思いました。

  • C問題でも解けるかもしれないので諦めない
  • C問題は解けるのが普通、というメンタルになるためにも精進が必要

Discussion