ゆるふわオンサイト#5-G Exponential Banana Game

writerしました。

www.hackerrank.com

以下ネタバレや解説の記事になるので、自力で解きたい人はご注意！

改行

はてなで改行たくさんいれるのどうするんだ

改行

改

行

改行

こんなもんでいいか

裏話

writerしたとはいえ、ネタはほぼてんぷらさんの助言です

Grundy数やるだけだったゲーム問題を原案置き場に雑に置いといたのですが、

🍤「これGrundy数が0,1,2しかとらないことを利用して変なことできそう」

🦍「変なこと　なに！？」

🍤「先手がゲームに勝てるようにゲーム開始前にバナナをこっそり食べてしまう食べ方何通りありますか、とか」

🦍「うおおお」

というやりとりがあり、ごりちゃん作問してません。

こうやって問題って作るんだなと勉強になりました。

複数人で作問するとこういう貴重な経験ができるので楽しいです
ありがとうございます。

FO社に入ってゆるふわオンサイトの作問してくれる方募集中です。

裏話2

1ターンに $B_i^j$ 本食べる設定にした理由はすごく雑で、Grundy数求めるときの遷移をlog回にしてシミュレーションを間に合わせようとしてたのでした
美しい性質があったとは知らずに...

裏話3

ちなみに

久しぶりに、ゴリラのゴリ太郎君とウホ次郎君はゲームで対決します！

と書いたのですが、これ何が久しぶりなのか伝わってない気しかしないです
(これが伝わった人がいたらかなりのごりちゃんファンだ...)

ゴリ太郎君とウホ次郎君は以前ゆるふわ#2 で対決していたのでした
こっちのほうがゲーム問題としてはとっつきやすいですのでぜひ
www.hackerrank.com

解説

さて、解説なのですが
ここにスライドがあるじゃろ

ざっくりはこれを見てくださいなんですけど
現地解説用に作ったスライドなのでどうしてGrundy数がこのような値をとるのか？の証明的なものは書けてなかったです
ので書きます
コンテスト中は実験された方が多いのではないでしょうか
(証明もてんぷらさんが考えてくれたんですが難しかったのでかみ砕いています　間違いありましたらご指摘ください)

以下、現在のバナナの本数を $x$ とします
バナナの本数が $n$ のときの Grundy数を $g(n)$ とします

$B_i$ が奇数のとき

$B_i^j$ は必ず奇数なので、バナナの数の偶奇は1回の操作で必ず反転します。
$g(0) = 0$ なので、 $g(x) =x\mod 2$ がそのままGrundy数になります。

$B_i$ が偶数のとき

のとき
- $j = 0$ しか選べないので、必ずバナナを1本ずつしか減らせず、 $g(x) = x\mod 2$ となります。
のとき
- $j = 0$ または $j = 1$ が選べます。食べれるバナナは $1$ 本または $B_i$ 本です。これらの行動をしたときの Grundy数は $g(x-1) = 1, g(x-B_i) = g(0) = 0$ となり、これらの mexを取ると $2$ になります。
のとき
- です
  - $B_i^{2n} - 1$ が必ず $B_i + 1$ で割り切れるんですね　すごい
- 同様に、 $x - B_i \equiv x - B_i^3 \equiv x - B_i^5 \equiv \ldots \pmod{B+1}$ です
- つまり、すべての操作について、操作の結果残るバナナの本数を mod (B+1) で考えると、 $x - 1$ または $x - B_i$ となります
- これらをもとに数学的帰納法を適用することができます。
  - $n \gt B_i$ となる $n$ に対して、Grundy数は $g(n) = mex(g(n-1), g(n-B_i))$ により求まる
  - これを適用するとGrundy数の列は実際に $(0,1,0,1,0,1, \ldots, 2)$ の繰り返しになることを確かめられる

結局、証明というか、キミの目で確かめてくれ！みたいになってしまった

writerコード

grundy_count() を O(1) で算出するところの実装がつらめでした
こういうのうまく書けるようになりたい
a以上b以下のときの何かの個数を求めたいときに f(b) - f(a-1) みたいにするのはやるやるですね

'''
想定解概要：
  ゲームの勝敗はgrundy数で求まる。
  grundy数の取り得る値が少ないことから、grundy数の値を持ってdpができる。
  grundy数はB_iが奇数のとき、
    0,1,0,1,0,1,0,1, ... となり、
  grundy数はB_iが偶数のとき
    (0,1,0,1,...,2), (0,1,0,1,...,2), ... となる (B_i + 1 周期)
'''

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

MOD = 998244353

# B_i = b の部屋で、バナナto本以下でゲームを開始したときのgrundy数が gとなるパターン数
def _grundy_count(b, g, to):
    if to < 0: return 0
    if b%2:
        if g==0:
            return (to+2)//2
        elif g==1:
            return (to+1)//2
    else:
        if g==2:
            return (to+1)//(b+1)
        elif g==0 or g==1:
            d,m = divmod(to, b+1)
            ret = d*b//2
            if m < b:
                if g==0:
                    ret += (m+2)//2
                else:
                    ret += (m+1)//2
            else:
                ret += b//2
            return ret
    return 0

# B_i = b の部屋で、バナナfr本以上to本以下でゲームを開始したときのgrundy数が gとなるパターン数
def grundy_count(b, g, fr, to):
    return (_grundy_count(b, g, to) - _grundy_count(b, g, fr-1)) % MOD

# dp[i] = これまでのgrundy数を累積した結果がiとなるパターンの数
dp = [1,0,0,0]
for a,b in zip(A,B):
    ndp = [0,0,0,0]
    for i in range(4):
        for g in range(3):
            ndp[i^g] += grundy_count(b, g, a-M, a) * dp[i]
    for i in range(4):
        ndp[i] %= MOD
    dp = ndp

print(sum(dp[1:]) % MOD)