この問題はGreedyアルゴリズムによって解決された.PPAP文字列のうちの1つのPをPPAPに置き換える文字列がPPAPの定義となるには、少し理解する必要がある.
この定義を簡単な例にまとめると、PPAP->PPAPPAP(1番PがPPAPである場合)、PPPAPAP(2番PがPPAPである場合)、PPAPPAP(3番PがPPAPである場合)に変換することができ、これらの文字列はいずれもPPAPに対応する.
ルールを探すのに少し時間がかかりました.

Aが必要です.

からは、Pが2つ以上存在した後にAが必要である.

Aは2回連続して現れない.

ルールに基づいて、次の問題が解決されました.

文字列がPの場合、stベクトルにPを入れてtrueを返します.

文字列の長さでチェックします.

文字列の現在のインデックスの文字がPである場合、stベクトルpush back(「P」)に向かいます.

文字列の現在のインデックスはPではなく、stに入るPが2より大きく、次のインデックスに対応する文字がPである場合、stベクトルにpop back()がある.

のほかfalseも返されます.

文字列の長さでチェックが正常に完了した場合、trueが返されます.

xcodeではよく実行されていますが、Baekに提出され、70%の人がエラーに答えました.反例を考えるとPPPPはPPAPではないと思います.本人が作成したコードではPPPPもtrueを返すためエラー処理される.

PPPをNPに出力するために、ソリューション関数の最後にstに入るPの長さをチェックし、Pが1であればtrueを返し、1でなければfalseを返す.PPAP -> st: +P , +P , -P , -P , +P st.size()=1PPPAPAP -> st: +P , +P , +P , -P , -P , +P , -P , -P , +P st.size()=1PPPP -> st: +P , +P , +P , +P st.size()=4

Code

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string ppap;
vector<int> st;

void Input(){
    cin>>ppap;
}

bool Solution(){
    if(ppap.size()==1&&ppap.front()=='P'){
        st.push_back('P');
    }
    else{
        for(int i=0; i<ppap.size(); i++){
            if(ppap[i]=='P'){
                st.push_back('P');
            }
            else if(st.size()>=2&&ppap[i+1]=='P'){
                st.pop_back();
                st.pop_back();
            }
            else{
                return false;
            }
        }
    }
    if(st.size()==1)
        return true;
    else
        return false;
}

void Solve(){
    if(Solution())
        cout<<"PPAP"<<endl;
    else
        cout<<"NP"<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solve();
    return 0;
}