Problem:

B: Hokkaido University Hard

注意

　問題設定は A 問題と同一のものですが、制約のみが異なりますのでご注意ください。

物語

　北海道大学に合格し、新たな生活の始まりに心を躍らせるほむらちゃん。しかし彼女の前には、とてつもなく広いキャンパスが待ち受けていた...。

　「え...次の授業に間に合わないんだけど...」

問題

　北海道大学札幌キャンパスは異常に広いことで有名です。札幌キャンパスは縦に H マス、横に W マス並んだ長方形のマス目で表現されます。北から i マス、西から j マス進んだマスを (i,j) で表すことにします。キャンパス内にはいくつか建物があり、マス  (i,j) で表される位置に建物がある場合は 'B' 、ない場合は '.' が c_{i,j} に書かれています。

　北海道大学の新入生のほむらちゃんは、キャンパスのあまりの広さに驚愕し、建物間の移動が心配になってきました。そこで、建物のある 2 つのマスのうち、最も遠い組はどれくらい離れているのかが気になりました。ここで、2 つのマスの組 (i,j) , (i',j') の間の距離を |i-i'|+|j-j'| と定義します。

　ほむらちゃんは、自分にはこの問題は難しいと思い、同級生のあなたに助けを求めてきました。ほむらちゃんの代わりに答えを求めてください。

入力形式

H W
c_{11}c_{12} ... c_{1W}
:
c_{H1}c_{H2} ... c_{HW}

制約

 2 \leq H,W \leq 10^3

 H,W は整数

 c_{i,j} は 'B' か '.' のいずれかである。

 c_{i,j} のうち少なくとも 2 つは 'B' である。

出力形式

答えを表す整数を 1 行に出力せよ。

入力例 1

3 3
B.B
..B
.BB

出力例 1

4

(1,1) と (3,3) の 2 点間が最長です。

入力例 2

4 3
B..
B..
...
...

出力例 2

1

隣り合う位置が最長になる場合もあります。

入力例 3

6 6
...B..
B.B.B.
.B.B.B
...B.B
.B..B.
..B...

出力例 3

7



Sample input:
3 3
B.B
..B
.BB


Sample output:
4

Submission status: Accepted

Solution code:
# from sys import exit, stderr
# from inspect import currentframe
# def debug(*args):
#     names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
#     print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args), file=stderr)
#     return
INF = 10e10
H, W = [int(n) for n in input().split()]
c = [["" for __ in range(W)] for _ in range(H)]
B = set()
for i in range(H):
    c[i] = list(str(input()))
    for j in range(W):
        if c[i][j] == "B":
            B.add((i,j))


a = 0
b = INF
c = 0
d = INF
for e in B:
    a = max(e[0] + e[1],a)
    b = min(e[0] + e[1],b)
    c = max(e[0] - e[1],c)
    d = min(e[0] - e[1],d)
print(max(a-b, c-d))

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
s = []
for k in range(H):
    s.append(input())
m1 = float("inf")
M1 = 0
m2 = float("inf")
M2 = 0
for k in range(H):
    for l in range(W):
        if s[k][l] == "B":
            m1 = min(m1,k+l)
            M1 = max(M1,k+l)
            m2 = min(m2,W-1-l+k)
            M2 = max(M2,W-1-l+k)
print(max(M1-m1,M2-m2))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    h,w = LI()
    s = SR(h)
    ans = 1
    for y in range(h):
        for x in range(w):
            if s[y][x] == "B":
                for y_ in range(h):
                    for x_ in range(w):
                        if s[y_][x_] == "B":
                            ans = max(ans, abs(y-y_)+abs(x-x_))
    print(ans)
    return

#B
def B():

    def quickhull(l,r,s,k,il,ir):
        if not s:
            return
        su = []
        sd = []
        a = (r[0]-l[0],r[1]-l[1])
        for x,y in s:
            b = (x-l[0],y-l[1])
            cro = cross(a,b)
            if cro > 0:
                su.append((x,y)) #上半分
            elif cro < 0:
                sd.append((x,y)) #下半分

        ind = (ir-il)/2 #凸包に追加する頂点が反時計回りで何番目かを表す基数

        if su:
            c,d = direction(l,r,su[0])
            p = su[0]
            for i in range(1,len(su)):
                c_,d_ = direction(l,r,su[i])
                if c*d_ < c_*d:
                    c,d = c_,d_
                    p = su[i]
            i = ir+ind #irよりも後
            k.append((tuple(p),i)) #もっとも離れた点を凸包の頂点に追加
            b = (l[0]-p[0],l[1]-p[1])
            c = (p[0]-r[0],p[1]-r[1])
            s1 = []
            s2 = []
            for x,y in su:
                b_ = (x-p[0],y-p[1])
                c_ = (x-r[0],y-r[1])
                cro_b,cro_c = cross(b,b_),cross(c,c_)
                if cro_b >= 0 and cro_c >= 0: #三角形内部判定
                    continue
                else:
                    if cro_b < 0:
                        s1.append((x,y))
                    elif cro_c < 0:
                        s2.append((x,y))
            quickhull(l,p,s1,k,il,i) #再帰
            quickhull(r,p,s2,k,ir,i) #順序がr->pの点に注意して再帰

        if sd:
            c,d = direction(l,r,sd[0])
            p = sd[0]
            for i in range(1,len(sd)):
                c_,d_ = direction(l,r,sd[i])
                if c*d_ < c_*d:
                    c,d = c_,d_
                    p = sd[i]
            i = il+ind
            k.append((tuple(p),i)) #もっとも離れた点を凸包の頂点に追加
            b = (l[0]-p[0],l[1]-p[1])
            c = (p[0]-r[0],p[1]-r[1])
            s1 = []
            s2 = []
            for x,y in sd:
                b_ = (x-p[0],y-p[1])
                c_ = (x-r[0],y-r[1])
                cro_b,cro_c = cross(b,b_),cross(c,c_)
                if cro_b <= 0 and cro_c <= 0: #三角形内部判定(ベクトルの向きにより上下で判定が異なることに注意)
                    continue
                else:
                    if cro_b > 0:
                        s1.append((x,y))
                    elif cro_c > 0:
                        s2.append((x,y))
            quickhull(l,p,s1,k,il,i) #再帰
            quickhull(p,r,s2,k,i,ir) #順序がp->rの点に注意して再帰
        k.sort(key = lambda x:x[1])
        return tuple(zip(*k))[0]

    def cross(a,b): #外積
        return a[0]*b[1]-a[1]*b[0]

    def direction(l,r,p): #点と直線の距離
        a = r[1]-l[1]
        b = l[0]-r[0]
        return (a*(p[0]-l[0])+b*(p[1]-l[1]))**2, a**2+b**2 #分子の2乗,分母の2乗

    def manh(x,y):
        return abs(x[0]-y[0])+abs(x[1]-y[1])
    h,w = LI()
    c = SR(h)
    s = []
    for y in range(h):
        for x in range(w):
            if c[y][x] == "B":
                s.append([x,y])
    n = len(s)
    if n < 1000:
        ans = 1
        for x in s:
            for y in s:
                ans = max(ans,manh(x,y))
        print(ans)
    else:
        s.sort()
        l = tuple(s.pop(0))
        r = tuple(s.pop(-1))
        k = quickhull(l,r,s,[(l,0),(r,n)],0,n)
        ans = 1
        for x in k:
            for y in k:
                ans = max(ans,manh(x,y))
        print(ans)
    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

#H
def H():
    n = I()

    return

#I
def I_():
    n = I()

    return

#J
def J():
    n = I()

    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
# from sys import exit
H, W = [int(n) for n in input().split()]
c = [[0 for _ in range(W)] for __ in range(H)]
Bs = []

for i in range(H):
    c[i] = list(str(input()))
    for j in range(W):
        if c[i][j] == "B":
            Bs.append((i, j))

INF = 10e10
a, c = -INF, -INF
b, d = INF, INF
for e in Bs:
    a = max(e[0] - e[1], a)
    b = min(e[0] - e[1], b)
    c = max(e[0] + e[1], c)
    d = min(e[0] + e[1], d)
print(max(a-b, c-d))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



H,W = map(int, input().split())
builds = []
for h in range(H):
  l = str(input())
  for w in range(W):
    if l[w] == "B":
      builds.append([h,w])

# [min,max]
lu = [H+W,0]
ld = [H+W,0]
for h,w in builds:
  lu = [min(lu[0],h+w),max(lu[1],h+w)]
  ld = [min(ld[0],H-h+w),max(ld[1],H-h+w)]
print(max(lu[1]-lu[0],ld[1]-ld[0]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
# gcd
from fractions import gcd
# 切り上げ，切り捨て
from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
from collections import Counter
import math
from functools import reduce
sys.setrecursionlimit(200000)
# input関係の定義
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
# template

H, W = mi()
S = [li() for i in range(H)]
ans = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "B":
            ans.append((i, j))
        
ans.sort(key=lambda x: x[0] + x[1])
debug(ans[-1])
debug(ans[0])
tmp = abs(ans[-1][0] - ans[0][0]) + abs(ans[-1][1] - ans[0][1])
ans.sort(key=lambda x: x[0] + (W - x[1]))
debug(ans[-1])
debug(ans[0])
tmp2 = abs(ans[-1][0] - ans[0][0]) + abs(ans[-1][1] - ans[0][1])
print(max(tmp,tmp2))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
MAP=[list(input()) for i in range(H)]

BLIST=[]

for i in range(H):
    for j in range(W):
        if MAP[i][j]=="B":
            BLIST.append([i,j])

BLIST.sort(key=lambda x:x[0]+x[1])
ANS=abs(BLIST[0][0]-BLIST[-1][0])+abs(BLIST[0][1]-BLIST[-1][1])

BLIST.sort(key=lambda x:x[0]-x[1])
ANS=max(ANS,abs(BLIST[0][0]-BLIST[-1][0])+abs(BLIST[0][1]-BLIST[-1][1]))

print(ANS)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

H, W = inpl()
ans = 0

C = [input() for _ in range(H)]
for i in range(2):
    L = [0]*H
    R = [0]*H
    Lk = []
    Rk = []
    for h in range(H):
        L[h] = C[h].find("B")
        R[h] = C[h].rfind("B")
        if L[h] >= 0:
            Lk.append(h)
        if R[h] >= 0:
            Rk.append(h)
    
    for lh in Lk:
        for rh in Rk:
            ans = max(ans, abs(L[lh] - R[rh]) + abs(lh - rh))

    if i == 0:
        C = ["".join(c) for c in zip(*C)]
        H, W = W, H

print(ans)