量子人狼を定式化した（速いアルゴリズム募集中）

量子人狼は、CISRA Puzzle Competition 2008 で考案されたとされているゲームです。詳しいルールは次の記事を参照してください。

uhyo.hatenablog.com

また、筆者によるサービス月下人狼ではこの量子人狼を実装しており、確率表の高速な計算が必要です。現在月下人狼に存在する問題として、実装されているアルゴリズムがナイーブなものでありスケールしないという点があります。筆者のアルゴリズム力はとても弱いので、皆さんの力を借りるべく量子人狼の問題を定式化してみました。ぜひチャレンジして速そうなアルゴリズムを作ってみてください。

問題

人狼村には $1$ さん、 $2$ さん、 $\dots$ 、 $N$ さんという $N$ 人の村人が住んでいます。それぞれの村人は「ただの村人」、「人狼」、「占い師」のいずれの役職を持ちます。 $N$ 人の村人のうち人狼は $W$ 人であり、占い師は $D$ 人です。また、人狼たちには序列が存在し、序列の高いほうから「人狼 $1$ 」、「人狼 $2$ 」、 $\dots$ 、「人狼 $W$ 」です。高橋君は村の村長であり、村人たちの行動からそれぞれの村人が人狼や占い師である確率を求めて人狼を処刑したいです。

各村人には役職の他に、「生存」または「死亡」のいずれかの状態が割り当てられます。村の状態とは、各村人に対する役職および生死の割り当てです。村の状態においては、役職「人狼 $1$ 」 $\dots$ 「人狼 $W$ 」を割り当てられた村人はそれぞれ1人ずつで、役職「占い師」を割り当てられた村人はちょうど $D$ 人でなければいけません。（例えば、 $N=3, W=1, D=1$ の村では $\{1 \mapsto (人狼1, 生存), 2 \mapsto (村人, 死亡), 3 \mapsto (占い師, 生存) \}$ は村の状態です。）

また、それぞれの村の状態に対してドミナント人狼が定まることがあります。役職「人狼 $i$ 」を割り当てられた（唯一の）村人の生死が「生存」であるような $i$ のうち最小のものを $i_m$ とするとき、その村の状態におけるドミナント人狼は役職「人狼 $i_m$ 」を指します。そのような $i_m$ が存在しない場合はドミナント人狼はありません。

村の状態集合は、村の状態の集合です。初期状態では、これは村人たちへの役職の割り当て全通りの集合です。生死については、いずれの村の状態でも全ての村人に「生存」が割り当てられています。（例えば、 $N=3, W=1, D=1$ の村では村の状態集合の初期状態は $\{1 \mapsto (人狼1, 生存), 2 \mapsto (村人, 生存), 3 \mapsto (占い師, 生存) \}$ や $\{1 \mapsto (人狼1, 生存), 2 \mapsto (占い師, 生存), 3 \mapsto (村人, 生存) \}$ などからなる6要素の集合です。）

村人たちは以下のいずれかの行動を合計 $M$ 回行います。各行動の結果として村の状態集合が変更されます。

村人 $p$ を処刑して役職 $r$ に収束する行動。まず、村の状態集合から、村人 $p$ が死亡しているものと村人 $p$ の役職が $r$ でないものを全て取り除く。次に、残った全ての村の状態において村人 $p$ の生死を「死亡」に変更する。
村人が村人を占って結果を得る行動。結果は「白」または「黒」である。
- が「白」の場合、村の状態集合から以下の条件を満たすものを取り除く：
  - 村人 $p$ の役職が「占い師」かつ生死が「生存」であり、村人 $q$ の役職が「人狼」である。
- が「黒」の場合は、村の状態集合から以下の条件を満たすものを取り除く：
  - 村人 $p$ の役職が「占い師」かつ生死が「生存」であり、村人 $q$ の役職が「人狼」ではない。
村人が村人を襲撃する行動。以下の操作を順に行う。
- 村人 $p$ の役職がドミナント人狼かつ村人 $q$ の役職が人狼のいずれかであるような村の状態を取り除く。
- 村人 $p$ の役職がドミナント人狼である村の状態全てにおいて、村人 $q$ の生死を「死亡」に変更する。

$M$ 回の行動が全て終わった後の村の状態集合に対して、全ての $i$ に対して次の値を求めてください。

村の状態集合の要素のうち、村人 $i$ の役職が「ただの村人」であるものの割合。
村の状態集合の要素のうち、村人 $i$ の役職がいずれかの「人狼」であるものの割合。
村の状態集合の要素のうち、村人 $i$ の役職がいずれかの「占い師」であるものの割合。
村の状態集合の要素のうち、村人 $i$ の生死が「死亡」であるものの割合。

注釈

問題文はフィクションであり、実在の人物、とりわけ株式会社人狼およびVR 人狼渋谷を経営する高橋一成さんとは関係ありません。
実際の量子人狼のルールを一部簡略化しています（処刑以外の要因による収束など）。

制約

$1 \leq N \leq 100$
$0 \leq W, D$
$0 \leq W+ D \leq N$
$0 \leq M \leq 10^4$

入力

入力は以下の形式でどこかから与えられます。

$N\ W\ D\ M$

$t_1\ a_1\ b_1\ c_1$

$\vdots$

$t_M\ a_M\ b_M\ c_M$

ただし $t_i$ は $i$ 回目の行動の種類を表す文字でL（処刑）、S（占い）、A（襲撃）のいずれかです。

Lの場合、村人 $a_i$ を処刑して役職 $b_i$ に収束する行動を表します。 $b_i$ は役職を表す整数であり、 $0$ はただの村人、 $-1$ は占い師、 $w (> 0)$ は人狼 $w$ を表します。 $c_i$ は整数が与えられますが意味はありません。
Sの場合、村人 $a_i$ が村人 $b_i$ を占って結果 $c_i$ を得る行動を表します。 $c_i$ は $0$ または $1$ であり、 $0$ のとき白、 $1$ のとき黒を表します。
Aの場合、村人 $a_i$ が村人 $b_i$ を襲撃する行動を表します。 $c_i$ は整数が与えられますが意味はありません。

出力

全ての操作の終了後、村の状態集合の要素数が $0$ である場合は-1とだけ出力してください。

そうでない場合、以下の形で出力してください。

$p_1\ q_1\ r_1\ d_1$

$\vdots$

$p_N\ q_N\ r_N\ d_N$

ただし、 $p_i$ は村人 $i$ が「ただの村人」である割合、 $q_i$ は村人 $i$ が「人狼」である割合、 $r_i$ は村人 $i$ が「占い師」である割合、 $d_i$ は村人 $i$ の生死が「死亡」である割合です。

割合は0以上1以下の数値で出力してください。誤差は絶対値 $0.00005$ まで許容されます。

入力例1

5 1 1 2
S 1 2 1
L 2 0 0

出力例1

0.6667 0.3333 0.0000 0.0000
1.0000 0.0000 0.0000 1.0000
0.4444 0.2222 0.3333 0.0000
0.4444 0.2222 0.3333 0.0000
0.4444 0.2222 0.3333 0.0000

$N=5, W=1, D=1$ の村です。まず、村人 $1$ が村人 $2$ を占って結果「黒」を得ます。その後、村人 $2$ を処刑して役職「ただの村人」に収束します。これにより、村人 $2$ は「ただの村人」である割合が1、他の役職である割合は0となります。また、死亡している割合も1となります。村人 $1$ は「占い師」である割合が0であり、他の3人の村人で均等に分けあっています。

入力例2

出力例2

0.4286 0.2857 0.2857 0.7143
0.4286 0.5000 0.0714 0.0000
0.3810 0.4048 0.2143 0.0000
0.3810 0.4048 0.2143 0.0000
0.3810 0.4048 0.2143 0.0000

村人 $1$ は他の村人たちから集中的に襲撃されたことで死亡の割合が上がっています。村人 $2$ は占いを行ったことで「占い師」の割合が減少しています。

入力例3

出力例3

-1

入力例4

出力例4

0.6744 0.3256 0.0000 0.0000
0.5930 0.2733 0.1337 0.2384
1.0000 0.0000 0.0000 1.0000
0.5640 0.2616 0.1744 0.1628
0.6570 0.2267 0.1163 0.0000
0.6279 0.2384 0.1337 0.1453
0.5407 0.2849 0.1744 0.0988
0.6512 0.2326 0.1163 0.3314
0.6919 0.1570 0.1512 0.1221

うひょー（ブログ）

うひょー