No.562 超高速一人かるた small
タグ : / 解いたユーザー数 47
作問者 :


超高速一人かるた largeの制約小さい版です。
small に large 用の解法を提出することは特に制限しませんが、 large をコンテスト中に解くつもりのある方は、他の方の提出を覗かないようお願いします。
問題文
かるた取りとは
- 読み札
には文字列 が書かれています。 - 読み札
には対応する取り札 が一つだけ存在します。
異なる読み札が同じ取り札に対応することはありません(つまり一対一対応)。
ゲームは次のように進行します。
- 読手は
枚の読み札を持ち、競技者は 枚の取り札を場に並べます - 読手はまだ読んでいない読み札
枚を等確率で選び、書かれている文字列を読み上げます。 - 文字列が読み上げられ始めたら、競技者は今読まれている読み札
を推定し、 場から対応する取り札 を探して取ります - 読まれていない読み札がまだ残っているなら 2. へ戻ります。 そうでないならゲームは終了です
太郎くんはかるたが得意なので、読み上げられている読み札が一意に定まった瞬間に取り札を取ることができます。
一意に定まらないうちに札を取ることはありません。
しかし大変集中力を要するため、取るまでに読み上げられた文字列長分の疲労度が蓄積されます。
つまり、
ただし、読み上げられ方のパターン数
入力
1行目に読み札・取り札の枚数
制約
出力
サンプル
サンプル1
入力
3 umr uma tsf
出力
7 24 30
3枚中1枚読まれるとき、それぞれ次の強調部が読まれたときに一意に定まります
- umr 疲労度+3
- uma 疲労度+3
- tsf 疲労度+1
それぞれ 1/3 の確率なので、 (3+3+1)/3 * 3 = 7
3枚中2枚読まれるとき、
[1枚目が"umr" 疲労度+3]
- uma 疲労度+1
- tsf 疲労度+1
[1枚目が"uma" 疲労度+3]
- umr 疲労度+1
- tsf 疲労度+1
[1枚目が"tsf" 疲労度+1]
- umr 疲労度+3
- uma 疲労度+3
(4+4+4+4+4+4)/6 * 6 = 24
3枚中3枚読まれるとき、2枚のときに加えて残った1枚を取るときに 疲労度+1
(5+5+5+5+5+5)/6 * 6 = 30
サンプル2
入力
2 a aa
出力
4 6
"a" だけでは一意に定まりません。 2文字目に"a"が読み上げられるか、 何も読み上げられないかを確認する必要があります。
- a.
- aa
サンプル3
入力
12 a b c d e f g h i j k l
出力
12 264 3960 47520 475200 3991680 27941760 159667200 718502400 395007986 269017565 748019165
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。