9週目その他のアルゴリズム-5/5

5549惑星探査

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
k = int(input())
arr=[]
for i in range(n):
    arr.append(list(input()))
pp = [[[0,0,0] for i in range(m+1)] for j in range(n+1)] 
# 2차원 prefix sum 문제에서는 행, 열이 한 줄씩 더 필요함!! 
for i in range(n):
    for j in range(m):
        for l in range(3):
            pp[i+1][j+1][l] = pp[i+1][j][l] +pp[i][j+1][l]- pp[i][j][l]
        if arr[i][j]=='J':
            pp[i+1][j+1][0] += 1
        elif arr[i][j]=='O':
            pp[i+1][j+1][1] +=1
        elif arr[i][j]=='I':
            pp[i+1][j+1][2] += 1
for _ in range(k):
    a, b, c, d = map(int, input().split())
    answer = [0,0,0]
    for i in range(3):
        answer[i] = pp[c][d][i]-pp[a-1][d][i] - pp[c][b-1][i] + pp[a-1][b-1][i]
    print(answer[0], answer[1], answer[2])

に注意

for i in range(n):
    for j in range(m):
        planet[i][j+1] = planet[i][j] # 여기
        if arr[i][j]=='J':
            planet[i][j+1][0] = planet[i][j][0]+1
        elif arr[i][j]=='O':
            planet[i][j+1][1] = planet[i][j][1]+1
        elif arr[i][j]=='I':
            planet[i][j+1][2] = planet[i][j][2]+1
        print(planet)

コメントとしてマークされた場所を表示すると、アドレス値と値が変化すると元の配列も変化します.

に答える

まず、配列内のすべての要素を表示する必要があります.これは、数ビットO(KNM)の時間を消費し、タイムアウトを招きます.したがって,各行にprefix sumを格納して解く.理論的にはO(KN)の時間がかかりますがタイムアウトです.結局答えが見えた.

私たちが探している部分は4番で、すべて(1+3)+(1+2)-1を加えればいいです.dpだと思うかも?どうせ2 D接頭辞と問題を解くことができます.