Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

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…