abc149_dの解き方の解説 全探索できるので、よく考えれば簡単
2020/05/26 13:05
感謝の正拳突き１万回ならぬ、競プロサイトで 1 日 1AC(正解)するように頑張る。
ABC149 の D 問題 Prediction and Restrictionを解いていきます。普通に全探索で解けるので簡単でした。
出した手にに対応した得点を返す
そのまんまですね・・
- r(グー・rock)だったら p(パー・paper)の得点を返す
- s(チョキ・scissors)だったら r の得点を返す
- グーでもチョキでもなければ s の得点を返す
出せない場合かどうか考える
k までは出せない手はないので、得点をそのまま加算します。
i < kk 回前が同じ手だったら、同じ手を出せないので得点できません。
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;
}