ABC303D "Shift vs. CapsLock" この問題の正解者は実は間違っていない
この記事について
こちらの記事へのエアリプです。ちなみに筆者はグリーンランクです。(血涙)
遷移の仕方
dp[i][j]を「CapsLockがONであればi=1, OFFであればi=0であり、j文字目まで入力した時点での最短時間」とする。
実は、遷移は以下のようになっています。
前計算3種類
CapsLockを偶数回使い、現在と同じ側の文字を打つ
これは「Aキーを押す」と「CapsLockを切り替えてからshift+Aを押し、もう一度CapsLockを切り替える」です。元記事で言う所のBです。
# CapsLockが偶数回、大文字小文字がこちら側の意味
EVEN_THIS_SIDE = [x,z+y+z].min
CapsLockを偶数回使い、現在と反対側の文字を打つ
これは「shift+Aを押す」と「CapsLockを切り替えてからAを押し、もう一度CapsLockを切り替える」です。元記事で言う所のAです。
# CapsLockが偶数回、大文字小文字があちら側の意味
EVEN_OTHER_SIDE = [y,z+x+z].min
CapsLockを1回使い、文字は大文字小文字どちらでも良い
個人的には大文字と小文字は区別した方がDPを書きやすいのですが、元記事が共通としているので共通化します。
これは「Aキーを押してからCapsLockを切り替える」「CapsLockを切り替えてからshift+Aを押す」で遷移前のCapsLockと同じ側(遷移後の反対側)の文字を打てます。「CapsLockを切り替えてからAを押す」「shift+Aを押してからCapsLockを切り替える」で遷移前のCapsLockと反対側(遷移後と同じ側)の文字を打てます。元記事のCです
# CapsLockが奇数回、大文字小文字がどちらでも良いの意味
ODD_ANY_SIDE = [x + z, y + z].min
遷移式
# s[j+1] == 'A'のとき、
dp[0][j+1] = [dp[0][j] + EVEN_OTHER_SIDE, dp[1][j] + ODD_ANY_SIDE].min
dp[1][j+1] = [dp[1][j] + EVEN_THIS_SIDE, dp[0][j] + ODD_ANY_SIDE].min
# s[j+1] == 'a'のとき、
dp[0][j+1] = [dp[0][j] + EVEN_THIS_SIDE, dp[1][j] + ODD_ANY_SIDE].min
dp[1][j+1] = [dp[1][j] + EVEN_OTHER_SIDE, dp[0][j] + ODD_ANY_SIDE].min
dp[1][0]は仮にzとしておいてもいいでしょうが、どうせ元記事にある通りdp[0][0]からの遷移で塗りつぶされるので最小値を取る必要はなく一意に決まります。
ACコード
なぜ元記事のコードが通らなかったのか
s[j+1] == 'A'のとき、
dp[0][j+1] = min(dp[0][j] + B, dp[1][j] + C)
dp[1][j+1] = min(dp[1][j] + A, dp[1][j] + C)
ここの3行目、dp[1][j+1]への遷移なのにdp[1][j]から奇数回CapsLockを押してしまっています。奇数回CapsLockを使うならdp[0][j]から遷移しなくてはいけません。
s[j+1] == 'a'のとき、
dp[0][j+1] = min(dp[0][j] + A, dp[1][j] + C)
dp[1][j+1] = min(dp[1][j] + B, dp[1][j] + C)
ここもです。「C」としているので一見CapsLockが奇数なのがわかりにくいですね。「ODD」と変数(定数)名に入っていれば1と0の書き間違いに気づけたかもしれません。
別のとらえ方
CapsLockを押すだけの遷移を考えることで別の更新式を作ることができます。
s[j+1] == 'a'のときだけを例にとると、
dp[0][j+1] = [dp[0][j] + x, dp[1][j] + z + x].min # 元記事はここがdp[1][j] + z + yになってしまっている
dp[1][j+1] = [dp[0][j] + z + y, dp[1][j] + y].min # ここもdp[1][j] + xではaではなくAが出力されてしまう。
# とした後に、
dp[0][j+1] = [dp[0][j+1], dp[1][j+1] + z].min
dp[1][j+1] = [dp[1][j+1], dp[0][j+1] + z].min
ACコード
最後に
CapsLockを押すだけの遷移を考えることの長所は、１つ目の解法と違い「CapsLock切り替え→a打鍵→CapsLock切り替え」→「CapsLock切り替え→a打鍵→CapsLock切り替え」みたいなCapsLock二連打を計算しなくていいことなので、わざわざ１つ目の解法と同じことをしなくてもこれでいいような……
dp[0][j+1] = dp[0][j] + x
dp[1][j+1] = dp[1][j] + y
# とした後に、
dp[0][j+1] = [dp[0][j+1], dp[1][j+1] + z].min
dp[1][j+1] = [dp[1][j+1], dp[0][j+1] + z].min
ACコード
Discussion