問題

提出解答

a key, Shift key, CapsLock key からなるキーボード, ランプ, 画面がある. 最初, ランプは off であり, 画面には空文字列が表示されている.

以下の $3$ 種類の操作のうち, $1$ つを選んで実行するということを $0$ 回以上何度でも行うことができる.

ミリ秒かけて, a key のみ押す. このとき, ランプの on/off によって, 次のように分岐する.
- ランプが off ならば, 画面の文字列の末尾に ${\tt a}$ が付け足される.
- ランプが on ならば, 画面の文字列の末尾に ${\tt A}$ が付け足される.
ミリ秒かけて, Shift key, a key を同時に押す. このとき, ランプの on/off によって, 次のように分岐する.
- ランプが off ならば, 画面の文字列の末尾に ${\tt A}$ が付け足される.
- ランプが on ならば, 画面の文字列の末尾に ${\tt a}$ が付け足される.
$Z$ ミリ秒かけて, CapsLock key を押す. CapsLock key のランプの off/on が切り替わる.

${\tt A}, {\tt a}$ からなる文字列 $S$ が与えられる. 画面の文字列を $S$ に一致させるのに必要な最短の時間は何ミリ秒か?

まず, 次のことに注意する.

よって, 調べるべき入力の方法は順に

に限られる.

このことから, ランプの off/on を状態に持った動的計画法で考えれば良いことがわかる.

次のような動的計画法を考える. ただし, $0 \leq i \leq N, x \in \{{\rm off}, {\rm on}\}$ とする.

ベースケースは $i=0$ のときで,

${\rm DP}[0,x ]=\begin{cases} 0 & (x = {\rm off}) \\ \infty & (x = {\rm on}) \end{cases}$

である.

遷移式について, $S_i={\tt a}$ ならば, ランプの動きで場合分けすることにより,

${\rm DP}[i, {\rm off}]=\min ({\rm DP}[i-1, {\rm off}], {\rm DP}[i-1, {\rm on}]+Z)+X$
${\rm DP}[i, {\rm on}]=\min ({\rm DP}[i-1, {\rm off}]+Z, {\rm DP}[i-1, {\rm off}])+Y$

となる.

また, $S_i={\tt A}$ の場合も同様にして, ランプの動きで場合分けすることにより,

${\rm DP}[i, {\rm off}]=\min ({\rm DP}[i-1, {\rm off}], {\rm DP}[i-1, {\rm on}]+Z)+Y$
${\rm DP}[i, {\rm on}]=\min ({\rm DP}[i-1, {\rm off}]+Z, {\rm DP}[i-1, {\rm off}])+X$