【ABC219】C問題で犯したとんでもないミス

はじめに

AtCoder Beginner Contest 219に参加した。
いつもA, B, C問題はさらっと解けるので、D問題が解けるかどうかが肝になるはずだったが、 どうやってもC問題が解けない。結局A, B問題しか解くことができなかった。

終了後に解説を見ると、自分がとんでもないミスをしていたことに気が付いた。

提出したコード

このコードのどこがおかしいかわかるだろうか?

#include <bits/stdc++.h>
using namespace std;
 
// 置換表
map<char, char> m;
 
// 比較用の関数
bool comp(const string l, const string r) {
    string ls = "", rs = "";
    for (char c : l) {
        ls += m.at(c);
    }
    for (char c : r) {
        rs += m.at(c);
    }
    return ls < rs;
}
 
// メイン関数
int main() {
    string x;
    int n;
    cin >> x >> n;

    // 入力された文字列xから置換表を作成する
    for (int i = 0; i < x.length(); ++i) {
        m.insert(make_pair('a' + i, x.at(i)));
    }
    
    // sを受け取る
    vector<string> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s.at(i);
    }

    // 比較関数を渡してソート
    sort(s.begin(), s.end(), comp);
 
    // 結果を出力
    for (string str : s) {
        cout << str << endl;
    }
}

正解発表

おかしいのはこの部分。

    // 入力された文字列xから置換表を作成する
    for (int i = 0; i < x.length(); ++i) {
        m.insert(make_pair('a' + i, x.at(i)));
    }

make_pairの引数が逆である。
以下のように直せば通る。

    // 入力された文字列xから置換表を作成する
    for (int i = 0; i < x.length(); ++i) {
        m.insert(make_pair(x.at(i), 'a' + i));
    }

なぜこんなミスに気付かなかったのか

間違ったコードでサンプル(入力例)が通ってしまったのが大きな要因である。
この問題で与えられたサンプルは2通りあるのだが、そのいずれも誤ったコードで通ってしまう。
そのため、

コードを書き終わる
↓
サンプルを試してみる
↓
正解した
↓
自信満々に提出する
↓
WA(しかもサンプル以外すべて誤答)
↓
？？？？？？？？？？？  

という状況に陥ってしまった。

図1. サンプル以外の全テストケースでWAだった様子