Shift vs. CapsLock Rust - 問題リンク
この記事では、AtCoderの「Shift vs. CapsLock」という問題の解説を行います。問題文と制約は問題リンクから確認して下さい。
コード例はRustで示しますが、別言語を使用している方でも理解できると思います。
Shift vs. CapsLock — 考察
問題文を見た途端、これはDPで解けるなと思いました。3種類の操作をどのようにとると最短で文字列$S$を作れるかという最適化問題のようです。ナップサック問題と同じようなタイプの問題ですね。
"0回以上何度でも"操作を行えるというところについて考えてみます。各操作を1つの遷移とすると、文字を追加せずに状態だけ変える操作があるので少し混乱してしまいます。
そこで、「$S$の$i$文字目を得るのに必要な操作(操作列)」を1つの遷移だとみなして、$|S|$まで状態遷移させると良いです。
説明のため、各操作をそれぞれ$x,y,z$とおくことにします。それぞれ、操作$x$は$X$ミリ秒、操作$y$は$Y$ミリ秒、操作$z$は$Z$ミリ秒かかります。
$S$のi番目の文字を得るための操作について考えます。i文字目を得るために使用できる操作列は無限にありますが、考慮するべき操作列のパターンは絞ることができます。例えば、ある状態から操作xを行うことで得られる文字と操作列(z→z→x)を行うことで得られる文字は同じですが、後者は余計な時間をかけているだけなので考慮する必要がありません。
実際は、ある状態から文字'a'を得る場合の遷移は以下の4パターンだけ考慮すれば良さそうです。
| 状態 | 操作列 | 意味 |
|---|---|---|
| CapsLock=Off | x | CapsLockがOffの時に、'a'を押す |
| CapsLock=On | y | CapsLockがOnの時に、'a'とShiftキーを押す |
| CapsLock=On | z → x | CapsLockがOnの時に、CapsLockキーを押してから、'a'を押す |
| CapsLock=Off | z → y | CapsLockがOffの時に、CapsLockキーを押してから、'a'とShiftキーを押す |
文字'A'が欲しい場合についても同様に考えられます。上記表の状態(CapsLockのOn/Off)が反転するだけです。
上記の4パターンの遷移を行うようなDPを行います。実装はシンプルなので、コードを見てもらうのがわかりやすいと思います。
Shift vs. CapsLock — Rust解法
上記の考察結果をRustコードにすると以下のようになります。入出力など本質的でない部分は省いてあります。
use std::cmp::min;
fn solve(x: i64, y: i64, z: i64, s: &Vec<char>) -> i64 {
let n = s.len();
let mut dp = vec![vec![i64::MAX / 2; 2]; n + 1];
dp[0][0] = 0;
for i in 1..=n {
if s[i - 1] == 'a' {
dp[i][0] = min(dp[i][0], dp[i - 1][0] + x);
dp[i][1] = min(dp[i][1], dp[i - 1][1] + y);
dp[i][1] = min(dp[i][1], dp[i - 1][0] + y + z);
dp[i][0] = min(dp[i][0], dp[i - 1][1] + x + z);
} else {
dp[i][1] = min(dp[i][1], dp[i - 1][1] + x);
dp[i][0] = min(dp[i][0], dp[i - 1][0] + y);
dp[i][0] = min(dp[i][0], dp[i - 1][1] + y + z);
dp[i][1] = min(dp[i][1], dp[i - 1][0] + x + z);
}
}
return min(dp[n][0], dp[n][1]);
}
最後にCapsLockはOn/Offどちらでも良いので、両方の最小値をとることに注意です。
Discussion