公式
C - Snuke the Cookie Picker 解説 by Nyaan
まず、素直な方針として、次のアルゴリズムがまず考えられる解法だと思います。
- \(1 \leq a \lt b \leq H, 1 \leq c \lt d \leq W\) を満たす範囲の整数の組 \((a,b,c,d)\) について, 次の条件を満たすかを判定する。
- \((a, b)\) を左上, \((c, d)\) を右下とする長方形領域内部の
.
の個数を調べる。 .
がちょうど 1 個だった場合、そのマスがすぬけ君がクッキーを取ったマスになる。
- \((a, b)\) を左上, \((c, d)\) を右下とする長方形領域内部の
しかしこのアルゴリズムは 6 乗の for-loop を必要とするため時間計算量が \(\mathrm{O}(H^3 W^3)\) となり非常に遅いです。どうにか高速化する方法を考えましょう。
重要な気づきとして、次の事実があります。
- \(U\) を(クッキーが置かれている行の番号の最小値) とする。このとき、すぬけ君がクッキーを食べる前と食べた後で、\(U\) の値は変わらない。
(証明) 部分長方形は縦横ともに 2 マス以上の大きさがあります。よって、すぬけ君がクッキーを食べる前の時点で最上段のクッキーは 2 個以上あります。すぬけ君はクッキーを 1 個しか食べないので、すぬけ君がクッキーを食べた後も最上段のクッキーは 1 個以上残っています。よって \(U\) の値もまた変わりません。(証明終わり)
同様の考え方で、次の 3 つの値もクッキーを食べる前と食べた後で変わらないことが分かります。
- \(D :=\) (クッキーが置かれている行の番号の最大値)
- \(L :=\) (クッキーが置かれている列の番号の最小値)
- \(R :=\) (クッキーが置かれている列の番号の最大値)
よって、次のような方針のアルゴリズムでこの問題を解くことができます。
- \(U, D, L, R\) を求める。これは全てのマスについて全探索すれば計算できる。
- \((U, L)\) を左上、\((D, R)\) を右下とする部分長方形の範囲で
.
になっているマスが答えである。
時間計算量は \(\mathrm{O}(HW)\) で、AC するのに十分高速です。
- 実装例(C++)
#include <algorithm>
#include <iostream>
using namespace std;
int H, W, U = 1e9, D = -1e9, L = 1e9, R = -1e9;
char S[502][502];
int main() {
cin >> H >> W;
for (int i = 0; i < H; i++) cin >> S[i];
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (S[i][j] == '#') {
U = min(U, i), D = max(D, i);
L = min(L, j), R = max(R, j);
}
}
}
for (int i = U; i <= D; i++) {
for (int j = L; j <= R; j++) {
if (S[i][j] == '.') cout << i + 1 << " " << j + 1 << endl;
}
}
}
投稿日時:
最終更新: