ARC046 B - 石取り大作戦

AtCoder やり直し

解法

N <= Aの時

絶対に先行が勝つ

N > Aの時
  • A > Bの時

N > A > Bであるため先攻が1個だけとる戦法をとると絶対にN > Bにできる。N <= Aになったら全部取れば良い。よって先攻が勝つ。

  • A < Bの時

N > B > Aである。A > Bの時と同様に考えると、後攻が絶対勝つ。

  • A == Bの時

A + 1個にされると絶対勝てない

2(A + 1)個にされると絶対勝てない

.

.

.

x(A+1)にされると絶対に勝てない。

つまりN % (A + 1) = 0なら後攻が勝ち、そうでないなら先攻が勝ちとなる。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
void f() {cout << "Takahashi" << endl;}
void s() {cout << "Aoki" << endl;}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, A, B; cin >> N >> A >> B;
  if(N <= A) f();
  else {
    if(A > B) f();
    else if(A < B) s();
    else {
      if(N % (A + 1) == 0) s();
      else f();
    }
  }
  return 0;
}

ゲーム系は苦手だな〜。