白駿-16235木材財テク

木材財テク問題リンク
問題の説明
樹木は毎年以下の過程を経る時、K年後の活樹の数を求める.
四季

春:自分の年齢で養分を食べ、年齢を1歳増やす
一室にいくつもあり、幼木から養分をいただきます
養分が足りなければ、いっそ養分を食べないで、すぐに死んでしまう.

夏:春に死んだ木が養分になる(木の年齢/2)

秋:年齢5倍の樹木が隣接する8マスのうち、年齢1の繁殖

冬季:A[r][c]と同じ養分を1室ずつ添加

条件

1 ≤ N ≤ 10

1 ≤ M ≤ N2

1 ≤ K ≤ 1,000

1 ≤ A[r][c] ≤ 100

1≦与えられた木の年齢≦10を入力

入力されたツリーの位置が異なる

一間に複数の木がある場所

最初は1室あたり5等量の養分があった

に答える
問題のように、春、夏、秋、冬を実現していますが、タイムアウトします.
初めての試み
結果

コード#コード#

import sys
read = sys.stdin.readline


# 나무가 번식할 수 있는 위치를 구하기 위한 배열
drdc = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]

# N: 땅의 크기, M: 나무의 수, K: 연도 수
N, M, K = map(int, read().split())
land = [[5] * N for _ in range(N)]

# A: 겨울에 추가할 양분
A = [list(map(int, read().strip().split())) for _ in range(N)]
trees = []
for _ in range(M):
    # x,y: 나무의 위치, z: 나무의 나이
    x, y, z = map(int, read().split())
    trees.append([z, x - 1, y - 1])
# 나무의 나무가 적은 순서로 정렬한다
trees.sort()

for _ in range(K):  # K년만큼 반복
    # 봄
    dead_trees = []
    for index in range(len(trees)):  # 나무별로 반복
        age, r, c = trees[index]

        if land[r][c] < age:  # 양분이 부족하면
            dead_trees.append((index, age // 2, r, c))
        else:  # 양분이 충분하면
            land[r][c] -= age
            trees[index][0] += 1

    # 여름
    # 뒤의 인덱스부터 제거해주어야 한다
    for i in range(len(dead_trees) - 1, 0 - 1, -1):
        index, value, r, c = dead_trees[i]
        land[r][c] += value
        del trees[index]

    # 가을
    new_trees = []
    for age, r, c in trees:
        if age < 5 or age % 5 != 0:
            continue

        for dr, dc in drdc:
            dr, dc = r + dr, c + dc
            if 0 <= dr < N and 0 <= dc < N:
                new_trees.append([1, dr, dc])
    trees.extend(new_trees)
    trees.sort()

    # 겨울
    for r in range(N):
        for c in range(N):
            land[r][c] += A[r][c]

print(len(trees))

2回目の試み
アイデア
四季を问わず、一度にできる仕事をしばってしまった.
木の年齢昇順ソートを前提として,次のような操作を行った.

--- 각 위치별로 반복 시작 ---
is_lack - True: 양분 부족, False: 양분 부족하지 않음
  False: 한 위치에서 나이가 어린 순으로 양분을 먹고, 나이 1 증가
         나이가 5의 배수라면 breed_trees에 추가
  True: add_val += 나이 // 2
land[r][c] += add_val + A[r][c]
--- 각 위치별로 반복 종료 ---
breed_trees 번식

結果

ただし、pypyのみが通過します.
コード#コード#

from collections import defaultdict
import sys
read = sys.stdin.readline


def do(r, c):
    is_lack = False  # 현재 위치 양분 부족 여부
    add_val = 0  # 현재 위치에서 죽은 나무가 양분이 되어 더할 수
    new_trees = []  # 이번 작업이 끝난 뒤 (r, c) 에 위치한 나무들

    trees[(r, c)].sort()  # 나이 오름차순으로 정렬

    for age in trees[(r, c)]:
        if land[r][c] < age:
            is_lack = True

        if is_lack:  # 현재 위치의 양분이 부족하다면
            add_val += age // 2
        else:  # 양분이 부족하지 않다면
            land[r][c] -= age

            age += 1
            new_trees.append(age)
            if age % 5 == 0:
                breed_trees.append((r, c))

    trees[(r, c)] = new_trees

    return add_val


# 나무가 번식할 수 있는 위치를 구하기 위한 배열
drdc = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]

# N: 땅의 크기, M: 나무의 수, K: 연도 수
N, M, K = map(int, read().split())
land = [[5] * N for _ in range(N)]


# A: 겨울에 추가할 양분
A = [list(map(int, read().strip().split())) for _ in range(N)]
trees = defaultdict(list)
for _ in range(M):
    # x,y: 나무의 위치, z: 나무의 나이
    x, y, z = map(int, read().split())
    trees[(x - 1, y - 1)].append(z)


for _ in range(K):
    # 각 위치별로 반복
    breed_trees = []  # 번식할 나무들
    for r in range(N):
        for c in range(N):
            add_val = 0
            if (r, c) in trees:
                add_val = do(r, c)
            land[r][c] += add_val + A[r][c]
            if not trees[(r, c)]:
                del trees[(r, c)]

    # 나무 번식
    for r, c in breed_trees:
        for dr, dc in drdc:
            dr, dc = r + dr, c + dc
            if 0 <= dr < N and 0 <= dc < N:
                trees[(dr, dc)].append(1)

print(sum(map(len, trees.values())))

3回目の試み
アイデア
結果
コード#コード#