問題 Programming Problems and Competitions :: HackerRank サイズがnの数列A, Bがある。 2人のプレイヤーはそれぞれのターンで以下の操作を行う。 ・0 ・プレイヤー1ならA[i]点、プレイヤー1ならB[i]点を得る。 ・ゲーム全体で、同じiを2回選ぶことは出来ない。 最後に、点数の総和が大きい方が勝ち。 勝つのはどちらか。

…ゲームの分割の性質(Game Theory (HackerRank) : Tower Breakers, Again! - 4bitにっき)を使う。 累積和を使って座標(0, 0)を左上とする長方形領域について素数の数を求めておくと、任意の長方形領域に含まれる素数の数がO(1)で求まる。 (参考: 惑星探査 Planetary Exploration | Aizu Online Judge)累積和の前計算は各テストケースについてしかかからないので、DP(メモ化再帰)の計算量を…

…hessboard Game(Game Theory (HackerRank) : A Chessboard Game - 4bitにっき)の駒がk個(k 解法 上に貼った問題(Chessboard Game)の時もGrundy数を求めて殴ったので、同じように各駒のGrundy数を求めてXORを取る。(Grundy数のゲームの分割についての性質(Game Theory (HackerRank) : Tower Breakers, Again! - 4bitにっき)を使う) 実…

… Breakes( Game Theory (HackerRank) : Tower Breakers, Revisited! - 4bitにっき )と同じように約数列挙を使って、各のGrundy数がで求まる。 全体でも同じく。 実装 #include <bits/stdc++.h> using namespace std; #define int long long int T, N, H[100]; int memo[1000001]; int Grundy(int n)…

…ルールはほぼ同じ。 Game Theory (HackerRank) : Tower Breakers - 4bitにっき 今度はN個の山の高さがそれぞれとなる。 解法 それぞれの山についてGrundy数を求める。 約数を列挙する時に、までの約数aについて、対になる約数をで得ることで、に抑えるテクを使う。 すると 各について、setを使うことまで考慮するとGrundy数がで求まる。 全体で。なので、mはせいぜい500もなさそう。 実装 #include <bits/stdc+…

問題 Programming Problems and Competitions :: HackerRank n個のチップの山がある。 それぞれの山には個のチップがある。 2人のプレイヤーは、それぞれのターンで1個の山を選び、1つ以上のチップを取り除くか加えるかする。 ただし、各プレイヤーは、どんな山においてもK回以上の追加操作は出来ない。 先に操作の出来なくなったほうが負けである時、勝つのはどちらか。

問題 Programming Problems and Competitions :: HackerRank N個の箱がある。 それぞれの箱には個の石が入っている。 2人のプレイヤーは、それぞれのターンで石を1つだけ選んでより番号の小さい箱へ移動させる。 先に操作出来なくなったほうが負けである。 勝つのはどちらか。

問題 Programming Problems and Competitions :: HackerRank Nimゲームとほぼ同じだが、最後の石を取ったほうが負け(動かせなくなった方の勝ち)であるところが違う。

問題 Programming Problems and Competitions :: HackerRank 一般的なNimゲーム。

問題 Programming Problems and Competitions :: HackerRank 15*15マスの盤に1つの駒が置いてある。 駒が(x, y)にあるとすると、その駒は (x-2, y+1), (x-2, y-1), (x+1, y-2), (x-1, x-2) に移動できる。(図を参照) 2人のプレイヤーはそれぞれのターンで駒を1回移動させ、先に移動させられなくなった方の負け。 どちらが勝つか。

問題 Programming Problems and Competitions :: HackerRank 高さがMの山がN個ある。 2人のプレイヤーは、それぞれのターンで高さXの山を選び、その山の高さを、X未満のXの約数に変える。 先に操作できなくなった方が負け。 どちらが勝つか。

問題 Programming Problems and Competitions :: HackerRank N個の石を持つ山が1つだけある。 2人のプレイヤーは各ターンで2,3,または5個だけ石を取り除くことが出来、先に石を取れなくなった方の負け。 勝つのはどちらか。