ABC149 D - Prediction and Restriction
問題
考察
まず手の制約はどんなものなのかを考えてみます。
https://gyazo.com/61b4f1e7e15e168bd6bedb669d6b1823
手が影響を与えるのは
$ 0 \rightarrow K \rightarrow 2K \rightarrow \dots
$ 1 \rightarrow K + 1 \rightarrow 2K + 1 \rightarrow
$ \dots
で、この系列のそれぞれが影響を与え合うことはないので独立して考えて良いです。これはmodで類別することに相当します。 $ {\rm dp}_{i,j}を$ \lbrack 0, i \rbrackを利用して、$ i番目の手で$ jを出したときのスコアの最大値とします。
あとは、だした手の分スコアを足して、$ {\rm dp}_{i,j} \rightarrow {\rm dp}_{i+K,l} (l \ne j)と遷移させていけばよいです。
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() int N, K, R, S, P;
string T;
int main() {
cin >> N >> K >> R >> S >> P >> T;
unordered_map<char, int> score, idx;
vector<vector<ll>> dp(N, vector<ll>(3, 0));
rep(i, N) rep(j, 3) {
dpij += ((idx[Ti] + 1) % 3) == j ? score[Ti] : 0; if (i + K < N) rep(l, 3) if (l != j) {
}
}
ll ans = 0;
rep(i, K) ans += *max_element(all(dpN - 1 - i)); cout << ans << endl;
return 0;
}
勝てる手が前回出した手と同じ場合
次の手の邪魔にならない手を出す
勝てる手が前回出した手と違う場合
勝つ
証明
勝てる手が前回出した手と同じ場合に、次の手の邪魔になる手を出すと次の手で勝てなくなるので損です。
勝てる手が前回出した手と違う場合には、
1. 勝たない
この場合次の手の邪魔にならない手を出すことで、次の手では必ず勝てます。
2. 勝って次の手の邪魔にならない
この場合今の手も次の手も勝てます。
3. 勝つが次の手の邪魔になる
この場合今の手でのみ勝てますが、邪魔になるということは今勝てる手と次勝てる手が同じということなので、次の手でのみ勝てる1と同じスコアになります。
以上から勝てる場合には勝つことで損をしないことがわかります。
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() int N, K, R, S, P;
string T;
int main() {
cin >> N >> K >> R >> S >> P >> T;
unordered_map<char, int> score;
unordered_map<char, char> enemy;
ll ans = 0;
rep(i, K) {
char h = '?';
for (int j = i; j < N; j += K) {
if (j + K < N) h = Tj + K; } else {
}
}
}
cout << ans << endl;
return 0;
}