じゃんけんの手の出し方 (paizaランク A 相当) Python解説

自己紹介

僕のX：
https://x.com/e4h99rhQ7I24670
この記事でおかしなところがあれば教えてください。

問題　URL

感想

Aランク問題相当にしては難しかった。(´;ω;｀)
（ただ僕の考察が下手なだけという説もある）
Atcoderでdiff200くらい

解説

N, Mの制約がそれほど大きくないので、へんな工夫をせずに考察をする。
ここで、なにも考えずに全探索をするとO(3^N)となりTLEする、
ここでの注目ポイントとしてはじゃんけんで出す種類ごとの数が決まれば、後は最大で勝てる順番に並び替えるのは簡単であるであること。

つまり、相手が出してきたものの順番は一切考えなくてよい。

ここで、自らがパーを出す回数をi回とすると、
チョキを出す回数は（M-5i)/2回になる。
グーを出す回数はN-i-(M-5i)/2回。

ただし、小数点以下が存在するときは、考えない。（continueする）

あとは最大で勝てる回数をそれぞれmin()をとってカウントするだけ。

実装

自分が出す種類ではなく、相手が出したものの種類数でカウントしている。
例えば相手がグーなら指を５本消費など。

N, M = map(int, input().split())
S = input()
ans = 0
G = 0
C = 0
P = 0

for i in range(N):
    if S[i] == 'G':
        G += 1
    elif S[i] == 'C':
        C += 1
    else:
        P += 1

for i in range(M//5+1):
    num_G = i
    num_P = (M-5*i)//2
    num_C = N-num_G-num_P
    if 5*num_G+2*num_P != M or num_G+num_P > G+P+C:
        continue
    ans = max(ans, min(num_P, P)+min(num_G, G)+min(num_C, C))
print(ans)