Mujin Programming Challenge 2018-C：うほょじご(400)

問題

https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_d

rev(x) := x を 10 進表記してできる文字列を反転したものを 10 進表記に持つ整数を表す。
正の整数 N, M について 1 <= x <= N, 1 <= y <= M なる (x, y) について、以下の操作が無限に繰り返すことができるものの個数を求めよ。

操作

  1. x, y のいずれかが 0 であれば終了する。
  2. x < y ならば x = rev(x)、そうでなければ y = rev(y) で置き換える。
  3. 2 の操作後、 x < y となっていれば、 y = y - x そうでなければ x = x - y で置き換える。

制約

1 <= N, M <= 999

考え方

まず制約として x, y は [1, 999] であるから rev(x) をとったときの値の範囲も [1, 999] におさまる。ある点についての遷移について考えよう。ある点 (i, j) からの遷移を考えたときに遷移する方向は1通りに決まる。またある点 (i, j) が (0, x) or (x, 0) で終了するとき、その過程で通過した点についても同様に (0, x) or (x, 0) で終了する。よって一度訪れた(ないしは通過した)点については O(1) で操作が終了するかしないかを求めることができる。(0, x) or (x, 0) で終了しない場合は、遷移する過程で一度訪れた点に再度遷移していることになる。

よってこれはメモ化再帰をすることで解くことができる。

       boolean[][] visited, memo;
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt(), m = in.nextInt();
            visited = new boolean[1000][1000];
            memo = new boolean[1000][1000];

            long ans = 0;
            for (int x = 1; x <= n; x++) {
                for (int y = 1; y <= m; y++) {
                    if (memo[x][y] = rec(x, y)) {
                        ans++;
                    }
                }
            }

            out.println(n * m - ans);
        }

        boolean rec(int x, int y) {
            if (x == 0 || y == 0) {
                return memo[x][y] = true;
            }

            if (visited[x][y]) {
                return memo[x][y];
            }

            visited[x][y] = true;

            if (x < y) {
                x = rev(x);
            } else {
                y = rev(y);
            }

            if (x < y) {
                y = y - x;
            } else {
                x = x - y;
            }
            return memo[x][y] = rec(x, y);

        }

        int rev(int k) {

            char[] sk = String.valueOf(k).toCharArray();
            int len = sk.length;
            int ret = 0;
            for (int i = len-1, j = 0; i >= 0; i--, j++) {
                ret += (int)(sk[i]-'0') * Math.pow(10, len-1-j);
            }

            return ret;
        }

ポイント

  • 取りうる変数の状態を考える
  • 遷移を考える

類題

雑記

本番中は愚直にシミュレーシュンした後に、メモ化を考えるのみであった...。一度訪問した点については再度調べる必要がないことに気づければよかった。