Python3で解く AtCoder Beginner Contest 149 D - Prediction and Restriction

じゃんけんにおいて、事前に相手が出す手がわかっていて、何を出して勝ったかで得点が異なる時に、何回かじゃんけんして特典の最大値を求める問題（ほぼ概要だな）。

目次

概要

問題

• 回 じゃんけんを行う。
• プレイヤーがじゃんけんで勝った場合、プレイヤーは出した手に応じて以下のスコアを得る (あいこや負けは 0点)。
  • グーで勝った場合 点
  • チョキで勝った場合 点
  • パーで勝った場合 点
• 回前のじゃんけんで出した手と同じ手を出すことはできない。
• プレイヤーは能力者で相手が何を出すかが予知できる。
• 文字列の左から文字目に相手の手が書かれている。
• 例えばなら、グー・チョキ・パーの順でと出すと予知したという事。
• この時、得られる最大値は？

---

解くときに考えた内容

• 回目までとそれ以降で考える。
  • 回目までは、何も考えず勝てばいい。
  • 回目より後だと、例えば、の時に、最初のはよくて、３回目のはとにかく勝てない。でもここでをのどちらかを選べるが５回目のの時に勝つためには３回目の時にを出しておく必要がある。
  • ということは、勝てない時は負けてもあいこでも得点が変わらないので、「遊びがある」状態なので、とが同じ時は勝てないと考えるでよい。
• あとはとが異なる時のを数えてそれぞれの得点を掛け合わせた時が最大値となる。

---

コード

from collections import Counter

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = list(input())
l = list()
ans = 0
for i in range(k):
    l.append(t[i])
for i in range(k, n):
    if l[i-k] == t[i]:
        # 勝てない状態
        l.append(None)
    else:
        # 勝てる手を必ず選べる
        l.append(t[i])
res = Counter(l)
ans = res['r'] * p + res['s'] * r + res['p'] * s
print(ans)

---

書籍

アルゴリズムの参考書籍

まだ、発売されていないが内容に期待している一冊。

• 問題解決力を鍛える!アルゴリズムとデータ構造
  けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。（というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので）
  投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

drken1215.hatenablog.com

• プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい） ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

最近ポチった書籍

• ゼロからつくるPython機械学習プログラミング入門

機械学習スタートアップシリーズ ゼロからつくるPython機械学習プログラミング入門 (KS情報科学専門書)

アルゴリズムとは関係ないが、一応機械学習も生業としているので、関連書籍は目を通すようにしている。 強いていうならば、第3章の数学のおさらいの最適化・確率あたりは関連がある。その他、回帰分析・分類・ニューラルネットワーク・強化学習・教師なし学習とかなり幅広く、初学者が一通り学ぶには良さそうである。これは別記事で紹介する予定である。

• 実用的でないPythonプログラミング

実用的でないPythonプログラミング: 楽しくコードを書いて賢くなろう!

バカ売れしているのか、アマゾンでは値段があがっている。自分は、予約していたのに来ないので、楽天で購入した。 内容としては、面白いテーマの物が多く、pygletなどを使って描画もあるような内容が結構推されているが、アルゴリズムに関する内容もある。特に前半は文字列を操作して暗号解読であったり、アナグラム・回文といったものが扱われているので勉強になる。遺伝的アルゴリズムも面白く金庫破りの実装は非常に参考になった。

blacktanktop.hatenablog.com