実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 730

問題概要

高橋君と青木君が $N$ 回のじゃんけんを行った。青木君が出した手は各文字がR(グー)、P(パー)、S(チョキ) のいずれかである長さ $N$ の文字列 $S$ で表される。高橋君の出した手は、次の2つの条件を満たす。

青木君に1回も負けなかった。
連続して同じ手を出さなかった。

このとき、高橋君が青木君に勝った回数としてあり得る最大値を求めよ。

制約

$N$ は整数で、 $1 \leq N \leq 2 \times 10^5$ を満たす。

考察

とりあえずサンプルケース1で考えてみよう。「各回で高橋君が何を出したか」と「現在までに勝った回数の最大値」をまとめると下図のようになる。

1回目のじゃんけんでは青木君は「パー」を出した。

高橋君は「チョキ」を出した場合は青木君に勝つことができ、ここまでの最大勝利数は1回である。
「パー」を出すと「あいこ」となり、ここまでの最大勝利数は0回である。
「グー」を出すと負けてしまうため、このケースは考えない。

2回目のじゃんけんでは青木君は「グー」を出した。

1回目に高橋君が「チョキ」または「パー」を出した場合は2回目で「グー」を出すことで「あいこ」となり、ここまでの最大勝利数は1回である。
一方、2回目で「パー」を出した場合は青木君に勝つことができ、ここまでの最大勝利数は2回である。
2回目で「チョキ」を出した場合は青木君に負けてしまうため、このケースは考えない。

このように考えていくと、 $i \: (0 \leq i \leq N-1)$ 回目における最大勝利数の結果から $i$ 回目の最大勝利数の結果を計算できるため、以下のような DP テーブルを作ることができる。

$\mathrm{dp}[i][j] := i 回目に高橋君が手 j を出したとき, i 回目までに高橋君が条件を満たす手を出して青木君に勝った回数の最大値 \quad (0 \leq i \leq N - 1, \: j \in \{0, 1, 2\})$

ただし、 $j = 0$ がR、 $1$ がP、 $2$ がSに対応している。

初めに全てのテーブルを $0$ で初期化すると、以下の漸化式が立てられる (初期条件も含む) 。なお、 $S_i$ は 0-indexed である。

$\mathrm{dp}[i+1][0] = \left\{ \begin{array}{} \max(\mathrm{dp}[i][1], \mathrm{dp}[i][2]) & (S_i = \text{R}) \\ \max(\mathrm{dp}[i][1], \mathrm{dp}[i][2]) + 1 & (\text{else}) \\ \end{array} \right. \\ \mathrm{dp}[i+1][1] = \left\{ \begin{array}{} \max(\mathrm{dp}[i][0], \mathrm{dp}[i][2]) & (S_i = \text{P}) \\ \max(\mathrm{dp}[i][0], \mathrm{dp}[i][2]) + 1 & (\text{else}) \\ \end{array} \right. \\ \mathrm{dp}[i+1][2] = \left\{ \begin{array}{} \max(\mathrm{dp}[i][0], \mathrm{dp}[i][1]) & (S_i = \text{S}) \\ \max(\mathrm{dp}[i][0], \mathrm{dp}[i][1]) + 1 & (\text{else}) \\ \end{array} \right. \\$

求めるべき答えは $\max(\mathrm{dp}[N][0], \mathrm{dp}[N][1], \mathrm{dp}[N][2])$ となる。

ここまで分かれば後はプログラムに落とし込むだけである。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    string S;
    cin >> S;

    vector<vector<int>> dp(200020, vector<int>(3, 0));
    rep(i, 0, N)
    {
        if (S[i] == 'R')
        {
            dp[i + 1][0] = max(dp[i][1], dp[i][2]);
            dp[i + 1][1] = max(dp[i][0], dp[i][2]) + 1;
        }
        else if (S[i] == 'P')
        {
            dp[i + 1][1] = max(dp[i][0], dp[i][2]);
            dp[i + 1][2] = max(dp[i][0], dp[i][1]) + 1;
        }
        else
        {
            dp[i + 1][2] = max(dp[i][0], dp[i][1]);
            dp[i + 1][0] = max(dp[i][1], dp[i][2]) + 1;
        }
    }

    cout << max({dp[N][0], dp[N][1], dp[N][2]}) << endl;
}