BETA

初心者日記(3)『Atcoder (Postdocs)を解く』

投稿日:2020-06-09
最終更新:2020-06-24

AtCoderにはABCの他にも色々なコンテストがある。その中で今日解いた『NOMURA プログラミングコンテスト 2020』のB問題、『Postdocs』が面白かったので記事にする。

問題は D と PD の合計が一番多くなるように、? に P か D を入れる。
例を見たら

PD?D??P  
↓  
PDPDPDP  

P?P?  
↓  
PDPD  

となっていたので、『もしかしたら交互に配置すれば最大になる?』という考えに至った。

t = list(input())  

for i in range(len(t)):  
    if i == 0 and t[i] == '?':  
        t[i] = 'D'  

    if 0 < i and t[i] == '?':  
        if t[i-1] == 'P':  
            t[i] = 'D'  
        else:  
            t[i] = 'P'  

print(''.join(t))  

とりあえず前の文字が P なら D、D なら P を ? に代入するようにしてみた。先頭が ? の場合は PD で点数を稼げないと考え、 D を固定で入れるようにしている。しかし、不正解だったのでさらに考える。

t = list(input())  

for i in range(len(t)):  
    if i == 0 and t[i] == '?':  
        t[i] = 'D'     

    if 0 < i < len(t) - 1 and t[i] == '?':  
        if t[i-1] == 'P':  
            t[i] = 'D'  
        else:  
            t[i] = 'P'  

    if i == len(t) -1 and t[i] == '?':  
        t[i] = 'D'  

print(''.join(t))  

最後が ? のとき、その前の文字が D の場合 P を出力して、点数が下がることに気づいた。そこで、最後の文字は絶対に D を出力するように変更したが、不正解だった。

t = list(input())  

for i in range(len(t)):  
    if i == 0 and t[i] == '?':  
        t[i] = 'D'  

    if 0 < i < len(t) - 1 and t[i] == '?':  
        if t[i-1] == 'P':  
            t[i] = 'D'  
        elif t[i+1] == 'P':  
            t[i] = 'D'  
        else:  
            t[i] = 'P'  

    if i == len(t) -1 and t[i] == '?':  
        t[i] = 'D'  

print(''.join(t))

次の文字が P の場合に D?P の配置が来ると、DPP となり点数が下がる次の文字が P の場合も ? に D を代入するように変更すると、正解になった。

まとめ:楽しかった。

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

tnodino(つのでぃの)のブログ。日頃の内容を記事にしています。

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう