結果
問題 |
No.402 最も海から遠い場所
|
ユーザー |
|
提出日時 | 2024-09-09 18:48:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,222 ms / 3,000 ms |
コード長 | 1,025 bytes |
コンパイル時間 | 410 ms |
コンパイル使用メモリ | 82,772 KB |
実行使用メモリ | 150,824 KB |
最終ジャッジ日時 | 2024-09-09 18:48:57 |
合計ジャッジ時間 | 7,363 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
""" 解法 答えで二分探索する。 答えが m 以上であるためには、(2 * m + 1) × (2 * m + 1) の正方形領域が全て # であるものが存在することが必要十分条件となる ここで、二次元累積和で正方形領域の # の個数を O(1) で求めることができるようにしておくと、判定は O(HW) でできる。 計算量は O(HW log(min(H, W))) """ H, W = map(int, input().split()) S = [input() for _ in range(H)] A = [[0] * (W + 1) for _ in range(H + 1)] for i in range(H): for j in range(W): if S[i][j] == '#': A[i + 1][j + 1] += 1 for i in range(H + 1): for j in range(W): A[i][j + 1] += A[i][j] for i in range(H): for j in range(W + 1): A[i + 1][j] += A[i][j] le = 0 ri = (min(H, W) + 1) // 2 while le + 1 < ri: mi = (le + ri) // 2 k = 2 * mi + 1 ok = False for i in range(H + 1 - k): for j in range(W + 1 - k): if A[i + k][j + k] - A[i][j + k] - A[i + k][j] + A[i][j] == k * k: ok = True if ok: le = mi else: ri = mi print(ri)