0w1

Game Theory

POJ 3537 Crosses and Crosses

Problem Description: Two players take turn in playing a game on a 1 x N board. When it is a player's turn, he puts a marker on a grid that had no marker. If after a movement there are 3 consecutive markers on the board, the player who made…

POJ 1740 A New Stone Game

Problem Description: There are N piles of stones, each with no more than 100 stones. Two players play this game, when it is one's turn, one should: Select a non-empty pile, remove at least one stone, then take arbitrary number of stones fr…

CFR 794 E. Choosing Carrot ( Game, Ad hoc )

Problem - 794E - Codeforces題意: 給長度 N 的數列 A[]。現在輪流玩遊戲,選擇一個端點的元素,讓它消失。當元素數量為 1 的時候遊戲立即結束。先手的目標是最大化最後一個元素,後手的目標是最小化最後一個元素。先手打算作弊,自己操作連續 K 輪後,當作…

HE Filler Game ( SG )

Filler Game | Dynamic Programming and Bit Masking & Algorithms Practice Problems | HackerEarth題意: 一個 N * M 的棋盤,一開始也許會有障礙物。輪流操作放置一個障礙物,一個格子可以放障礙物若且唯若它是空的,而且它有一個相鄰的格子是空的。問先…

Yuki 361 門松ゲーム2 ( SG, Game Theory )

No.361 門松ゲーム2 - yukicoder題意: 一開始有一個長度 L 單位的棒子。輪流操作,操作要選擇一個棒子,砍成三個不同長度的棒子,令這三個棒子的長度為 L1, L2, L3,則必須滿足: max( L1, L2, L3 ) - min( L1, L2, L3 ) ≤ D 先不能操作的人輸,問誰贏。制…

ARC 072 D - Alice&Brown ( Game Theory, SG )

D: Alice&Brown - AtCoder Regular Contest 072 | AtCoder題意: 兩堆石頭,數量 X, Y。輪流操作,一次選一個正整數的偶數 v,從一個至少有 v 個石頭的堆裡除去,並在另一堆上添加 v / 2 顆石頭。先不能操作的人輸。問雙方最佳操作下誰贏。制約: 0 ≤ X, Y ≤…

CFR 786 A. Berzerk ( DP, Game )

Problem - A - Codeforces題意: 有 n 個星球,從 0 開始編號,順時針排成一圈。0 號星球是黑洞。兩人有各自的操作集合,遊戲採取輪流操作,每次操作時選擇自己的集合裡的一個數字,將怪獸順時針推移該數字那麼遠。第一位把怪獸推移至 0 號星球的人獲得勝利…

CFR 389 E. Fox and Card Game ( Greedy, Game )

Problem - E - Codeforces題意: 有 N 個堆,第 i 個堆有 S[ i ] 個元素,每個元素都有權值 C[ i ][ j ] 。玩家 A 每次選一個堆,取最上面的元素,玩家 B 每次選一個堆,取最下面的元素。玩家 A 開始,並輪流操作。求雙方最大化自己的權值總和為前提,玩家 A…

Yuki 102 トランプを奪え ( Game Theory, SG Value )

No.102 トランプを奪え - yukicoder題意: 四種花色堆四疊,每疊張數 1 至 13 張,輪流操作玩一場遊戲。一次操作需選擇一疊,並抽走 1 至 3 張,納入自己的手牌。若取得了該疊最後一張,就能奪走對手的手牌,使對手手排只剩原本的一半,向下取整。張數多的贏…

ARC 064 D - An Ordinary Game ( Ad hoc, Game Theory )

D: An Ordinary Game - AtCoder Regular Contest 064 | AtCoder題意: 給一個字串,每次可選取非兩端的任意字元使其消失,但前提是消失後不能有任意兩個相鄰字元相同。兩個人輪流做,先不能做的輸,求誰贏。資料規模: 3 ≤ | S | ≤ 1e5解法: 考慮最終狀態的…

Yuki 374 コイン ( Game Theory )

No.374 コイン - yukicoder もし先手が置けたら中心に置き、後手がどう置けば先手はその対称する位置にもおく。すると先手は必ず勝つと示せる。 #include <bits/stdc++.h> using namespace std; const string msg[] = { "K", "S" }; signed main(){ unsigned int A, B; cin </bits/stdc++.h>…

CFR 455 B. A Lot of Games ( Game Theory + Trie )

Problem - 455B - Codeforces 題意: 玩連續 K 輪遊戲。每輪遊戲規則都一樣,初始時為空字串,輪流向字串結尾添加一個新的字元,操作後必須是字典中某個字的前綴。若無法進行合法的操作,則判為失敗。敗者為下一輪遊戲的先手。兩人採取最優策略爭奪第 K 輪的…

TIOJ 1092 跳格子遊戲 ( DP + Game theory )

1092 - A.跳格子遊戲 | TIOJ INFOR Online Judge 看網上大家都是寫拓撲排序逆著遞推,我覺得沒必要。另外我換了一下題意,因為事實上第一個動作的是初期的後手,所以我調換一下,這樣比較容易思考。邊界是當目前這個節點沒有可移動的,就代表前一個人已經勝…

ABC 27 C - 倍々ゲーム ( Game theory, Adhoc )

C: 倍々ゲーム - AtCoder Beginner Contest 027 | AtCoder abc027 from AtCoder Inc. www.slideshare.net ちょっと面白かった。説明はスライドの図を見た方がわかりやすい。こういったアプローチは幾つか選択肢木を描いて考察した方がでやすいですね。 #incl…

Range Mex

Mex ( minimum excludant ), has an interesting property in game theory, where an sprague grundy value of a state in a fair game can be deduced from the mex of the sg-values of all the states it could reach in the next step.The definition of…