Google Code Jam 2012 Round1A 問題A

問題

あるB文字からなるパスワードをA文字目まで入力した状態でいる。
これまで入力した文字の正しさの確率がそれぞれ与えられる。
次の動作として、「そのまま入力しきる」「BackSpaceを何回かして打ち直す」「Enterで一度入力して、その場合最初から入力しなおす」ができる。
次の動作からの入力は必ず正しい入力ができているとする。

それぞれの動作で一番キーボードの入力回数の期待値が少なくなるものは何回か答える。

考え方

「Enterで一度入力して入力しなおす」場合は、必ず同じ入力数になる。
他の2つの動作は、これまでの入力ですべて正しい場合と間違いがあった場合で2つに分けられる。
BSを0回、1回、2回、、、の場合で上の確率とその時のキー入力回数は計算できるので、それで計算して最小値を返せばよい。