ABC049 - C: 白昼夢 / Daydream

自爆して大変なことになった問題．

問題を解く上で勘違い，思い込み，先入観による WA は辛いよという話です．これらはコンテスト中になかなか気づけないと思うので，自分への教訓としてこの記事を書きました．

問題

• ABC049 - C: 白昼夢 / Daydream

解説

公式解説

• editorial

実装の方針としては，まず文字列の長さで篩にかけた． 文字列の長さと 5, 6, 7 の mod を計算し，ありえない文字数（例えば 8 文字では絶対に dream, erase, eraser, dreamer の組み合わせは無理）は取り除こうと場合分けをした．（結局ここが WA の元になった）

あとは丁寧に実装していけば難しい問題ではないと思う． 始めにdreamerを6文字だと勘違いしていてしばらくそれで WA を連発してしまった． それに気づいて提出したら WA が 1 つになった．ここからバグ取りを丁寧に始めた．

バグ取りで気をつけることは，度々学んでいる

• オーバーフロー
• コーナーケース

の二つである．今回のコードはオーバーフローを気にするところがなく，コーナーケースも分かりやすいものであるためなかなか見つけられなかった．

最終的に，mod による場合分けで NO と出力しているところを YES にしたら WA が別のところへ動いたので，そもそも場合分けの段階で間違っていたことがわかった．（本番でやるとペナルティで死ぬ）

私のコード中で振り分けに使った部分は以下である．

bool bool5 = (len%5 == 0 || len%5 == 1 || len%5 == 2);
bool bool6 = (len%6 == 0 || len%6 == 5 || len%6 == 1);
bool bool7 = (len%7 == 0 || len%7 == 5 || len%7 == 6);
if (bool5 || bool6 || bool7) {
    // 処理
} else {
    cout << "NO" << "\n";
    return 0;
}

5, 6, 7 で割り切った余りが条件を満たせば文字列が処理されるコードになっている．このコードのNOをYESにすると WA が別の場所へ移ったため，「場合分けをすり抜けかつ， 5, 6, 7 の組み合わせでその文字数にすることができる数字」があることが分かる．

間違ってフィルターにかかってしまうのは結局文字列を精査するので問題ないが，正解の文字列をNOとしてしまっているのが WA の原因だった．

場合分けを細かく見てみると，

• 5 の倍数
  • n%5 == 0（5, 10, 15, ..., 全て 5 文字 dream, erase を使う）
  • n%5 == 1（6, 11, 16, ..., 6 文字 eraser を使って文字数を調整できる）
  • n%5 == 2（7, 12, 17, ..., 7 文字 dreamer を使って文字数を調整できる）
• 6 の倍数
  • n%6 == 0（6, 12, 18, ..., 全て 6 文字を使う）
  • n%6 == 5（5, 11, 17, ..., 5 文字を使って文字数を調整できる）
  • n%6 == 1（7, 13, 19, ..., 7 文字を使って文字数を調整できる）
• 7 の倍数
  • n%7 == 0（7, 14, 21, ..., 全て 7 文字を使う）
  • n%7 == 5（5, 12, 19, ..., 5 文字を使って文字数を調整できる）
  • n%7 == 6（6, 13, 20, ..., 6 文字を使って文字数を調整できる）

※ 公倍数はどれかで場合分けに引っかかるので問題ない．

以上のような場合分けを行った．この中から穴を見つけ出す．とりあえず Python で 10 ~ 99 まで出力させてみた．

for i in range(10, 100):
    bool5 = (i % 5 == 0 or i % 5 == 1 or i % 5 == 2)
    bool6 = (i % 6 == 0 or i % 6 == 5 or i % 6 == 1)
    bool7 = (i % 7 == 0 or i % 7 == 5 or i % 7 == 6)
    if not(bool5 or bool6 or bool7):
        print(i)
        print("{}%5 = {}".format(i, i % 5))
        print("{}%6 = {}".format(i, i % 6))
        print("{}%7 = {}".format(i, i % 7))

出力

38
38%5 = 3
38%6 = 2
38%7 = 3
39
39%5 = 4
39%6 = 3
39%7 = 4
44
44%5 = 4
44%6 = 2
44%7 = 2
58
58%5 = 3
58%6 = 4
58%7 = 2
64
64%5 = 4
64%6 = 4
64%7 = 1
74
74%5 = 4
74%6 = 2
74%7 = 4
88
88%5 = 3
88%6 = 4
88%7 = 4
93
93%5 = 3
93%6 = 3
93%7 = 2
94
94%5 = 4
94%6 = 4
94%7 = 3
99
99%5 = 4
99%6 = 3
99%7 = 1

以上の数字の中に，私の作った場合分けをすり抜けつつ 5, 6, 7 を組み合わせてその文字数になれるものがたくさんあったということ．簡単に見つかってしまった．例えば，

38 = 5*2 + 7*4 = 10 + 28

39 = 5*1 + 6*1 + 7*4

が挙げられ，自分で作った場合分けは意味を成していないことが分かる．1 WA だったので惜しい気もするが，おそらくこれらの数字を上手く場合分けするのはできないと思われるので今回の方針は間違っていたと認めざるを得ない．

場合訳ありのコード：WA

気になった方用．飛ばして全く問題ない．

▶︎ソースコード展開

// ABC049_C
#include <iostream>
#include <string>
using namespace std;

int main() {    
    // input
    string str;
    cin >> str;
    
    // calculation
    string five, six, seven;
    unsigned long len = str.length();
    
    if (len < 5) {
        cout << "NO" << "\n";
        return 0;
    } else if (len == 5) {
        if (str == "dream" || str == "erase") {
            cout << "YES" << "\n";
            return 0;
        } else {
            cout << "NO" << "\n";
            return 0;
        }
    } else if (len == 6) {
        if (str == "eraser") {
            cout << "YES" << "\n";
            return 0;
        } else {
            cout << "NO" << "\n";
            return 0;
        }
    } else if (len == 7) {
        if (str == "dreamer") {
            cout << "YES" << "\n";
            return 0;
        } else {
            cout << "NO" << "\n";
            return 0;
        }
    } else {
        // amari 0
        bool bool5 = (len%5 == 0 || len%5 == 1 || len%5 == 2);
        bool bool6 = (len%6 == 0 || len%6 == 5 || len%6 == 1);
        bool bool7 = (len%7 == 0 || len%7 == 5 || len%7 == 6);
        if (bool5 || bool6 || bool7) {
            while (str.length() != 0) {
                five = str.substr(str.size()-1 -4, 5);
                if (five == "dream" || five == "erase") {
                    str.erase(str.end()-5, str.end());
                } else {
                    six = str.substr(str.size()-1 -5, 6);
                    if (six == "eraser") {
                        str.erase(str.end()-6, str.end());
                    } else {
                        seven = str.substr(str.size()-1 -6, 7);
                        if (seven == "dreamer") {
                            str.erase(str.end()-7, str.end());
                        } else {
                            cout << "NO" << "\n";
                            return 0;
                        }
                    }
                }
            }
            cout << "YES" << "\n";
            return 0;
        } else {
            cout << "NO" << "\n";
            return 0;
        }
    }
}

場合分けなしのコード：AC

場合分けの部分を取り除いたら AC した．ロジック部分は合ってたため全ての入力に対してそれを適用すれば OK だったということ．なんで場合分けをしてしまったんだろうか．

▶︎ソースコード展開

// ABC049_C
#include <iostream>
#include <string>
using namespace std;

int main() {
    // input
    string str;
    cin >> str;
    
    // calculation
    string five, six, seven;
    unsigned long len = str.length();
    
    if (len < 5) {
        cout << "NO" << "\n";
        return 0;
    } else if (len == 5) {
        if (str == "dream" || str == "erase") {
            cout << "YES" << "\n";
            return 0;
        } else {
            cout << "NO" << "\n";
            return 0;
        }
    } else if (len == 6) {
        if (str == "eraser") {
            cout << "YES" << "\n";
            return 0;
        } else {
            cout << "NO" << "\n";
            return 0;
        }
    } else if (len == 7) {
        if (str == "dreamer") {
            cout << "YES" << "\n";
            return 0;
        } else {
            cout << "NO" << "\n";
            return 0;
        }
    } else {
        while (str.length() != 0) {
            five = str.substr(str.size()-1 -4, 5);
            if (five == "dream" || five == "erase") {
                str.erase(str.end()-5, str.end());
            } else {
                six = str.substr(str.size()-1 -5, 6);
                if (six == "eraser") {
                    str.erase(str.end()-6, str.end());
                } else {
                    seven = str.substr(str.size()-1 -6, 7);
                    if (seven == "dreamer") {
                        str.erase(str.end()-7, str.end());
                    } else {
                        cout << "NO" << "\n";
                        return 0;
                    }
                }
            }
        }
        cout << "YES" << "\n";
        return 0;
    }
}

反省

自分で作ってしまった場合分け，思い込みにより盲目的な WA 探しをしてしまった（なんか日本語おかしい）．自分の場合分けが間違っているとは微塵も思わなかった．コンテスト中にこれをやらかすことを想像してしまうと怖い．コンテスト中では，ペナルティを気にせず条件を変えて WA の変化を見るという方法は当然できない．

ただ一つだけ良かった点は，場合分けの違和感に気づけたことである（所要時間 2 時間...）．少しずつ「これはおかしいやろ」という点に違和感をもてる感覚を身につけていきたい．実際自分が場合分けを行なった際には本当にそれが正しいのか神経を注いでチェックする以外にはなさそうである．

WA を取るための自分的方針

最後に WA を取るための方針を晒しておく．今回，勘違い関連の WA が新しく追加された．一茶色コーダーの拙い方針なので，これを見た方でここにも気をつけたほうがいいよという方はコメントお願いします．

• オーバーフロー関連

  • を超える数は long long型を使う（オーバーフローの記事）
  • C++ の整数演算では，2 の冪乗（，）の mod が暗黙に行われており，演算の結果が（0 を因子に持たなくとも） 0 になりうる．（前回の記事）

• TLE関連

  • は一回ループを回せる．（約 1 秒．けんちょんさんの記事）
  • は（C++なら？）一回ループを回せる．回せない．（参考問題とその解説p67）
  • は TLE になる．

• 勘違い関連 ← New!!

  • 問題の読み間違えで時間を溶かすな．丁寧に読め．
  • 場合分けをしたときに漏れを見つけるのは大変，確実に場合分けができているかちゃんと確認すること．（本記事）

最後まで読んでくださりありがとうございました．