Ускорение кода Python с помощью NumPy

Question

Всем привет! Очень медленно работает программа с этими 4 циклами. Можно ли как-то ускорить ее используя модуль NumPy? (1 ≤ N,M,D ≤ 1000) (1 ≤ A ≤ N, 1 ≤ B ≤ M). В игре «Heroes of Wizardry and Sorcery» игровой мир представляет собой таблицу N × M с квадратными полями, длина сторон которых равна 1. Поля обозначаются (i,j), где i — номер строки, а j — номер столбца. Каждому полю соответствует магическая защита Di,j.

Ваш замок находится на поле (A,B). Вы можете построить защитную ограду в форме прямоугольника, стороны которого проходят по линиям таблицы, при этом замок должен находиться внутри ограды. Пусть верхнее левое поле забора (p,q), правое нижнее (r,s), а длина забора равна l. Тогда защитная сила забора равна Dp,q + Dr,s + l.

Требуется построить забор с максимальной защитной силой.

Система оценки Всего в задаче 20 тестов (не считая примеров). Каждый тест оценивается в 10 баллов.

В 15% тестов N, M ≤ 50, в 25% тестов Di,j ≤ 50, в 35% тестов N, M ≤ 400.

Пояснения к примерам В первом тесте из примера наиболее выгодно выбрать (p, q) и (r, s) равные (1, 1) и (3, 3), тогда получим защитную силу забора 8 + 7 + 12 = 27.

Во втором примере можно выбрать левое верхнее поле забора совпадающим с правым нижним, а именно поле замка (2, 1), тогда защитная сила забора будет равна 9 + 9 + 4 = 22

В третьем примере хочется по аналогии со вторым взять поле со значением 50, чтобы получить защитную силу забора 50 + 50 + 4 = 104, однако, в таком случае замок окажется снаружи, что противоречит условию, соответственно, наибольшая возможная защитная сила забора будет 1 + 50 + 6 = 57.


n, m, a, b = map(int, input().split())
arr = [list(map(int, input().split())) for t in range(n)]
res = 0
for i in range(a):
    for j in range(b):
        for i2 in range(a - 1,n):
            for j2 in range(b - 1, m):
                L = np.multiply(2,(np.add(np.subtract(i2, i), 1))) + np.multiply(2,(np.add(np.subtract(j2,j),1)))
                D = arr[i][j] + arr[i2][j2] + L
                res = max(res, D)

print(res)

Answer 1

Сложность этого полного перебора - O(N^2*M^2), что для размеров 1000 даёт 10^12 циклов, время неприемлемое.

Однако задачу можно решить за O(NM).

Пройдём по матрице, добавляя к каждому D[i][j] из правого нижнего сегмента удвоенную сумму индексов Fij=2*(i+j), и отнимая соответствующую величину для левого верхнего сегмента. Заметим, что добавки выглядят так:

0  2* 4  6
2  4  6  8
4  6  8  10
6  8  10 12*

И их разность для двух ячеек как раз равна периметру прямоугольника (длине забора). Например, для помеченных 12-2=10 = 2*3+2*2

При проходе по матрице просто запоминаем максимальные значения Dij-Fij и Dij+Fij соответственно левее-выше и правее-ниже поля A, B, и лучший результат - сумма этих максимумов плюс 4 (т.к. у вас от точки 1,1 до точки 3,3 периметр считается 12, а не 8).

Примерно так:

maxl, maxr = -3000, -1
for i in range(a):
    for j in range(b):
        maxl = max(maxl, arr[i][j] - 2 * (i + j))

for i in range(a-1, n):
    for j in range(b-1, m):
        maxr = max(maxr, arr[i][j] + 2 * (i + j))

print(maxl + maxr + 4)

БЛОГ НА HUSL

Ускорение кода Python с помощью NumPy

Ответы (1 шт):