SRM 701 Div 2 Hard : ThueMorseGame

TopCoder Statistics - Problem Statement

通せなくてめちゃくちゃ悔しい。

当初の解法

DPだなって思ってしまった。

  public class ThueMorseGame {
    boolean[][] dp;
    boolean[][] done;
    int n;
    int m;

    public String get(int n, int m) {
      this.n = n;
      this.m = m;
      dp = new boolean[n + 1][2];
      done = new boolean[n + 1][2];
      return dfs(n, 0) ? "Alice" : "Bob";
    }

    boolean dfs(int remain, int turn) {
      if (done[remain][turn]) {
        return dp[remain][turn];
      }
      if (isLose(remain)) {
        done[remain][turn] = true;
        dp[remain][turn] = true;
        return dp[remain][turn];
      }
      if (remain <= m) {
        done[remain][turn] = true;
        dp[remain][turn] = true;
        return dp[remain][turn];
      }
      boolean flag = false;
      for (int i = m; 1 <= i; --i) {
        int nr = remain - i;
        flag |= dfs(nr, 1 - turn);
      }
      done[remain][turn] = true;
      dp[remain][turn] = flag;
      return dp[remain][turn];
    }

    boolean isLose(int num) {
      int cnt = 0;
      while (num > 0) {
        if (num % 2 == 1) {
          ++cnt;
        }
        num /= 2;
      }
      return cnt % 2 == 1;
    }
  }

このあとメモリー使いすぎ問題のため、
byteにしてビットで管理するも、
そもそも遷移にO(m)かかっているので、
O(mn)でダメになる。

解法を見て

https://apps.topcoder.com/wiki/display/tc/SRM+701

ビット演算？？？　意味分からね～～～

となってけど、読み砕いてみる。

まず上記のソースについて、その数字が勝てる数字なのか
どうかしか着目しなくていいので、[2]がいらない。
あと、これをfor文のDPに書き直す。

    public String get(int n, int m) {
      boolean[] dp = new boolean[n + 1];
      for (int i = 1; i <= n; ++i) {
        if (i <= m) {
          dp[i] = true;
        } else if (isLose(i)) {
          dp[i] = true;
        } else {
          boolean flag = false;
          for (int j = 1; j <= m; ++j) {
            int nr = i - j;
            flag |= dp[nr];
          }
          dp[i] = flag;
        }
      }
      return dp[n] ? "Alice" : "Bob";
    }

O(m)の遷移が大変邪魔なので、
これをbitで管理する。

    public String get(int n, int m) {
      boolean[] dp = new boolean[n + 1];
      long bits = 0;
      for (int i = 1; i <= n; ++i) {
        if (i <= m) {
          dp[i] = true;
        } else if (isLose(i)) {
          dp[i] = true;
        } else {
          boolean flag = ((~bits) & full) > 0 ;
          dp[i] = flag;
        }
        bits = (bits << 1L) | (dp[i] ? 1L : 0L);
      }
      return dp[n] ? "Alice" : "Bob";
    }

ビットを反転させているのは、
その数を取ったら相手が勝つ遷移というのに
行かないようにするため。
相手が負ける遷移が勝ち。

そもそもdpテーブルがいらないことに
気づく。
あと、isLose関数が遅かった（なぜ？）
ので、Integer.bitCountを利用する。

  public class ThueMorseGame {
    public String get(int n, int m) {
      long bits = 0;
      long full = (1L << m) - 1L;
      for (int i = 1; i <= n; ++i) {
        long win = 0;
        if (i <= m) {
          win = 1;
        } else if (isLose(i)) {
          win = 1;
        } else {
          win = ((~bits) & full) > 0 ? 1 : 0;
        }
        bits = (bits << 1L) | win;
      }
      return (bits & 1) == 1 ? "Alice" : "Bob";
    }

    boolean isLose(int num) {
      return Integer.bitCount(num) % 2 == 1;
    }
  }

それでもだいぶ遅いんですが・・・。
でもこれでSystem Testに通ることができた。