AtCoder ABC 046 D - AtCoDeerくんと変なじゃんけん (ARC 062 D) (2Q, 水色, 300 点)

一見、 の DP に見えたが、その必要はなかった。

• 問題へのリンク

問題概要

グーとパーしか出せないジャンケンを 回する。相手が各回に何を出すかが予めわかっている。ただし、どの時点でも

(それまでに出したグーの回数) (それまでに出したパーの回数)

を満たし続けなければならない。

(勝つ回数) - (負ける回数) の最大値を求めよ。

制約

• 

考えたこと

一瞬、次のような DP を考えた。

• dp[i][j]：最初の 回のジャンケンで、(グーを出した回数) - (パーを出した回数) = であるようにしたときの、(勝った回数) - (負けた回数) の最大値

しかし、これでは の計算量となってしまう。そして、容易には改善できなさそうだった。

そこで作戦を考えて「実はグーとパーを出す順序はあまり関係ないのでは」という方面の考察をしてみた。そして、この予想はあたった。

---

ある 2 回で出す手が「パー、グー」であるとき、これを入れ変えて「グー、パー」にしても、次の通り、スコアが変わらないのだ。

• 相手が「パー、パー」のとき：-1
• 相手が「パー、グー」のとき：0
• 相手が「グー、パー」のとき：0
• 相手が「グー、グー」のとき：1

---

よって、グーの回数とパーの回数だけが問題なのだ。なるべく多くのパーを出したいので、

• グーの回数：(N + 1) / 2 回
• パーの回数：(N - 1) / 2 回

とするのがよいだろう。あとは、最初の (N + 1) / 2 回グーを出して、後半の (N - 1) / 2 回パーを出すとして、勝敗を求めれば良い。

計算量は となる。

コード

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

int main() {
    string S;
    cin >> S;
    int N = S.size(), res = 0;
    for (int i = 0; i < (N + 1) / 2; i++) {
        if (S[i] == 'p') res--;
    }
    for (int i = (N + 1) / 2; i < N; i++) {
        if (S[i] == 'g') res++;
    }
    cout << res << endl;
}