GCJ2012 Round 1A Problem A. 解き方

Google Code Jam 2012 Round 1A
Problem A. Password Problem 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

問題の表を素直にコードにすれば Small はクリアできるかもしれません。
でもそれでは Large の10万桁パスワードで時間がかかってしまいます。

問題文ではわかりやすいようにわざわざ “Xu” と “XX” が分けて書かれていますが、この2つは「正しいパスワードを入力するまでの残りキー入力回数」という観点では同じものです。
n文字目でミスタイプした（n-1文字目までは正しく入力できている）場合、n+1文字目以降を正しく入力できていてもミスタイプしていても、次のどちらかとなります。

• [backspace] でn文字目まで削除した ⇒ 再入力で正しいパスワードが完成する
• [backspace] でn文字目までは削除しなかった ⇒ ミスタイプが残ったままなので一度失敗して最初から再入力になる

これに気付くと1回のループで [backspace] 入力回数別のキー入力回数期待値をリストすることができます。

[backspace] を A-1回（Aは入力済みパスワード長）押したときのことを考えてみます。
入力済みパスワードは最初の1文字以外は全部削除しています。この残った1文字が正しく入力できている確率は p1 で、間違えている確率は 1-p1 です。
2文字目以降を正しく入力できているか・ミスタイプしているかは関係ないので、このときのキー入力回数の期待値は

([enter] するまでのキー入力回数)×p1

+

([enter] するまでのキー入力回数 + 全て入力し直すキー入力回数)×(1-p1)

となります。

ちなみに [enter] するまでのキー入力回数 は

[backspace] の入力回数 + 残りパスワード入力文字数 + [enter] 1回

全て入力し直すキー入力回数 は

全パスワード長 + [enter] 1回

です。

次に最初の2文字を残す場合を考えてみます。（[backspace] を A-2回押すケース）

この2文字がどちらも正しく入力できている確率は p1×p2 です。

この2文字までにミスタイプがある確率は 1-(p1×p2) です。

先ほどと同様にキー入力回数の期待値を求めることができます。

[backspace] を1度も押さずにこのまま入力を続ける場合も同じ式でキー入力回数の期待値が求められます。（全て正しく入力できている確率は p1×p2×...×pA）
[backspace] を A回押して入力済みパスワードを全て消した場合も、正しく入力できている確率を 1 と見れば同じ式が成り立ちます。

[enter] して最初から入力し直す場合は入力済みパスワードの正解率は無関係で、[enter] 1回 + 全パスワード長 + [enter] 1回 でキー入力回数（の期待値）が求められます。

こうして算出した期待値の最小が答えとなります。