AtCoder が提供しているABC（AtCoder Beginner Contest）365 D問題をC++とPythonで解いてみました。ABC365は、2024年8月3日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 AtCoder Janken 3（Difficulty : 730）
問題の詳細は、リンク先をご覧ください。
この問題は貪欲法で解けません。DPを使います。AtCoder Problems による Difficulty は 730 でした。
解答案
相手が以下のように手を出したとします。
グー、グー、チョキ
貪欲法を採用する場合、初手はパーになります。2手目にパーをだすことができないためグーを出します。このため3手目にグーをだすことができずチョキを出すしかありません。結果的に1回しか勝つことができません。
一方、初手を引き分けにした場合、グー、パー、グーとだして2回勝つことができます。
勝つ場合と引き分けにする場合の選択が可能です。結果的に $2^n$ の選択肢がありますが、すべてを計算することはできません。このような場合は、DPの活用となります。
C++ プログラム例（ABC365D）
2次元の配列 dp[i][j] を i 番目までの手を選び、今回 j（0:グー、1:パー、2:チョキ）を選んだ勝ちの最大数とします。
相手がグーを出す場合、以下の選択肢があります。
- 自分はグーを出して、勝ち数は変わらない（19行目）。
- 自分はパーを出して、勝ち数を増やす（20行目）。
パー（22、23行目）とチョキ（25、26行目）も同じです。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
int main()
{
int n;
cin >> n;
string s;
cin >> s;
vector<vector<int>> dp(n + 1, vector<int>(3, -INF));
dp[0][0] = 0;
dp[0][1] = 0;
dp[0][2] = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == 'R') {
dp[i + 1][0] = max(dp[i][1], dp[i][2]);
dp[i + 1][1] = max(dp[i][0] + 1, dp[i][2] + 1);
} else if (s[i] == 'P') {
dp[i + 1][1] = max(dp[i][2], dp[i][0]);
dp[i + 1][2] = max(dp[i][0] + 1, dp[i][1] + 1);
} else if (s[i] == 'S') {
dp[i + 1][0] = max(dp[i][1] + 1, dp[i][2] + 1);;
dp[i + 1][2] = max(dp[i][0], dp[i][1]);
}
}
cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC365D）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 365 D"""
INF = 10 ** 9 + 1
n = int(input())
s = input()
dp = [[-INF for _ in range(3)] for _ in range(n + 1)]
dp[0][0] = 0
dp[0][1] = 0
dp[0][2] = 0
for i in range(n):
if s[i] == 'R':
dp[i + 1][0] = max(dp[i][1], dp[i][2])
dp[i + 1][1] = max(dp[i][0] + 1, dp[i][2] + 1)
elif s[i] == 'P':
dp[i + 1][1] = max(dp[i][2], dp[i][0])
dp[i + 1][2] = max(dp[i][0] + 1, dp[i][1] + 1)
elif s[i] == 'S':
dp[i + 1][0] = max(dp[i][1] + 1, dp[i][2] + 1)
dp[i + 1][2] = max(dp[i][0], dp[i][1])
print(max(dp[n][0], dp[n][1], dp[n][2]))こちらも「AC」と判定されました。
最後に
DPを使う問題には、タグをつけています。この問題は解けましたが、Diffが低い問題でも解けない場合があります。まだ理解が浅いのかもしれません。
引き続き ABC の問題を紹介していきます。
