ABC195 E Lucky 7 Battle
最近忙しくてこまる。精進する精神的な余裕が.......。 何かDPをするのはわかったんだけど微妙に合わなかった。たすけて
問題概要
読んで
考察
うーん、7で割ったあまりで状態が表せることはわかって、前からDPしたけどダメでしたね。
こういうゲーム系の問題を状態遷移で考える時は、後ろから必勝かどうかを考えていくといいらしい。そういえばgrundy数とかもそんな感じですね。これは典型として絶対覚えておきます。
後ろからやるタイプのDPはよくある「番目までみたときに云々」ではなく「番目から始めたときに云々」と解釈すると頭がすっきりします。
ターン目に7で割ったあまりがである状態から始めたとき、高橋君の勝ちが確定しているかどうか という関数を考えます。
え、これ初期化どうすんねん。後ろから必勝かどうかを考えたい -> まず一番後ろの判定どうするの という気持ちになって困ってしまいました。しかし上の定義をよく考えると、ターン目から始めたときに勝つかどうかなので、ターン目に7で割ったあまりがのものだけ勝つということが言えます。
そして遷移は
- を採用するかをつけるかで場合分け
- 高橋君のターンか青木君のターンかで場合分け
の二つについて考える必要があります。
まず一つ目の場合分けですが、
を採用した場合が次のあまりになり、
を採用した場合はが次のあまりになります。
これを踏まえたうえで二つめの場合分けを考えます。
まずどちらのターンにしろ、後ろから更新していくので ()の状態は勝つか負けるかが確定しています。
自然言語で説明すると「番目のターンから始めたときどうなるか」がわかっているので、その情報をもとに「番目のターンから始めたらどうなるか」を考えたいです。
- 高橋君のターンの場合
結論から言うと、
とおいて、
です。
自然言語で説明すると、「ターン目からターン目にはかのどちらかを選ぶことで遷移出来て、そのターン目のどちらか片方でも勝ちが確定した状態であればそちらに遷移すればいいので、ターン目から始めても高橋君の勝ちが確定した状態になる」
ということになります。
- 青木君のターンの場合
やはり結論から言うと
です。やは高橋君のターンと同じ値を表しています。
自然言語で説明すると、「ターン目からターン目にはかのどちらかを選ぶことで遷移出来て、そのターン目が両方とも勝ち確定状態だった場合のみ、青木君は逃げ場がないのでターン目から始めても高橋君の勝ちが確定した状態になる」
ということです。
これを実装するとACします。以下コード。やっぱメモ化再帰はラムダ式が楽だなあ。
#include <bits/stdc++.h> const int INF = 1e9; const int MOD = 1e9+7; const long long LINF = 1e18; #define dump(x) cout << 'x' << ' = ' << (x) << ` `; #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define rep(i,n) for(ll i=0;i<(n);++i) #define REPR(i,n) for(ll i=n;i>=0;i--) #define FOREACH(x,a) for(auto& (x) : (a) ) typedef long long ll; using namespace std; typedef pair<ll, ll> P; template<typename T> void print(const vector<T> &x) { int n = x.size(); rep(i,n) { cout << x[i]; if (i!=n-1) cout<<" "; else cout << endl; } } template<typename T> void print(const vector<vector<T>> &x) { int n = x.size(); rep(i,n) { rep(j,x[i].size()) { cout << x[i][j] << " "; } cout << endl; } } template<typename T> void print(const vector<T> &x, int n) { rep(i,n) { cout << x[i]; if (i!=n-1) cout<<" "; else cout << endl; } } template<typename T> void print(const vector<vector<T>> &x, int n, int m) { rep(i,n) { rep(j,m) { cout << x[i][j] << " "; } cout << endl; } } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } void input_init() { cin.tie(0); ios::sync_with_stdio(false); } int main(int argc, char const *argv[]) { int n; cin>>n; string s,t; cin>>s>>t; vector<vector<bool>> memo(n+1, vector<bool>(7, false)); vector<vector<bool>> vi(n+1, vector<bool>(7, false)); auto dp = [&](auto &&f, int i, int j) -> bool { if (i == n) return (j == 0); if (vi[i][j]) return memo[i][j]; vi[i][j] = true; int d = s[i]-'0'; int x = (10*j+d)%7; int y = (10*j)%7; bool ret = false; if (t[i] == 'A') { ret |= (f(f, i+1, x) && f(f, i+1, y)); } else { ret |= (f(f, i+1, x) || f(f, i+1, y)); } return memo[i][j] = ret; }; if (dp(dp, 0, 0)) cout << "Takahashi" << '\n'; else cout << "Aoki" << '\n'; return 0; }