AtCoder ABC 187 C - 1-SAT (灰色, 300 点)

とにかく実装力を鍛えよう〜〜

• 問題へのリンク

問題概要

個の文字列が与えられる。そのうちのいくつかは先頭の文字が ! である (それ以外はすべて英小文字)。

red
gray
!orange
yellow
!blue
cyan
!green
brown
!gray

! の付いていない文字列と、付いている文字列とで、共通しているものがあれば、そのうちの 1 つを出力せよ。共通しているものがない場合はその旨を報告せよ。

制約

• 

考えたこと

問題設定が複雑だけど、結局こういう問題。

---

2 つの集合 が与えられる。それらの共通要素を求めよ。

---

こういうのは過去に何度も出題されている！！！いろんな方法があるけど、こういう風にできる。

• 集合 A の要素を std::set などで管理する
• 集合 B の要素を順に見ていって、A にも含まれるものがあれば、それを出力する

ここで、A に含まれるかどうかを判定する部分を高速化するために、std::set などを用いる。計算量は になる。

コード

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

int main() {
    int N;
    cin >> N;
    set<string> se1, se2;
    for (int i = 0; i < N; ++i) {
        string str;
        cin >> str;
        if (str[0] == '!') se1.insert(str.substr(1));
        else se2.insert(str);
    }
    
    string res = "";
    for (auto it: se1) if (se2.count(it)) res = it;
    if (res == "") cout << "satisfiable" << endl;
    else cout << res << endl;
}