GCJ2012 Round 1A Problem A. 問題紹介

Google Code Jam 2012 Round 1A
Problem A. Password Problem 問題紹介

長いパスワードを途中まで入力したけれど、ミスタイプしたかもしれない。正しくパスワードを入力完了するまでにあと何回キーをタイプすればよいか、最短の期待値を求める、、という問題です。

パスワードの入力を終えたら [enter] キーを押して判定します。間違っていたら(ミスタイプがあれば)入力したパスワードが全て消えて最初から入力し直しになります。これから入力するパスワードはミスタイプしません。慎重になるんですね（棒

次の3通りのどれかを行います。

• このままパスワードの入力を続ける（入力を終えたら [enter] キーで判定し、間違いがあれば全て消えて再入力）
• [backspace] キーを数回押して入力済みパスワード(の一部)を消して入力し直す（入力を終えて [enter] キーを押したときに間違いがあれば再入力になるのは１つめと同じ）
• 一旦 [enter] キーを押してパスワードをクリアして最初から入力し直す

例:
パスワードは “guest” で、既に2文字入力しているとします。1文字目も2文字目も40%の確率で間違えている可能性があります。このとき、

• ミスせず “gu” と入力できている可能性は 0.6×0.6=0.36（36%）です。
• 最初の “g” は正しく入力できたけれど、2文字目の “u” をミスした可能性は 0.6×0.4=0.24（24%）です。これを “gX” と表現します。
• 2文字目の “u” は正しく入力したけれど1文字目をミスタイプしていた可能性は 0.4×0.6=0.24（24%）です。“Xu”  と表現します。
• 1文字目も2文字目もミスタイプしていた（“XX”）可能性は 0.4×0.4=0.16（16%）です。

正しいパスワードを入力完了するまでにあと何回キー入力が必要かを表にするとこうなります。

	“gu”	“gX”	“Xu”	“XX”	期待値
確率	36%(0.36)	24%(0.24)	24%(0.24)	16%(0.16)	-
このまま入力を続ける	4回	10回	10回	10回	7.84回
[backscape] で1文字消して入力し直す	6回	6回	12回	12回	8.4回
[backscape] で2文字消して入力し直す	8回	8回	8回	8回	8回
[enter] して最初から入力し直す	7回	7回	7回	7回	7回

このまま入力を続ける場合、36%の確率で、あと4回のキー入力（“est”+[enter]）で正しいパスワードを入力完了できます。残りの64%では [enter] してもパスワードが間違っているので最初から入力し直しとなります。“guest”+[enter] の6回余分にキー入力が必要で、全部で10回のキー入力を必要とします。
このとき期待値は、4×0.36 + 10×(0.24+0.24+0.16) = 7.84回 となります。

[backspace] で1文字消して入力し直す場合、“gu” と “gX” はそのまま正しいパスワードを入力することができます。[backspace]+“uest”+[enter] で6回のキー入力です。“Xu” と “XX” の場合はもう一度最初から入力し直す必要があるので、 [backspace]+“uest”+[enter]+“guest”+[enter] の12回のキー入力が必要です。

[backspace] で2文字消して入力し直す場合、どのパターンでも、 [backspace]+[backspace]+“guest”+[enter] の8回のキー入力です。


[enter] して最初から入力し直す場合は [enter]+“guest”+[enter] の7回のキー入力で正しいパスワードを入力完了でき、今回のケースの期待値ではこれが最小となります。

入力データ:

最初の行は問題数 T。以降 T問の問題データが続きます（各2行）。

問題の1行目には入力済みパスワード長 A とパスワード全体の長さ B がスペース区切りで記述されています。
問題の2行目はパスワードを正しく（ミスせず）入力した確率 pi がA個の並んでいます。

データ制限:

• 1 ≤ T ≤ 20 （問題数は20問）
• Small input の場合：1 ≤ A ≤ 3、A < B ≤ 100 （最長100文字のパスワードを1〜3文字入力済み）
  Large input の場合：1 ≤ A ≤ 99999、A < B ≤ 100000 （最長100000文字のパスワードを1〜99999文字入力済み）
• 0 ≤ pi ≤ 1  （正しく入力した確率は 0〜1 の間の全ての値。小数を含む）

解き方はこちら。