今日勉強したことを
つらつらと
logo

abc149_dの解き方の解説 全探索できるので、よく考えれば簡単

2020/05/26 22:05
AtCoder Beginner Contest 149のD問題 Prediction and Restrictionを解く。

感謝の正拳突き1万回ならぬ、競プロサイトで 1 日 1AC(正解)するように頑張る。

ABC149 の D 問題 Prediction and Restrictionを解いていきます。普通に全探索で解けるので簡単でした。

出した手にに対応した得点を返す

そのまんまですね・・

  • r(グー・rock)だったら p(パー・paper)の得点を返す
  • s(チョキ・scissors)だったら r の得点を返す
  • グーでもチョキでもなければ s の得点を返す

出せない場合かどうか考える

k までは出せない手はないので、得点をそのまま加算します。

i < k

k 回前が同じ手だったら、同じ手を出せないので得点できません。

t[i] != t[i - k]

ただし、k 回前に勝てる手を出せなかったら、今回は出せます。なので出せなかったのかどうかをメモしておきます。

出せなかった回の k 回後のこと考えなくていいの?

例えば k = 1 だとして、グー・グー・チョキを出してきたとします。

パー・グーと出してしまうと次にグーを出せなくなってしまいます。

しかし今回はあいこと負けは同じ得点です。なのでパー・チョキ・グーと出せばいいのです。

なんだか簡単すぎることを説明すると冗長になりますね・・

できあがり

#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll n, k, r, s, p;
string t;
// 出した手にに対応した得点を返す
int score(char hand) {
    if(hand == 'r') return p;
    if(hand == 's') return r;
    return s;
}
int main() {
  cin >> n >> k >> r >> s >> p >> t;
  ll result = 0;
  vector<bool> memo(n);
  for(int i = 0; i < n; i++) {
      if(i < k || t[i] != t[i - k] || memo[i - k]) {
          result += score(t[i]);
      } else {
          // 手が出せなかったことをメモしておく
          memo[i] = true;
      }
  }
  cout << fixed << result;
}

© 2021 simodake