/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
英大文字 P および D からなる文字列 S について、S が連続する部分文字列として含む D および PD の個数の和を S の「博士・PD 指数」と呼びます。例えば S = PPDDP のとき、S は連続する部分文字列として 2 個の D と 1 個の PD を含んでいるので、S の博士・PD 指数は 3 です。
P, D, ? からなる文字列 T があります。
T に含まれる ? をそれぞれ P または D のいずれかで置き換えてできる文字列の中で、博士・PD 指数が最大のものを 1 つ求めてください。
制約
- 1 \leq |T| \leq 2 \times 10^5
- T は
P,D,?からなる。
入力
入力は以下の形式で標準入力から与えられる。
T
出力
T に含まれる ? をそれぞれ P または D で置き換えてできる文字列の中で、博士・PD 指数が最大のものを 1 つ出力せよ。
そのような文字列が複数ある場合、どれを出力しても構わない。
入力例 1
PD?D??P
出力例 1
PDPDPDP
この文字列は連続する部分文字列として 3 個の D と 3 個の PD を含みます。
よってこの文字列の博士・PD 指数は 6 です。
T に含まれる ? をそれぞれ P または D で置き換えてできる文字列の中で、これは最大の博士・PD 指数です。
入力例 2
P?P?
出力例 2
PDPD
Score : 200 points
Problem Statement
For a string S consisting of the uppercase English letters P and D, let the doctoral and postdoctoral quotient of S be the total number of occurrences of D and PD in S as contiguous substrings. For example, if S = PPDDP, it contains two occurrences of D and one occurrence of PD as contiguous substrings, so the doctoral and postdoctoral quotient of S is 3.
We have a string T consisting of P, D, and ?.
Among the strings that can be obtained by replacing each ? in T with P or D, find one with the maximum possible doctoral and postdoctoral quotient.
Constraints
- 1 \leq |T| \leq 2 \times 10^5
- T consists of
P,D, and?.
Input
Input is given from Standard Input in the following format:
T
Output
Print one string with the maximum possible doctoral and postdoctoral quotient among the strings that can be obtained by replacing each ? in T with P or D.
If there are multiple such strings, you may print any of them.
Sample Input 1
PD?D??P
Sample Output 1
PDPDPDP
This string contains three occurrences of D and three occurrences of PD as contiguous substrings, so its doctoral and postdoctoral quotient is 6, which is the maximum doctoral and postdoctoral quotient of a string obtained by replacing each ? in T with P or D.
Sample Input 2
P?P?
Sample Output 2
PDPD