AOJ 3166 Not Found (HUPC 2020 day1-C) (1D)

単純に bit 全探索で良さそう。

• 問題へのリンク
• editorial

問題概要

長さ の 0 と 1 からなる文字列が 個与えられる ()。以下の条件を満たす文字列 が存在するかどうかを判定し、存在するならば具体例を一つ与えよ。

• の長さは
• は '0' と '1' と '*' のみで構成される
• に含まれる '0' と '1' の個数の合計値は 20 以下である
• 中の各 * をどのように 0 や 1 に置き換えても、 は のいずれとも一致しない

制約

• 

考えたこと

ならば単純に bit 全探索できる。

ならば、 となるはずなので、最初の 20 文字の時点で のどれとも異なるパターンを作ることができる。

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

int main() {
    int N, M;
    cin >> N >> M; // 長さ N、M 個
    vector<string> fi(M);
    for (int i = 0; i < M; ++i) cin >> fi[i];
    
    int len = min(20, N);
    set<string> se;
    for (int i = 0; i < M; ++i) se.insert(fi[i].substr(0, len));
    string res = "";
    for (int bit = 0; bit < (1<<len); ++bit) {
        string ans = "";
        for (int i = 0; i < len; ++i) {
            if (bit & (1<<i)) ans += "1";
            else ans += "0";
        }
        if (!se.count(ans)) res = ans;
    }
    if (res == "") cout << "hokudai" << endl;
    else cout << res + string(N - len, '*') << endl;
}