AtCoder Regular Contest 046 - B - 石取り大作戦
8回もWA.iconも出してしまった。。だめだこれ
https://gyazo.com/f21b72ab0728b9adda2e580e76af5045
考えたこと
部分点にもあるけど、$ A = Bと$ A \neq Bで分けた考えた方が良さそう
パッと答え出せる問題ではなさそう?勝利条件を1つづつ網羅しないといけなさそう
まず$ A = Bの場合を考える
勝利条件1 $ N \leq A であれば先手の勝ち(これは$ A \neq Bも同様かも)
1ターンキルできるので
勝利条件2 $ N = A + 1の時は後手の勝ち
例えば$ N=5で$ A,B=4の場合、先手は1~4取ることができるが、どれを選んでも勝てない
これ以外は先手の勝ちかな?
次に$ A \neq Bの場合は
$ A \gt Bだったら先手の勝ちだし、そうじゃなかったら後手の勝ち?
証明はできないけど、数大きい方がコントロール権持てそうなので
これで出したら、$ A \neq Bは正解だったけど、$ A = BでWA.iconが出た。
N を A + 1 で割ったあまりが 0 のとき、後手必勝
– 先手がどのように石を取っても、後手は石の数を A + 1 で 割ったあまりが 0 となるように石を取り続けることが可能
$ N = A + 1を考えたのはよかったけど、そのあとの詰めが甘かった.
最終的に$ N = A + 1を相手に投げつけたいので、先にこの条件を掴んだ方が勝ちになる。
提出したコード
code: B.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
int main() {
ll n,a,b; cin >> n >> a >> b;
if(a == b) {
if(a==1) {
// 1つしか取れない場合は奇数or偶数で判定可能
if(n%2==1) cout << "Takahashi" << endl;
else cout << "Aoki" << endl;
} else if(n <= a) {
// 1ターンキル
cout << "Takahashi" << endl;
} else if(n%(a+1) == 0) {
cout << "Aoki" << endl;
} else {
cout << "Takahashi" << endl;
}
} else {
if(a > b || n <= a) cout << "Takahashi" << endl;
else cout << "Aoki" << endl;
}
return 0;
}
考察不足が過ぎる