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) で間に合うはずもなく...。