AtCoder ABC 157 C - Guess The Number (300 点)

全探索した！
整数を string 型にするのに手こずってしまった。

問題へのリンク

問題概要

以下の条件を満たす整数があれば、それを出力し、存在しなければ -1 を出力せよ。

• ちょうど 桁である
• 左から数えて 桁目は である。()

制約

• 
• 

考えたこと

存在しない場合というのは、たとえば

• のように、等しい に対して の値が異なるような場合
• であって であるような場合 (leading zero)

というのがある。これらを丁寧に考えれば解けるはずだけど、ちょっとややこしくてミスりそうなので、全探索することにした。 ということは 0 以上 1000 未満の整数をすべて調べれば OK。

判定方法

整数 が条件を満たすかどうかを判定するには、次のように、文字列に変換しておくと楽そう。

• を文字列型に変換する
• その長さが に一致しなかったらダメ
• 桁目が になっているかどうかを check する

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

int N, M;
vector<int> s, c;

bool ok(string str) {
    if (str.size() != N) return false;
    for (int i = 0; i < M; ++i) if (str[s[i]] != (char)(c[i] + '0')) return false;
    return true;
}

string solve() {
    for (int i = 0; i <= 999; ++i) {
        stringstream iss; iss << i;
        string str = iss.str();
        if (ok(str)) return str;
    }
    return "-1";
}

int main() {
    cin >> N >> M;
    s.resize(M); c.resize(M);
    for (int i = 0; i < M; ++i) cin >> s[i] >> c[i], --s[i];
    cout << solve() << endl;
}