No.943 取り調べ

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.943 取り調べ

レベル : / 実行時間制限 : 1ケース 1.206秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 129
作問者 :

face4 / テスター :

ganariya

11 ProblemId : 3625 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-01-02 21:00:23

注意

Python使いの方はPyPyで提出することをお勧めします。
(Python素人のwriterが書いたコードでは最悪ケースで Python 4630ms, PyPy 240ms)

問題文

あなたは冷酷無比なベテラン刑事です。
集団詐欺グループのアジトをついに突き止めたあなたは、アジトへの突入作戦を実行し、
見事詐欺グループの全メンバー $N$ 人を捕まえることに成功しました。

捕らえられたメンバーは1人1部屋ずつ、合計 $N$ 部屋の取調室に収容されています。あなたの目標は、
全メンバーを自白させることです。

事前に行われた捜査から、詐欺グループの各メンバーはそれぞれ頼りにしているメンバーが何人か(0人以上)いる
ことがわかっています。頼りにしているメンバーが全員自白したと知った(もしくは最初から誰も頼りにしていなかった)
とき、そのメンバーは心の拠り所を失い、自分の犯した過ちを全て自白することでしょう。

前述の通り、各メンバーは1人ずつ別々の取調室に入れられています。つまり、他のメンバーが自白したかどうか
はあなたを通してしか知ることが出来ません。これは何を意味するでしょうか？

あなたはメンバーに対して嘘をつくことが出来ます。具体的には、メンバー $i$ がまだ自白していないにも関わらず、
$i$ 以外のメンバー $j$ に「 $i$ は自分のやったことを洗いざらい話して楽になったぞ、お前も楽になったらどうだ」
とハッタリをかけることが出来ます。いくら冷酷無比なあなたでも、 $i$ が自白したという嘘をつくことには $i$ に対して
若干の申し訳なさを感じてしまいます。しかし、慣れというのは恐ろしいもので、一度 $i$ が自白したという嘘をついて
しまえば、あとは何回同じ嘘をついても申し訳なさを全く感じません(冷酷無比なので)。

詐欺グループの各メンバーが頼りにしているメンバーのリスト $X$ 、及びあなたが「メンバー $i$ が自白した」という
嘘を初めてついたときに感じてしまう申し訳なさ $A_{i}$ が与えられます。全メンバーを自白させるために感じざる
を得ない申し訳なさの総和の最小値を求めてください。

「メンバーが自白した」という*事実*を伝える行為に対しては申し訳なさを感じないことに注意してください
(わからなければサンプルの説明を見てください)。

入力

 $N$ 
 $X_{11}$   $X_{12}$   $\dots$   $X_{1 N}$ 
 $X_{21}$   $X_{22}$   $\dots$   $X_{2 N}$ 
 $⋮$ 
 $X_{N 1}$   $X_{N 2}$   $\dots$   $X_{N N}$ 
 $A_{1}$   $A_{2}$   $\dots$   $A_{N}$

入力は全て整数で与えられる。

$1 \leq N \leq 18$
$X_{i j} = 0, 1$ (1ならばメンバー $i$ はメンバー $j$ を頼りにしている、0ならば頼りにしていない)
$X_{i i} = 0$ $(1 \leq i \leq N)$
$0 \leq A_{i} \leq 10^{5}$

出力

全メンバーを自白させるために感じざるを得ない申し訳なさの総和の最小値を出力してください。最後に改行してください。

サンプル

サンプル1

入力

出力

メンバーを順に $A, B, C$ とします。最適な戦略の一例を以下に示します。

まず、 $B$ に $A$ が自白したと伝えます。これは嘘なので、あなたは申し訳なさを5感じます。 $B$ が自白します。
次に、 $C$ に $A$ が自白したと伝えます。これは嘘ですが、この嘘は既に1回ついているので、ここでは
申し訳なさを感じません。 $C$ が自白します。
最後に、 $A$ に $B$ と $C$ が自白したと伝えます。これは事実なので、申し訳なさを感じません。 $A$ が自白します。

申し訳なさ5で全メンバーを自白させることができました。申し訳なさ5未満で全メンバーを自白
させることはできないので、5を出力します。

サンプル2

入力

出力

メンバーを順に $A, B, C$ とします。最適な戦略の一例を以下に示します。

まず、 $A$ に $B, C$ が自白したと伝えます。これはどちらも嘘なので、申し訳なさを $1 + 1 = 2$ 感じます。 $A$ が自白します。
次に、 $B$ と $C$ に $A$ が自白したと伝えます。これは事実なので、申し訳なさを感じません。 $B$ と $C$ が自白します。

申し訳なさ2で全メンバーを自白させることができました。申し訳なさ2未満で全メンバーを自白
させることはできないので、2を出力します。

サンプル3

入力

出力

メンバーを順に $A, B, C$ とします。最適な戦略の一例を以下に示します。

まず、 $C$ に $A, B$ が自白したと伝えます。これはどちらも嘘なので、申し訳なさを $1 + 2 = 3$ 感じます。 $C$ が自白します。
次に、 $B$ に $A, C$ が自白したと伝えます。 $C$ が自白したことは事実なので、申し訳なさを感じません。
$A$ が自白したというのは嘘ですが、この嘘はすでに1回ついているので、ここでも申し訳なさを感じることはありません。
$B$ が自白します。
$A$ に $B, C$ が自白したと伝えます。これはどちらも事実なので、申し訳なさを感じることはありません。 $A$ が自白します。

申し訳なさ3で全メンバーを自白させることができました。申し訳なさ3未満で全メンバーを自白
させることはできないので、3を出力します。

サンプル4

入力

4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
10 10 10 10

出力

全員が誰も頼りにしていないので、最初から全員が自白します。申し訳なさは0で済みます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

No.943 取り調べ

注意

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力

サンプル4

入力

出力