paiza Aランク相当練習問題 じゃんけんの出し方を解いてみた

paiza Aランク相当の練習問題「じゃんけんの出し方」をPython3で解いてみました。 問題文などは下記リンク先をご参照ください。 問題文を見るだけならログイン不要です。

paiza.jp

提出結果です。回答にかかった時間を手元で計測していましたが、27分でした。

以下が提出したコードです。

N, M = map(int, input().split())
s = list(input().rstrip())
G = len([x for x in s if x == 'G'])
C = len([x for x in s if x == 'C'])
P = len([x for x in s if x == 'P'])

patterns = []
for i in range(0, N+1):
    for j in range(0, N+1):
        if 2*i + 5*j == M and N - i - j >= 0:
            patterns.append([i, j])

ans = 0
for c, p in patterns:
    win = 0
    win += min(G, p)
    win += min(P, c)
    win += min(C, N - c - p)
    ans = max(ans, win)

print(ans)

入力パターンから相手が出すグー・チョキ・パーの数をそれぞれカウントしておきます。 次に、こちらがグーを出す場合は指の数は増えないので、チョキとパーに関して指の合計がM本になる組み合わせを列挙します。 列挙した各パターンと、カウントしておいた相手が出す手の数から勝利数の最大値を求めます。

最初はDPや再帰を使った問題なのかなぁと悩みましたが、思ったより簡単な方法で解くことができました。

難易度はAtCoder ABCでいうとBとCの中間ぐらいに感じました。