AtCoder

ABC303 D問題(Shift vs. CapsLock)を解く

AtCoder_ABC303_D

AtCoder が提供しているABC(AtCoder Beginner Contest)303 のD問題をC++とPythonで解いてみました。ABC303は、2023年5月27日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Shift vs. CapsLock(Difficulty : 778)

問題はリンク先をご覧ください。

ABC303 D問題 Shift vs. CapsLock

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 様に質問したところ、以下の回答をしていただけました(内容は、このブログの記事に追記しました。)。

質問とその解答

非常に分かりやすい勉強になる解説をしていただけました。いつか、わたしも同じような活動ができればと思います。

ABC303 について、引き続き問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA