AtCoder Beginner Contest 187 C - 1-SAT

問題

問題文へ

N個の文字列が与えられます。各文字列は、英小文字からなる空でない文字列の先頭に!を0文字か1文字付加したものです。

文字列Tは先頭に!を0文字付加しても1文字付加してものいずれかに一致するとき、不満な文字列といいます。

不満な文字列があるかどうか判定し、あれば1つ示してください。

制約

• 1 N 2 10⁵
• 1 10
• は英小文字からなる空でない文字列の先頭に!を0文字か1文字を付加したものである。

考えたこと

!の付加されていない文字列の集まりを考えます。!の付加された文字列から!を取り除いたものが、その集まりに含まれればそれが不満な文字列でしょう。

文字列を探す処理はstd:mapに任せれば、時間は間に合うと考えました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
    int N;
    cin >> N;
    vector<string> v(N);
    rep(i, N) cin >> v[i];

    map<string, int> mp;
    rep(i, N) {
        if (v[i][0] != '!') {
            mp[v[i]]++;
        }
    }

    rep(i, N) {
        if (v[i][0] == '!') {
            string t = v[i].substr(1);
            if (mp[t] != 0) {
                cout << t << endl;
                return 0;
            }
        }
    }

    cout << "satisfiable" << endl;

    return 0;
}

解説を読んで

なぜ、私は!付きの文字列をもとに調べたのだろう？