yukicoder No. 1314 - N言っちゃダメゲーム (5)

ネタ被りが前日に発覚して (4) が (5) になるってどんな偶然なんですか？？

問題リンク

https://yukicoder.me/problems/no/1314#

問題概要

N言っちゃダメゲームをします。つまり、先手であるあなたは から始め、お互いに の整数を加算したものを言っていき、 以上の整数を言った人の負けです。
は今回 以上 の各整数を用います。先手の人は残っているものの中から好きなものを選び、その回の とします。一度使った数は以降使えなくなります。 回目以降のゲームは前回負けたプレイヤーが先手をします。

お互いに各ゲームではわざと負けたりしない条件のもと勝つ回数を最大化します。あなたが勝つか負けるか、引き分けになるかを求めてください。

制約

考察・解法

個先まで言える 言っちゃダメゲームにおいて、後手必勝である必要十分条件は です。よって、先手必勝のゲーム数を 、後手必勝のゲーム数を とすると、 です。

さて、後手が勝ちのゲームは選択権は自分にあるものの相手が勝ち続けてしまうので、基本的にどちらも避けたいものです。なので、どちらも押し付けあいになります。一方先手が勝つゲームは次のゲームは負けたほうに選択権が移ります。そのため、このゲームで最適にプレイすると、お互いに先手必勝のゲームでひたすら選択権の押し付けあいをし、後手必勝のゲームだけが残るとそのとき先手の人がずっと負け続ける状態になります。

よって、先手であるあなたの勝利数は です。

実装

実装を展開する

       public void Solve()
        {
            var (m, k) = cin.ReadValue<int, int>();
            m--;
            int lose = m / (k + 1);
            int win = m - lose;
            int first = (win + 1) / 2;
            if (win % 2 == 1) first += lose;
            if (first > m - first) Console.WriteLine("Win");
            else if (first == m - first) Console.WriteLine("Draw");
            else Console.WriteLine("Lose");
        }

ACコード: https://yukicoder.me/submissions/592227

感想

Writer も運営も意図せずしてN言っちゃダメゲームが被ったようですね。そんなことってあるんですね……。驚きです。