Game Theory (HackerRank) : Poker Nim
問題
Programming Problems and Competitions :: HackerRank
n個のチップの山がある。
それぞれの山には個のチップがある。
2人のプレイヤーは、それぞれのターンで1個の山を選び、1つ以上のチップを取り除くか加えるかする。
ただし、各プレイヤーは、どんな山においてもK回以上の追加操作は出来ない。
先に操作の出来なくなったほうが負けである時、勝つのはどちらか。
解法
Nimと同じで、各山のサイズのXORを取る。
増やされても1手で元に戻せることと、増やされる操作は有限回しか行われないことから、増える操作は完全に無視できる。
実装
#define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define int long long int T, N, K, C[100]; signed main() { cin >> T; for (int tc = 0; tc < T; tc++) { cin >> N >> K; int x = 0; for (int i = 0; i < N; i++) { cin >> C[i]; x ^= C[i]; } puts(x ? "First" : "Second"); } return 0; }