AtCoder が提供しているABC（AtCoder Beginner Contest）303 のD問題をC++とPythonで解いてみました。ABC303は、2023年5月27日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Shift vs. CapsLock（Difficulty : 778）
問題はリンク先をご覧ください。
DP（動的計画法）で解くことができました。AtCoder Problems による Difficulty は 778 でした。
解答案
CapsLock が OFF の時に、’A’ を出すには、Shift ＋ a とするか、CapsLock を押してから a を押す2通りがあります。’a’ の場合も同様で、それぞれの文字出力について、2通りの選択肢があります。DP（動的計画法）の出番です。
dp[i][j] を i 文字目を入力した後の最短時間とします。j = 0 の場合は、CapsLock キーのランプが OFF の場合、j = 1 の場合は、CapsLock キーのランプが ON の場合とします。
なお、CapsLockは常に先に押すことにします。これは、CapsLockを2回押すことは明らかに無駄となります。このため、後にCapsLockを押す場合を追加しても最短時間が変わらなくなります。
漸化式を考えます。
A を入力する場合の漸化式は以下となります。
- dp[i + 1][0] = min (dp[i][0] + Y, dp[i][1] + Z + Y)
ランプがOFFの場合 Shift＋a、ONの場合 CapsLock の後に Shift＋a - dp[i + 1][1] = min (dp[i][0] + Z + X, dp[i][1] + X)
ランプがOFFの場合 CapsLock の後にa、ON の場合 a
a を入力する場合の漸化式は以下となります。
- dp[i + 1][0] = min (dp[i][0] + X, dp[i][1] + Z + X)
ランプがOFFの場合 a、ONの場合 CapsLock の後に a - dp[i + 1][1] = min (dp[i][0] + Z + Y, dp[i][1] + Y)
ランプがOFFの場合 CapsLock の後に Shift+a、ON の場合 Shift+a
初期値は以下となります。
- dp[0][0] = 0
- dp[0][1] = Z
C++ プログラム例（ABC303D）
上記で考察した漸化式をプログラムに落とし込みます。
求める解は、dp[文字列のサイズ][0] と dp[文字列のサイズ][1] の小さい方となります。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
ull x, y, z;
cin >> x >> y >> z;
string s;
cin >> s;
int size = s.length();
vector<vector<ull>> dp(size + 1, vector<ull>(2));
dp[0][0] = 0;
dp[0][1] = z;
for (int i = 0; i < size; ++i) {
if (s[i] == 'A') {
dp[i + 1][0] = min(dp[i][0] + y, dp[i][1] + z + y);
dp[i + 1][1] = min(dp[i][0] + z + x, dp[i][1] + x);
} else {
dp[i + 1][0] = min(dp[i][0] + x, dp[i][1] + z + x);
dp[i + 1][1] = min(dp[i][0] + z + y, dp[i][1] + y);
}
}
cout << min(dp[size][0], dp[size][1]) << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC303D）
Python 版も C++ 版のロジックを移植しました。
"""AtCoder Beginner Contest 303 D"""
x, y, z = map(int, input().split())
s = input()
INF = (1 << 60)
dp = [[INF for i in range(2)] for j in range(len(s) + 1)]
dp[0][0] = 0
dp[0][1] = z
for i in range(len(s)):
if s[i] == 'A':
dp[i + 1][0] = min(dp[i][0] + y, dp[i][1] + z + y)
dp[i + 1][1] = min(dp[i][0] + z + x, dp[i][1] + x)
else:
dp[i + 1][0] = min(dp[i][0] + x, dp[i][1] + z + x)
dp[i + 1][1] = min(dp[i][0] + z + y, dp[i][1] + y)
print(min(dp[len(s)][0], dp[len(s)][1]))こちらも「AC」と判定されました。
最後に
この問題は、コンテスト中に解くことができました。解いた後に疑問があり、@kyopro_friends 様に質問したところ、以下の回答をしていただけました（内容は、このブログの記事に追記しました。）。
非常に分かりやすい勉強になる解説をしていただけました。いつか、わたしも同じような活動ができればと思います。
引き続き ABC の問題を紹介していきます。
