第6回日本情報オリンピック 予選

2006年12月22日
情報オリンピック日本委員会

問題
   品質検査

解説

ある三つの部品をつないで検査して, 「合格」の結果が出ていれば, その三つの部品はすべて正常だとわかる. 言い換えれば, 「合格」の結果が出た検査で一度でも使われていた部品はすべて正常であるとわかる. 逆に, 正常であるとわかる部品はこれらの部品だけである. というのは, 「合格」の結果が出た検査で一度も使われなかった部品は, すべて故障しているとしても検査結果と矛盾しないからである.

故障しているとわかる部品はどのような部品だろうか? 正常とわかる部品二つと正常かどうかが不明な部品一つをつないで検査して, 「不合格」の結果が出れば, 不明だった部品は故障しているとわかる. 逆に, 部品 x を正常とわかる部品二つとつないで検査したことがなければ, x が正常であるとしても検査結果と矛盾しない (例えば, 正常とわかる部品と x だけが正常で, 他の部品がすべて故障しているという場合を考えればよい). よって, そのような部品 x は故障しているとも正常であるとも決まらない.

まとめると, すべての部品を故障しているとわかるもの, 正常だとわかるもの, どちらとも決まらないものの 3 種類に分類するには, 次のようにすればよい.

  1. まず, 各部品について「故障」「正常」「不明」のいずれかを記録しておくための場所を用意する. 最初はすべて「不明」に初期化しておく.
  2. 次に, 検査結果のうち「合格」を表す行について, 検査に使われた三つの部品を「正常」とマークする.
  3. 最後に, 検査結果のうち「不合格」を表す行について, 検査に使われた三つの部品のうち二つが「正常」であれば, 残りの一つを「故障」とマークする (そうでないときは無視する).

他の解法として, すべての部品の「故障」「正常」の組合せ 2a+b+c 通りについて, 検査結果と矛盾しないかどうかを調べるという方法がある. この方法は, 部品の個数 a+b+c が大きくなると, 調べる組合せの個数が急激に増えるため, a+b+c が小さい場合しか現実的に使えない. この方法では入力 1 のみが解ける.

このほか, 上で述べた効率の良い解法と効率の悪い解法の中間にあたるような解法も考えられるが, そのような解法には相応に部分点が与えられることを意図して入力を決めた.