HackerRank Game Theory 解いてみた

(575)

個人ブログの下書きに眠っていた記事の供養です。
！！！Day3までしかないです！！！

HackerRank Game Theory とは？

www.hackerrank.com

HackerRankにおける、ゲーム理論の典型問題を集めたコンテスト。コンテスト自体は終わっているが、提出してジャッジすることはできる。
元々5日間のコンテストで、問題名には「Day1〜Day5」と書いてある。
というわけで、実際に5日間で各Dayの問題を解いてみることにした。

Day1

そんなに難しくないです。

Game of Stones

2人の人がN個の石でゲームをする。交互に{2,3,5}個取っていく。先に取れなくなったほうが負け。
勝つのは？

解法

愚直にDPをする。
dp[i]:i個残っている時に先手必勝なら1、そうでないなら0 と定義する。
dp[0]=0
dp[i]=0(dp[i-2]=dp[i-3]=dp[i-5]=1のとき),1(それ以外)
として計算できる。dp[N]=1なら先手の勝ち、0なら後手の勝ち。
なぜこれで良いかというと、遷移先に1しかないなら後手必勝は明らかで、0が存在する場合、そこに遷移することで、石が0 or 遷移先が1しかない状態 のどちらかにできるから。

Tower Breakers

2人の人が、N個のタワーでゲームをする。最初、全てのタワーの高さはMである。交互にタワーを1つ選び、「その時点での選んだタワーの高さのある約数」まで減らす。ただし、高さ0にはできない。先に減らせなくなったら負け。
勝つのは？

解法

これは、Nimに帰着できる。
タワーの高さを素因数分解して、(タワーの高さ)=p_1^a_1+p_2^a_2+... と表せるとする(p_iは素数)。
このとき、タワーの高さを減らす操作は、a_1,a_2,... からいくつか選んでいくつか減らすという操作に相当する。
よって、a_1+a_2+... に注目すると、この値を負にならない限り自由に減らせて、操作によって素因数が増えることもないので、これはNim。
Nimの条件から、(a_1+a_2+...)をN回xorした値が0ならば後手の勝ち、そうでないなら先手の勝ち。
・M=1のとき そもそも1度も操作できないので、後手必勝。
・M>=2のとき (a_1+a_2+...)>=1 より、Nが奇数なら先手の勝ち、偶数なら後手の勝ち。
単純な条件に落とし込めたので、Nimを考えなくても解けそう。

A Chessboard Game

2人の人が、15*15のチェス盤でゲームをする。
初期位置が与えられ、そこにコインが置かれる。2人は、(x,y)にあるコインを(x-2,y+1),(x-2,y-1),(x+1,y-2),(x-1,y-2)のどれかに動かせる。先に動かせなくなった方が負け。
勝つのは？

解法

移動可能なマスに辺を張った有向グラフを考えると、これはDAGになる。
図を眺めると、(x+y)の昇順に見ていくことで、トポロジカル順序の逆順にDPできることが分かる。
dp[i][j]:(i,j)にいるときに先手必勝なら1、そうでないなら0 と定義する。
dp[1][1]=dp[2][1]=dp[2][2]=dp[1][2]=0
dp[i][j]=0(dp[i-2][j+1]=dp[i-2][j-1]=dp[i+1][j-2]=dp[i-1][j-2]=1のとき)、1(それ以外)
という遷移で、(i+j)の昇順に計算していくことができる。
あとはdp[x][y]の値で(x,y)に置いた時の勝ち負けが分かる。

Day2

問題名から分かるように、Nimのオンパレードだった。Day1より少し難しい。

Nim Game

2人の人がN個の石の山でゲームをする。i番目の山にはs_i個の石がある。交互に山を1つ選び、好きな個数(>=1)だけ石を減らす。先に減らせなくなった方が負け。
勝つのは？

解法

Nim。石の数のxor(=Xとする)が0なら後手の勝ち、そうでないなら先手の勝ち。
なぜこれでいいかというと、
・最終状態(負け)ではX=0
・X>0のとき、「Xで立っている最上位のbit」が立っているような山が存在するので、そこを選ぶと、X=0になるように減らすことが必ず可能
・X=0のとき、どんな操作をしてもX>0になる。
から。

Misère Nim

Nim Gameの、先に減らせなくなった方が勝つバージョンを解け。

解法

わからん。

Nimble Game

2人の人が、1列に並んだN個の四角とその上に置かれたコインでゲームをする。左からi番目の四角にはc_i個置いてある。交互にコインを1つ選び、そこより左の四角に動かす。動かせるコインがない(=全てが最も左にある)なら負け。
勝つのは？

解法

Nimに帰着できる。各コインが山、置いてある場所が石の数を表していると考えればよい。
全部xorしていると間に合わないので、同じ数を偶数回xorすると0になることを使う。

Poker Nim

2人の人が、c_i個のチップの乗ったN個の山でゲームをする。交互にある山を選び、「1つ以上の好きな個数のチップだけ取り除く」「1つ以上の好きな個数のチップだけ加える」を繰り返す。最後のチップを取った方が勝ち。
なお、1人につき加える操作はk回までしかできない。
勝つのは？

解法

実は、勝利条件はNimと全く同じ。なぜなら、石の数のxorをXとして、
・最終状態ではX=0
・X>0なら、必ずX=0になるように減らせるので、増やす操作をする必要がない
・X=0なら、どこを増やしても減らしてもX>0になる
からである。

Tower Breakers,Revisited!

Day1のTower Breakersの、各タワーの初期高さが同じとは限らない場合を解け。

解法

Day1の方での考察がそのまま使える。
各高さを素因数分解すれば(a_1+a_2+...)が求まるので、後はNim。

Day 3

Grundy数の性質を問う問題たち。かなり勉強になった。

Tower Breakers,Again!

2人の人が、高さが同じとは限らないN個のタワーでゲームをする。交互にあるタワー(高さXとする)と、あるXの約数Yを選び、タワーをX/Y個の高さYのタワーに分割する。
勝つのは？

解法

タワーが1つの場合のGrundy数が求まれば、後は全てのタワーのGrundy数をxorすることで全体のGrundy数が求まる。
タワーが1つの場合も、dp[i]:高さiのタワー1つのGrundy数 とすれば、遷移先の約数を全列挙することで前計算することができる。
このように、いくつかのゲームを並列でやる時の全体のGrundy数がそれぞれのGrundy数のxorで表せるということは、Grundy数の求め方を考えると示せる。

Chessboard Game,Again!

Day1のChessboard Gameの、コインがk枚ある場合を解け。

解法

各コインが独立なので、それぞれが1枚だけ置いてあった場合のGrundy数を求め、xorすれば、それが今の盤面のGrundy数となる。
Day1のバージョンを少し変え、Grundy数の定義に従ってDPすればよい。

Digits Square Board

2人の人がN*Nのマス目の乗った正方形でゲームをする。最初は、マス目には1~9のいずれかが書いてある。
交互に、「合成数が1つ以上含まれる、面積が2以上の長方形」を1つ選び、直線で切って2つの長方形に分割する。先に選べなくなった方が負け。
勝つのは？

解法

各部分長方形について、Grundy数を順に計算していく。
書いてある数が全て素数なら、Grundy数は0。そうでないなら割れるので、全ての切り方を調べ、分けた先の2つのGrundy数のxorが0であるものが存在するなら1。

おわりに

誰かDay4とDay5解いて記事書いて

答辞＿テンプレート(1)

こんにちは。𠮷川健雄です。

自己開示をします。

 

好きなもの10選

・手の指

理由→これがあるのでいろいろできて、便利

 

ニュートラル10選

・足の指

理由→わけのわからない、形

 

令和3年12月11日　卒業生代表 𠮷川健雄

 

「金栗四三」と「かなぐり捨てる」ってなんか似ていませんか？

こんにちは。ケンタです。

 

なぜなんでしょうか、私は今日、ふと思いました。

「金栗四三」と「かなぐり捨てる」ってなんか似ているな～

と。

 

みなさんにも同意していただけるのかな。どうなんだろう。

でもなんか似ていると思ってしまったんですよね。

 

不思議ですよね。文字数も違うというのに。

 

でも、一体何がそういう気持ちにさせているのでしょうか。

私は少し考えてみました。すると一つのアイデアが舞い降りてきました。

 

ひょっとすると使われてる音が似ているのでは？

 

どうでしょうか。少し確認してみましょう。

 

金栗四三　→　かなくりしそう（かなぐりしぞう）

かなぐり捨てる　→かなぐりすてる

 

これはまさか………

ビンゴです！！！！！

 

なんとなんと！予想通り使われている音が似ていました！

特に最初の4文字です。

位置も同じということで、これは驚きです。

 

このように日常に潜む小さな気付きも深く考えてみると、

その裏にはとても興味深い事実が隠されているのですね。

 

日本語って難しい！！！

ブログ開設にあたって

これは理ロシのブログらしいです。

 

というわけで、文系中国語クラスの人がいまこれを書いています。

 

圧をかけられたので私は悪くありません。

 

今回は、理ロシの名前を冠して大学への愚痴を言っていこうと思います。

 

理ロシってなあに？

理ロシはとにかく気持ちが悪いです。どれくらい気持ちが悪いと思いますか？

①　牛乳が腐ったようなにおいがする

②　豆乳が腐ったようなにおいがする

③　足が細い

いかがでしたか？結局理ロシとは何かはわかりませんでした。

しかし、理ロシはいまも活動を続けているようです。

あなたの後ろにも理ロシがいるかもしれません。

 

理ロシ以外ってなあに？

理ロシ以外ってなんでしょう。

さて、ところで、ここで考えてみましょう。

 

明日は私たちが何かをするかもしれません。しないかもしれません。

した方がいいでしょうか？

 

野原しんのすけが適しているCMと適していないCMを考える

本題に入りましょう。

最近テレビを見るとCMがあらゆるところにあふれています。

野原しんのすけも例外ではありません。

ドラえもんを見ているときに流れてくるCMをご存じですか？

「クリクラのおいしい水を飲もうよ」というキャッチコピーで野原家が踊りながらクリクラの水を紹介するCMがあります。そして、「チョコビ」のCMもあります。

 

これは本当に野原しんのすけがするべきCMなのでしょうか？

まず、チョコビについてはわかります。というのも、チョコビとはクレヨンしんちゃんのアニメ内でしんのすけが好んで食べている商品であるからです。しかし、クリクラやレオパレスと野原しんのすけに何の関係があるのでしょうか？いや、ない。

 

つまり、野原しんのすけは大体のCMに適している可能性があるわけです。

そうなれば、逆張りの私たちが考えることはただ一つ。

 

野原しんのすけが適していないCMってなんだろう？

 

当然の疑問でしょう。

ここからはこの疑問に答えていきたいと思います。

 

さいごに

いかがでしたか？

結局野原しんのすけが適しているCMはわかりませんでした。

これからも理ロシのブログをよろしくお願いします。

非理ロシ一同