AtCoder Regular Contest 046 B - 石取り大作戦

,

典型的な実験ゲー。 もちろんnimではない。単一のimpartial gameだし。

B - 石取り大作戦

解法

実験。

判断基準はだいたい以下のようなもの。

  • 入力が十分大きいこと
    • 線形は無理
    • 対数はなさそう
  • 出力が0/1であること
    • 規則性を見つけやすい
  • 明らかに一方が有利であること
    • $A \lt B$で$N$が十分大きいなら$B$側が必ず勝ちそう

実装

#!/usr/bin/env python3
n = int(input())
a, b = map(int,input().split())
if a < b:
    ans = n <= a
elif a > b:
    ans = True
else:
    ans = n % (a + 1) != 0
print(['Aoki','Takahashi'][ans])

実験用

#include <iostream>
#include <vector>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <typename T>
ostream & operator << (ostream & output, vector<T> const & a) {
    repeat (i, int(a.size())) { if (i) output << ' '; output << a[i]; }
    return output;
}
int main() {
    ll n, a, b; cin >> n >> a >> b;
    assert (n < 100);
    ll l[2] = { a, b };
    vector<vector<bool> > dp(2, vector<bool>(n+1));
    repeat (i,n+1) {
        repeat (j,2) {
            repeat_from (k, max(0ll,i-l[j]), i) {
                if (not dp[j^1][k]) {
                    dp[j][i] = true;
                    break;
                }
            }
        }
    }
    cerr << n << endl;
    cerr << a << ' ' << b << endl;
    cerr << dp[0] << endl;
    cerr << dp[1] << endl;
    cout << (dp[0][n] ? "Takahashi" : "Aoki") << endl;
    return 0;
}