Postdocs [NOMURA Programming Competition 2020 B]

https://atcoder.jp/contests/nomura2020/tasks/nomura2020_b

解説

https://atcoder.jp/contests/nomura2020/submissions/13929093

?にPを入れるかDを入れるかをDPで最適解を求めて、復元して答えを求める…
というのも1つの手ではあるが、200点問題としては厳しいだろう。

最適方針が存在する。
?には常にDを入れるのが最適になる。
Dを入れる時とPを入れる時をそれぞれ考えてみる。
Dを入れると必ず1pt入る。
Pを入れると、次がDの時に限り1pt入る。
Pを入れることで後々2pt入ることもないので、常にDを入れておけばいい。

?をDに変換して答える。

string T;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> T;
    fore(c, T) if (c == '?') c = 'D';
    cout << T << endl;
}