Zenn
✨

LeetCoding Challenge Oct. 25: Stone Game IV

2020/10/25に公開
Java
LeetCode
tech

LeetCode October Challenge の 25 日目。

今日の問題は Stone Game IV。

問題の概要

  • 次のルールに基づくゲームを先手・後手ともに最善手でプレイするとして、与えられた n の場合に先手が勝利できるかどうかを判定する
  • ルール
    • 初期状態として、n 個の石が存在する
    • 先手・後手ともに、1 以上 n 以下の任意の平方数の個数だけ石を取り除くことができる
    • 最後に石を取り除く操作をした方が勝利する

考え方

  • まずは問題をコーディング可能な形に落とし込む必要がありますね… 🤔
  • 「与えられた n で先手が必ず勝利できる」のは、いかのいずれかを満たす場合になるかな？
    • n が平方数そのものであること
    • n より「n 未満の平方数」を減じた数のいずれかに、後手が必ず負ける「数」が存在すること
  • おおっと、これは動的計画法を使って解く問題かな？
    • 1 から n までのすべての数値 (ループ変数 i) について順に、その値からゲームを開始した場合の先手の勝利・敗北をテーブルに記録していく
    • i が平方数なら、先手が勝利する
    • i が平方数ではない場合は、i - 1^2, i - 2^2, i - 3^2 ... のいずれかの数から負けにつながる数の有無を探索する
      • 負ける数が 1 つでもある場合にのみ、i は先手が勝利しうる
  • このアルゴリズムの空間計算量は O(n), 時間計算量は O(n * sqrt(n)) かな？
  • このまま実装してもいいけど、Solution#winnerSquareGame() のメソッドが呼び出される度に同じ計算が生じうるのが嫌だなあ
    • ちょっと卑怯な手段ではあるけど、計算結果のテーブルはクラス変数で保持しておこう
  • 実装して submit → 一発 accept 🤗
    • Runtime 28ms で Your runtime beats 54.63 % of java submissions. は遅いですね 🥺
  • これはちょっとアルゴリズムを考え直した方がよさそう
  • n は最大 100,000 (10^5) ということだけど、1 から 100,000 までの n を実際に与えて先手が勝利・敗北に至る回数を数えてみるとそれぞれ 97,219 vs 2,781 ということだそうだ
    • 先手が敗北する数値はわりとレアではあるのね
  • であれば、敗北する数値に着目することで runtime を削ることができるのでは？
    • 敗北する数値に平方数を足したものは必ず先手の勝利になるよね 💪
    • そういうわけで、敗北する数値が見つかったらその数値に平方数を足し合わせた数値が先手の勝利になることを事前計算するようにしてみよう
  • submit → accept した結果をみると、runtime は 5ms!
    • Your runtime beats 94.21 % of java submissions. ということで、随分と速くなったね 😊
  • これ以上は速くできなかったので諦めて他の上位陣のサンプルコードを見てみたが、なんと深さ優先の再帰探索でも十分速くできるのか…
    • DFS
  • そして最速 2ms のコードをみてみたが、これは僕の「負け」に着目する実装とほぼ同じだけどクラス変数は使っていないのね…
    • BitSet 使う実装で同様に記述してみたが 11ms になって速くならない一方で、ナイーブに boolean[] にしたほうが速くなる、と… 🤦‍♂️

コード

当初のコード

class Solution {
    static BitSet cache = new BitSet();
    static int count = 1;
    static int nextSqNum = 4;
    static int sqrtNum = 3;

    static {
        cache.set(0);
    }

    public boolean winnerSquareGame(int n) {
        for (int i = count + 1; i <= n; i++) {
            int bi = i - 1;
            if (i == nextSqNum) {
                nextSqNum = sqrtNum * sqrtNum;
                sqrtNum++;
                cache.set(bi, true);
                continue;
            }

            for (int j = 1, sq; (sq = j * j) < i; j++) {
                if (!cache.get(bi - sq)) {
                    cache.set(bi, true);
                    break;
                }
            }
        }

        if (count < n) {
            count = n;
        }

        return cache.get(n - 1);
    }
}

敗北する数に着目した実装

class Solution {
    static final int MAX = 100000;
    static BitSet cache = new BitSet(MAX);
    static int count = 1;

    static {
        for (int i = 1, sq; (sq = i * i) <= MAX; i++) {
            cache.set(sq - 1);
        }
    }

    public boolean winnerSquareGame(int n) {
        for (int i = count; i < n; i++) {
            if (cache.get(i)) {
                continue;
            }

            for (int j = 1, sq; i + (sq = j * j) <= MAX; j++) {
                cache.set(i + sq);
            }
        }

        if (count < n) {
            count = n;
        }

        return cache.get(n - 1);
    }
}

Discussion