この辺りから難しくなって来てる。「 $a, b, c$ で合格・不合格」という条件をどのように適切に言い換えるかが問われている。

問題へのリンク

問題概要

電源が $A$ 個、モーターが $B$ 個、ケーブルが $C$ 個ある。電源は $1, 2, \dots, A$ と番号づけられていて、モーターは $A+1, A+2, \dots, A+B$ と番号づけられていて、ケーブルは $A+B+1, A+B+2, \dots, A+B+C$ と番号づけらている。

電源とモーターとケーブルを 1 個ずつ組み合わせて製品ができる。3 つの部品がすべて正常だと、製品は「合格」となる。3 つの部品のうち 1 つ以上が故障していると、製品は「不合格」となる。

今、 $N$ 個の情報が与えられる。各情報は「電源 $a$ とモーター $b$ とケーブル $c$ を組み合わせてできる製品が合格であるか不合格しているか」を表す。

この情報から、各部品について

0：確実に故障していると言える
1：確実に正常であると言える
2：故障しているか正常であるかを言い切れない

を答えよ。

制約

$1 \le A, B, C \le 100$
$1 \le N \le 1000$

Step 1：合格製品から考える

この手の問題で問われていることは、今後より高度な問題を解くときにも必要になるイメージ。なので教育的問題と言えそう。

まず、「製品が合格」という情報のみを抽出して処理していくことにする。部品 $a, b, c$ からできる製品が正常ならば、 $a, b, c$ は確実に正常であるとしてよい。

こうして、確実に正常である部品はすべて洗い出すことができる。この段階で「確実に正常」とはならなかった部品は、今後「確実に正常」となることはない。

Step 2：不合格製品を考える

続いて、不合格製品を考えていこう。この場合は、合格製品ほど強い情報は得られない。部品 $a, b, c$ からなる製品が不合格だとしても、 $a, b, c$ のうち 1 個以上が故障していることしかわからない。

しかし、 $a, b, c$ のうちの 2 個が正常であれば、残りの 1 個が異常であると分かる。逆に、それ以外の場合で「確実に異常」を特定できることはあり得ない。たとえば、

$a, b, c$ の 3 つが「確実に正常」となることは問題の制約からあり得ない
$a$ が「確実に正常」で、 $b$ が「確実に異常」だとすでにわかっているとき： $c$ が正常か異常かはわからない
$a, b$ がともに「正常か異常か分からない」場合、 $c$ は正常か異常かはわからない

などというふうになっている。他の場合も同様に確認できる。

また、Step 1 で、確実に正常と言える部品はすべて洗い出されているため、考慮する不合格製品の順序はなんでもよいし、不合格製品たちを完全に独立に考えて大丈夫。

以上の解法の計算量は $O(N+ A + B + C)$ となる。

コード

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

int main() {
    // 入力
    int A, B, C, N;
    cin >> A >> B >> C >> N;
    vector<vector<int>> ok, ng;
    for (int i = 0; i < N; ++i) {
        int a, b, c, isok;
        cin >> a >> b >> c >> isok;
        --a, --b, --c;
        if (isok) ok.push_back(vector<int>({a, b, c}));
        else ng.push_back(vector<int>({a, b, c}));
    }
    
    // デフォルトでは「分からない」としておく
    vector<int> res(A + B + C, 2);
    
    // 検査結果「合格」の情報から、確実に OK な部分を先に埋める
    for (auto v : ok) {
        int a = v[0], b = v[1], c = v[2];
        res[a] = res[b] = res[c] = 1;
    }
    
    // 検査結果「不合格」の情報から、確実に NG な部分を埋めていく (3 つ中 2 つが OK)
    for (auto v : ng) {
        int a = v[0], b = v[1], c = v[2];
        if (res[b] == 1 && res[c] == 1) res[a] = 0;
        else if (res[c] == 1 && res[a] == 1) res[b] = 0;
        else if (res[a] == 1 && res[b] == 1) res[c] = 0;
    }
    
    // 出力
    for (auto v : res) cout << v << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 予選 2007 E - 品質検査 (AOJ 0514, 難易度 5)

問題概要

制約

Step 1：合格製品から考える

Step 2：不合格製品を考える

コード