Mujin Programming Challenge 2018-C:右折(400)

問題

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

N 行 M 列のマス目がある。(i, j) は '.' or '#' である。あるマスに上下左右のいずれかの方向を向いたロボットをおく。ロボットは直進し、あるマスで右折した後直進することができる。ロボットが置かれた位置と停止した位置の順序対の個数を求めよ。

考え方

すべての組み合わせの中で右折するポイントが位置 (i, j) になる組み合わせを考える。すると (i, j) で右折する組み合わせは、

(i, j) から上方向に直進することのできるマスの数 * (i, j) から左方向に直進することのできるマスの数
(i, j) から左方向に直進することのできるマスの数 * (i, j) から下方向に直進することのできるマスの数
(i, j) から下方向に直進することのできるマスの数 * (i, j) から右方向に直進することのできるマスの数
(i, j) から右方向に直進することのできるマスの数 * (i, j) から上方向に直進することのできるマスの数

の和であることがわかる。よって事前計算で各マス (i, j) について全探索し、上下左右に直進できるマスの数をかけ合わせれば良い。上下左右に直進できるマスの数は事前計算しておくことで O(1) で取得できるため、全体の計算量としては O(NM) となる。
事前計算については、DPっぽい要領で、各マス (i, j) を見たときに隣接するマスと着目している (i, j) のマスが '#', '.' であるかによって O(1) で求められる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt(), m = in.nextInt();
            char[][] s = new char[n][m];
            for (int i = 0; i < n; i++) {
                s[i] = in.nextString().toCharArray();
            }

            int[][] u = new int[n][m];
            int[][] d = new int[n][m];
            int[][] l = new int[n][m];
            int[][] r = new int[n][m];

            // 上
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (s[i-1][j] != '#' && s[i][j] == '.') {
                        u[i][j] = u[i-1][j] + 1;
                    }
                }
            }

            // 下
            for (int i = n-2; i >= 0; i--) {
                for (int j = 0; j < m; j++) {
                    if (s[i+1][j] != '#' && s[i][j] == '.') {
                        d[i][j] = d[i+1][j] + 1;
                    }
                }
            }

            // 左
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < m; j++) {
                    if (s[i][j-1] != '#' && s[i][j] == '.') {
                        l[i][j] = l[i][j-1] + 1;
                    }
                }
            }

            // 右
            for (int i = 0; i < n; i++) {
                for (int j = m-2; j >= 0; j--) {
                    if (s[i][j+1] != '#' && s[i][j] == '.') {
                        r[i][j] = r[i][j+1] + 1;
                    }
                }
            }

            long ans = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (s[i][j] == '.') {
                        ans += (u[i][j] + d[i][j]) * (l[i][j] + r[i][j]);
                    }
                }
            }

            out.println(ans);
        }

ポイント

  • 三点選択は真ん中に着目する。

類題

雑記

本番中は (i, j) と (i, j) の組み合わせを考えて、その対に動くことが可能かどうかを O(1) で求める方針で考えてしまった。単純に考えても計算量が O(n4) で間に合うはずもなく...。