Problem:


Score : 700 points

Problem Statement

There are some coins in the xy-plane.
The positions of the coins are represented by a grid of characters with H rows and W columns.
If the character at the i-th row and j-th column, s_{ij}, is #, there is one coin at point (i,j); if that character is ., there is no coin at point (i,j). There are no other coins in the xy-plane.

There is no coin at point (x,y) where 1\leq i\leq H,1\leq j\leq W does not hold.
There is also no coin at point (x,y) where x or y (or both) is not an integer.
Additionally, two or more coins never exist at the same point.

Find the number of triples of different coins that satisfy the following condition:

Choosing any two of the three coins would result in the same Manhattan distance between the points where they exist.

Here, the Manhattan distance between points (x,y) and (x',y') is |x-x'|+|y-y'|.
Two triples are considered the same if the only difference between them is the order of the coins.

Constraints

1 \leq H,W \leq 300

s_{ij} is # or ..

Input

Input is given from Standard Input in the following format:

H W
s_{11}...s_{1W}
:
s_{H1}...s_{HW}

Output

Print the number of triples that satisfy the condition.

Sample Input 1

5 4
#.##
.##.
#...
..##
...#

Sample Output 1

3

((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)) and ((1,3),(3,1),(4,4)) satisfy the condition.

Sample Input 2

13 27
......#.........#.......#..
#############...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
#############.#.#.#...###..
#...........#...#...#######
#..#######..#...#...#.....#
#..#.....#..#...#...#.###.#
#..#######..#...#...#.#.#.#
#..........##...#...#.#####

Sample Output 2

870



Sample input:
5 4
#.##
.##.
#...
..##
...#


Sample output:
3

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
I = [input() for _ in range(H)]
X = [[[0, 1][a=="#"] for a in inp] for inp in I]
k = 21
def r():
    global H, W, I
    I = ["".join([I[H - 1 - j][i] for j in range(H)]) for i in range(W)]
    H, W = W, H
def st1(s):
    return int(s.replace("#", "1" * k).replace(".", "0" * k), 2)
def st2(s):
    return int(s.replace("#", "0" * (k - 1) + "1").replace(".", "0" * k), 2)
def getsum(x):
    for i in range(8):
        x += x >> (k << i)
    return x & ((1 << k) - 1)

ans = 0
for _ in range(4):
    A1 = [st1(inp) for inp in I]
    A2 = [st1("".join([I[i][j] for i in range(H)])) for j in range(W)]
    B = [st2(inp[::-1]) for i, inp in enumerate(I)]
    for j in range(W):
        s, t = 0, 0
        m = (1 << j * k) - 1
        for i in range(H)[::-1]:
            s = ((B[i] >> (j + 1) * k) + (s << k)) & m
            t += A1[i] >> (W - j) * k & A2[j] >> (H - i) * k & s
        ans += getsum(t)
    r()
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
I = [input() for _ in range(H)]
X = [[[0, 1][a=="#"] for a in inp] for inp in I]
k = 32
def r():
    global H, W, I
    I = ["".join([I[H - 1 - j][i] for j in range(H)]) for i in range(W)]
    H, W = W, H
def st1(s):
    return int(s.replace("#", "1" * k).replace(".", "0" * k), 2)
def st2(s):
    return int(s.replace("#", "0" * (k - 1) + "1").replace(".", "0" * k), 2)
def getsum(x):
    for i in range(8):
        x += x >> (k << i)
    return x & ((1 << k) - 1)

ans = 0
for _ in range(4):
    A1 = [st1(inp) for inp in I]
    A2 = [st1("".join([I[i][j] for i in range(H)])) for j in range(W)]
    B = [st2(inp[::-1]) for i, inp in enumerate(I)]
    C = [[0] * W for _ in range(H)]
    for j in range(W):
        s = 0
        m = (1 << j * k) - 1
        for i in range(H)[::-1]:
            s <<= k
            s += B[i] >> (j+1) * k
            s &= m
            C[i][j] = s
    for i in range(1, H):
        for j in range(1, W):
            ans += A1[i] >> (W - j) * k & A2[j] >> (H - i) * k & C[i][j]
    r()
            
print(getsum(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class CumulativeSum2D:
    def __init__(self, field):
        self.h = len(field)
        self.w = len(field[0])
        self.h_offset = self.h
        self.w_offset = self.w
        self.field = field
        self.cumsum = [[0] * (self.w + self.w_offset * 2) for _ in range(self.h_offset)]
        for line in self.field:
            self.cumsum.append([0] * self.w_offset + line + [0] * self.w_offset)
        for i in range(self.h_offset):
            self.cumsum.append([0] * (self.w + self.w_offset * 2))
    
    def calc_diagonal_cumsum(self):
        # Calc ul to dr
        for h in range(self.h_offset, self.h_offset + self.h):
            delta = 1
            while delta + h < self.h_offset * 2 + self.h and self.w_offset + delta < self.w_offset * 2 + self.w:
                self.cumsum[h + delta][self.w_offset + delta] += self.cumsum[h + delta-1][self.w_offset + delta-1]
                delta += 1
        for w in range(self.w_offset + 1, self.w_offset + self.w):
            delta = 1
            while delta + w < self.w_offset * 2 + self.w and self.h_offset + delta < self.h_offset * 2 + self.h:
                self.cumsum[self.h_offset + delta][w + delta] += self.cumsum[self.h_offset + delta - 1][w + delta - 1]
                delta += 1
    
    def get_diagonal_sum(self, x1, y1, x2, y2):
        ret = self.cumsum[y2 + self.h_offset][x2 + self.w_offset]
        ret -= self.cumsum[y1 - 1 + self.h_offset][x1 - 1 + self.w_offset]
        return ret

def rotate(field):
    h = len(field)
    w = len(field[0])
    h, w = w, h
    new_field = []
    for col in zip(*field):
        new_field.append(list(reversed(col)))
    return new_field

if __name__ == "__main__":
    n, m = [int(item) for item in input().split()]
    field = [[0] * m for _ in range(n)]
    for i in range(n):
        line = input().rstrip()
        for j in range(m):
            if line[j] == "#":
                field[i][j] = 1

    ans = 0
    for i in range(4):
        n = len(field)
        m = len(field[0])
        cs = CumulativeSum2D(field)
        cs.calc_diagonal_cumsum()
        lu_to_rd = [[] for _ in range(n + m - 1)]
        for i in range(m):
            x = i; y = 0
            delta = 0
            while x + delta < m and y + delta < n: 
                if field[y + delta][x + delta] == 1:
                    lu_to_rd[i].append((x + delta, y + delta))
                delta += 1
        for i in range(1, n):
            x = 0; y = i
            delta = 0
            while x + delta < m and y + delta < n:
                if field[y + delta][x + delta] == 1:
                    lu_to_rd[i + m - 1].append((x + delta, y + delta))
                delta += 1
        for line in lu_to_rd:
            length = len(line)
            if length <= 1:
                continue
            for i in range(length):
                for j in range(i+1, length):
                    x1, y1 = line[i]
                    x2, y2 = line[j]
                    d = abs(x1 - x2)
                    ans += cs.get_diagonal_sum(x1 + d + 1, y1 - d + 1, x2 + d, y2 - d)
        field = rotate(field)[:]
    print(ans)

Submission status: Accepted

Solution code:
import sys
b=sys.stdin.buffer
import numpy as np
H,W=map(int,b.readline().split());p=min(H,W)+1
S=np.pad((np.frombuffer(b.read(),dtype='S1')==b'#').reshape(H,-1)[:,:W].astype(int),(p,p),'constant')
a=0
for _ in[0]*4:
  d=S[p:,p:].copy()
  for n in range(H+p):d[n,:W]+=d[n-1,1:W+1]
  for n in range(p):a+=(S[1+p:H+1+p,1-n+p:W+1-n+p]*S[1-n+p:H+1-n+p,1+p:W+1+p]*(d[1+n:H+1+n,1:W+1]-d[1:H+1,1+n:W+1+n])).sum()
  S = S.T[::-1,:];H,W=W,H
print(a)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np
import itertools

H,W = map(int,readline().split())
S = (np.frombuffer(read(),dtype='S1')==b'#').reshape(H,-1)[:,:W].astype(np.int64)

# pad_width
p = min(H,W)+1

S = np.pad(S,(p,p),'constant')

def F(S,H,W):
    # L,Uに頂点があって、RDに第3の頂点がある場合。
    # Rは数えずDだけ数えておく
    cnt = 0
    diag = np.zeros((H+p,W+p),np.int64)
    diag[:H,:W] += S[p:-p,p:-p]
    for n in range(1,H+p):
        diag[n,:W] += diag[n-1,1:W+1]
    for n in range(1,p):
        cnt += (S[1+p:H+1+p,1-n+p:W+1-n+p] * S[1-n+p:H+1-n+p,1+p:W+1+p] * (diag[1+n:H+1+n,1:W+1]-diag[1:H+1,1+n:W+1+n])).sum()
    return cnt

x = []
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))
S = S.T[::-1,:] # 90度回転
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))

answer = sum(x)
print(answer)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[input() for i in range(H)]
table=[[0]*(H+W-1) for i in range(H+W-1)]
for j in range(H):
    for i in range(W):
        if S[j][i]=='#':
            table[i+j][i-j+H-1]=1
yoko=[[0]*(H+W) for i in range(H+W-1)]
for j in range(H+W-1):
    for i in range(1,H+W):
            yoko[j][i]=yoko[j][i-1]+table[j][i-1]
tate=[[0]*(H+W-1) for i in range(H+W)]
for j in range(1,H+W):
    for i in range(H+W-1):
        tate[j][i]=tate[j-1][i]+table[j-1][i]

ans=0
for y in range(H+W-1):
    for x in range((y+H-1)%2,H+W-1,2):
        if table[y][x]!=1:
            continue
        for z in range(x+2,H+W-1,2):
            if table[y][z]==1:
                d=z-x
                if y+d<H+W-1:
                    ans+=yoko[y+d][z+1]-yoko[y+d][x]
                    #print(1,'.',ans,':',x,y,z)
                if y-d>=0:
                    ans+=yoko[y-d][z+1]-yoko[y-d][x]
                    #print(2,'.',ans,':',x,y,z)
        for w in range(y+2,H+W-1,2):
            if table[w][x]==1:
                e=w-y
                if x+e<H+W-1:
                    ans+=tate[w][x+e]-tate[y+1][x+e]
                    #print(3,'.',ans,':',x,y,w)
                if x-e>=0:
                    ans+=tate[w][x-e]-tate[y+1][x-e]
                    #print(4,'.',ans,':',x,y,w)

print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
table=[[0]*(H+W-1) for i in range(H+W-1)]
for j in range(H):
    for i in range(W):
        if S[j][i]=='#':
            table[i+j][i-j+H-1]=1
yoko=[[0]*(H+W) for i in range(H+W-1)]
for j in range(H+W-1):
    for i in range(1,H+W):
            yoko[j][i]=yoko[j][i-1]+table[j][i-1]
tate=[[0]*(H+W-1) for i in range(H+W)]
for j in range(1,H+W):
    for i in range(H+W-1):
        tate[j][i]=tate[j-1][i]+table[j-1][i]

ans=0
for y in range(H+W-1):
    for x in range((y+H-1)%2,H+W-1,2):
        if table[y][x]!=1:
            continue
        for z in range(x+2,H+W-1,2):
            if table[y][z]==1:
                d=z-x
                if y+d<H+W-1:
                    ans+=yoko[y+d][z+1]-yoko[y+d][x]
                    #print(1,'.',ans,':',x,y,z)
                if y-d>=0:
                    ans+=yoko[y-d][z+1]-yoko[y-d][x]
                    #print(2,'.',ans,':',x,y,z)
        for w in range(y+2,H+W-1,2):
            if table[w][x]==1:
                e=w-y
                if x+e<H+W-1:
                    ans+=tate[w][x+e]-tate[y+1][x+e]
                    #print(3,'.',ans,':',x,y,w)
                if x-e>=0:
                    ans+=tate[w][x-e]-tate[y+1][x-e]
                    #print(4,'.',ans,':',x,y,w)

print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[input() for i in range(H)]
table=[[0]*(H+W-1) for i in range(H+W-1)]
for j in range(H):
    for i in range(W):
        table[i+j][i-j+H-1]=S[j][i]
yoko=[[0]*(H+W) for i in range(H+W-1)]
for j in range(H+W-1):
    for i in range(1,H+W):
        if table[j][i-1]=='#':
            yoko[j][i]=yoko[j][i-1]+1
        else:
            yoko[j][i]=yoko[j][i-1]
tate=[[0]*(H+W-1) for i in range(H+W)]
for j in range(1,H+W):
    for i in range(H+W-1):
        if table[j-1][i]=='#':
            tate[j][i]=tate[j-1][i]+1
        else:
            tate[j][i]=tate[j-1][i]

ans=0
for y in range(H+W-1):
    for x in range((y+H-1)%2,H+W-1,2):
        if table[y][x]!='#':
            continue
        for z in range(x+2,H+W-1,2):
            if table[y][z]=='#':
                d=z-x
                if y+d<H+W-1:
                    ans+=yoko[y+d][z+1]-yoko[y+d][x]
                    #print(1,'.',ans,':',x,y,z)
                if y-d>=0:
                    ans+=yoko[y-d][z+1]-yoko[y-d][x]
                    #print(2,'.',ans,':',x,y,z)
        for w in range(y+2,H+W-1,2):
            if table[w][x]=='#':
                e=w-y
                if x+e<H+W-1:
                    ans+=tate[w][x+e]-tate[y+1][x+e]
                    #print(3,'.',ans,':',x,y,w)
                if x-e>=0:
                    ans+=tate[w][x-e]-tate[y+1][x-e]
                    #print(4,'.',ans,':',x,y,w)

print(ans)

Submission status: Accepted

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

def solve():
    cums = [[0]*(H+W) for y in range(H+W-1)]
    coins = [[] for y in range(H+W-1)]
    for i in range(H):
        for j in range(W):
            if src[i][j] == '.': continue
            x,y = j-i+H, j+i
            cums[y][x] += 1
            coins[y].append(x)
    for i in range(H+W-1):
        for j in range(H+W-1):
            cums[i][j+1] += cums[i][j]
    cnt = 0
    for y1 in range(H+W-1):
        if len(coins[y1]) < 2: continue
        for i1 in range(len(coins[y1])-1):
            for i2 in range(i1+1,len(coins[y1])):
                x1,x2 = coins[y1][-1-i1], coins[y1][-1-i2]
                y2 = y1 - (x2 - x1)
                if y2 < 0: continue
                cnt += cums[y2][x2] - cums[y2][x1]
    return cnt

def rotate():
    global H,W,src
    H,W = W,H
    src2 = []
    for col in reversed(list(zip(*src))):
        src2.append(''.join(list(col)))
    src = src2

ans = 0
for i in range(4):
    rotate()
    ans += solve()
print(ans)

Submission status: Accepted

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

res = 0
# cross
cross_posi = [[0]*(H+W-1) for _ in range(H+W-1)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            cross_posi[i+j][i-j+W-1] = 1
            
# pre-compute
cross_posi_1 = [[0]*(H+W) for _ in range(H+W-1)]
for i in range(H+W-1):
    r = 0
    for j in range(H+W-1):
        r += cross_posi[i][j]
        cross_posi_1[i][j+1] = r
        
cross_posi_2 = [[0]*(H+W) for _ in range(H+W-1)]
for i in range(H+W-1):
    r = 0
    for j in range(H+W-1):
        r += cross_posi[j][i]
        cross_posi_2[i][j+1] = r

for s in range(H+W-1):
    for t in range((s+W+1)%2, H+W-2, 2):
        if cross_posi[s][t] == 1:
            for u in range(t+2, H+W-1, 2):
                if cross_posi[s][u] == 1:
                    d = (u - t)
                    if s >= d:
                        res += cross_posi_1[s-d][u+1] - cross_posi_1[s-d][t]
                    if s+d < H+W-1:
                        res += cross_posi_1[s+d][u+1] - cross_posi_1[s+d][t]
for s in range(H+W-1):
    for t in range((s+W+1)%2, H+W-2, 2):
        if cross_posi[t][s] == 1:
            for u in range(t+2, H+W-1, 2):
                if cross_posi[u][s] == 1:
                    d = (u - t)
                    if s >= d:
                        res += cross_posi_2[s-d][u] - cross_posi_2[s-d][t+1]
                    if s+d < H+W-1:
                        res += cross_posi_2[s+d][u] - cross_posi_2[s+d][t+1]
print(res)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

H, W = reads()
S = []
for _ in range(H):
  S.append(input())

N = H + W
field = [[0] * N for _ in range(N)]
for i in range(H):
  for j in range(W):
    field[i+j][i-j+W] = int(S[i][j] == '#')

accRow = [None] * N
for i in range(N):
  accRow[i] = [0] + list(accumulate(field[i][j] for j in range(N)))

accCol = [None] * N
for i in range(N):
  accCol[i] = [0] + list(accumulate(field[j][i] for j in range(N)))

# for f in field:
#   print(f)

ans = 0
for i in range(N):
  for j in range((i+W)%2, N, 2):
    for k in range(j+2, N, 2):
      d = k - j
      if field[i][j] == field[i][k] == 1:
        if i - d >= 0:
          ans += accRow[i-d][k+1] - accRow[i-d][j]
        if i + d < N:
          ans += accRow[i+d][k+1] - accRow[i+d][j]
      if field[j][i] == field[k][i] == 1:
        if i - d >= 0:
          ans += accCol[i-d][k] - accCol[i-d][j+1]
        if i + d < N:
          ans += accCol[i+d][k] - accCol[i+d][j+1]

print(ans)

Submission status: Runtime Error

Solution code:


def distance(a,b):
	return abs(a[0]-b[0])+abs(a[1]-b[1])


n=0

H,W=input().split()
r=[]
for i in range(H):
	r.append(input().split())
stones=[]
for i in range(H):
	for j in range(W):
		if(r[i][j]=="#"):
			stones.append([j,i])

for i in range(len(stones)):
	for j in range(i,(len(stones)):
		d=distance(stones[i],stones[j])
		for k in range(j,len(stones)):
			if(distance(stones[i],stones[k])==distance(stones[j],stones[k])==d):
				n+=1
print(n)

Submission status: Runtime Error

Solution code:


H,W = map(int,raw_input().split())

s = []
for i in range(H):
    s.append(map(int,raw_input().split()))

count=0
for i in range(H):
    for j in range(W):
        if s[i][j]=='#':
            k=1
            while i-k>=0 and i+k<=H-1 and j+k<=W-1:
                if s[i-k][j+k]=='#' and s[i+k][j+k]=="#":
                    count+=1
                k+=1
            k=1
            while i+k<=H-1 and j-k>=0 and j+k<=W-1:
                if s[i+k][j-k]=='#' and s[i+k][j+k]=="#":
                    count+=1
                k+=1


print count

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()] for i in range(H)]
def countRD(n, i, j):
    return ccc(n, i, j, 1, 1)
def countRU(n, i, j):
    return ccc(n, i, j, -1, 1)
def countLD(n, i, j):
    return ccc(n, i, j, 1, -1)
def countLU(n, i, j):
    return ccc(n, i, j, -1, -1)
def countR(n, i, j):
    return cc(n, i, j, 0, 1)
def countL(n, i, j):
    return cc(n, i, j, 0, -1)
def countD(n, i, j):
    return cc(n, i, j, 1, 0)
def countU(n, i, j):
    return cc(n, i, j, -1, 0)
def ccc(n, i, j, DU, RL):
    c = 0
    for k in range(1, n):
        if i+k*DU >= 0 and i+k*DU < H:
            if j+(n-k)*RL >= 0 and j+(n-k)*RL < W:
                c += X[i+k*DU][j+(n-k)*RL]
    return c
def cc(n, i, j, DU, RL):
    ret = 0
    if i+n*DU >= 0 and i+n*DU < H:
        if j+n*RL >= 0 and j+n*RL < W:
            ret = X[i+n*DU][j+n*RL]
    return ret

ans = 0
for i in range(H):
    for j in range(W):
        for n in range(1, min(max(i+j,H-i+W-j), max(i+W-j,H-i+J))+2):
            if countR(n, i, j) and countD(n, i, j):
                ans += countLU(n, i, j)
            if countR(n, i, j) and countU(n, i, j):
                ans += countLD(n, i, j)
            if countL(n, i, j) and countD(n, i, j):
                ans += countRU(n, i, j)
            if countL(n, i, j) and countU(n, i, j):
                ans += countRD(n, i, j)
            if countR(n, i, j) and countD(n, i, j) and countL(n, i, j):
                ans += 1
            if countR(n, i, j) and countD(n, i, j) and countU(n, i, j):
                ans += 1
            if countR(n, i, j) and countU(n, i, j) and countL(n, i, j):
                ans += 1
            if countD(n, i, j) and countU(n, i, j) and countL(n, i, j):
                ans += 1
            
            
print (ans)

Submission status: Runtime Error

Solution code:
H,W = map(int,raw_input().split())

s = []
for i in range(H):
    s.append(map(int,raw_input().split()))

count=0
for i in range(H):
    for j in range(W):
        if s[i][j]=='#':
            k=1
            while i-k>=0 and i+k<=H-1 and j+k<=W-1:
                if s[i-k][j+k]=='#' and s[i+k][j+k]=="#":
                    count+=1
print count