← 返回题目列表

AtCoder · nomura2020_b

B. 博士后

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

对于字符串 S 由大写英文字母组成 P 和 D,让 博士和博士后商数 of S 是出现的总次数 D 和 PD in S 作为连续子字符串。例如,如果 S = PPDDP,它包含两次出现 D 并且出现一次 PD 作为连续子串,因此博士和博士后商 S is 3.

我们有一个字符串 T 组成 P, D,和 ?.

各个字符串替换即可得到 ? in T 与 P or D,找到一个拥有最大可能的博士和博士后商数的人。

约束

  • 1 \leq |T| \leq 2 \times 10^5
  • T 包括 P, D,和 ?.

输入

输入由标准输入按以下格式给出:

T

输出

打印一个字符串,在替换每个字符串后得到的字符串中,博士商和博士后商数最大 ? in T 与 P or D。 如果有多个这样的字符串,您可以打印其中任何一个。


示例输入 1

PD?D??P

示例输出 1

PDPDPDP

该字符串包含 3 次出现 D 和 3 次出现 PD 作为连续子串,因此其博士商和博士后商为 6,这是通过替换每个字符串获得的最大博士和博士后商 ? in T 与 P or D.


示例输入 2

P?P?

示例输出 2

PDPD