問題
D – 金塊ゲーム
回答
80点回答 分割統治法 再帰
分割された区域に再帰的に関数を適用することで問題を解きます。
def rec_get_golds(x_min, y_min, x_max, y_max):
'''
ある区域が与えられるとその中で取得できる最大の金の数を返す。
'''
max_amounts_gold = 0
for x, y in pos_cranes:
# クレーンが区域内にない場合
if (x < x_min or x_max < x) or (y< y_min or y_max < y):
continue
# (x, y)のクレーンを使うと、金塊が回収されるとともに、区域が4分割される。
# 分割された区域に対して、再帰的に関数を適用する。
amounts_gold = (x_max - x_min + 1) + (y_max - y_min + 1) - 1 \
+ rec_get_golds(x+1, y+1, x_max, y_max) \
+ rec_get_golds(x_min, y+1, x-1, y_max) \
+ rec_get_golds(x_min, y_min, x-1, y-1) \
+ rec_get_golds(x+1, y_min, x_max, y-1) \
max_amounts_gold = max(amounts_gold, max_amounts_gold)
return max_amounts_gold
W, H = map(int, input().split())
N = int(input())
pos_cranes = [list(map(int, input().split())) for _ in range(N)]
print(rec_get_golds(1, 1, W, H))
99点回答 メモ化再帰
メモ化再帰を使い、時間計算量を減らします。
が、今度は空間計算量の問題が発生します。
def rec_get_golds(x_min, y_min, x_max, y_max):
'''
ある区域が与えられるとその中で取得できる最大の金の数を返す。
'''
max_amounts_gold = 0
# メモ化再帰
if (x_min > x_max) or (y_min > y_max):
return 0
if dp[x_min-1][y_min-1][x_max-1][y_max-1] != -1:
return dp[x_min-1][y_min-1][x_max-1][y_max-1]
for x, y in pos_cranes:
# クレーンが区域内にない場合
if (x < x_min or x_max < x) or (y< y_min or y_max < y):
continue
# (x, y)のクレーンを使うと、金塊が回収されるとともに、区域が4分割される。
# 分割された区域に対して、再帰的に関数を適用する。
amounts_gold = (x_max - x_min + 1) + (y_max - y_min + 1) - 1 \
+ rec_get_golds(x+1, y+1, x_max, y_max) \
+ rec_get_golds(x_min, y+1, x-1, y_max) \
+ rec_get_golds(x_min, y_min, x-1, y-1) \
+ rec_get_golds(x+1, y_min, x_max, y-1) \
max_amounts_gold = max(amounts_gold, max_amounts_gold)
dp[x_min-1][y_min-1][x_max-1][y_max-1] = max_amounts_gold
return max_amounts_gold
W, H = map(int, input().split())
N = int(input())
pos_cranes = [list(map(int, input().split())) for _ in range(N)]
# メモ化再帰用の配列を準備
dp = [[[[-1] * H for _ in range(W)] for _ in range(H)] for _ in range(W)]
print(rec_get_golds(1, 1, W, H))
100点 @functools.lru_cache(user_function)
Python標準ライブラリで用意されているメモ化再帰のための@functools.lru_cache(user_function) を maxsize を適当な値に設定して使うと、100点になります。
from functools import lru_cache
@lru_cache(maxsize=2**20)
def rec_get_golds(x_min, y_min, x_max, y_max):
'''
ある区域が与えられるとその中で取得できる最大の金の数を返す。
'''
max_amounts_gold = 0
for x, y in pos_cranes:
# クレーンが区域内にない場合
if (x < x_min or x_max < x) or (y< y_min or y_max < y):
continue
# (x, y)のクレーンを使うと、金塊が回収されるとともに、区域が4分割される。
# 分割された区域に対して、再帰的に関数を適用する。
amounts_gold = (x_max - x_min + 1) + (y_max - y_min + 1) - 1 \
+ rec_get_golds(x+1, y+1, x_max, y_max) \
+ rec_get_golds(x_min, y+1, x-1, y_max) \
+ rec_get_golds(x_min, y_min, x-1, y-1) \
+ rec_get_golds(x+1, y_min, x_max, y-1) \
max_amounts_gold = max(amounts_gold, max_amounts_gold)
return max_amounts_gold
W, H = map(int, input().split())
N = int(input())
pos_cranes = [list(map(int, input().split())) for _ in range(N)]
print(rec_get_golds(1, 1, W, H))
100点 配列ではなくハッシュを使う
メモ化再帰のために配列ではなく、辞書を用いることでメモリを節約します。
def rec_get_golds(x_min, y_min, x_max, y_max):
'''
ある区域が与えられるとその中で取得できる最大の金の数を返す。
'''
max_amounts_gold = 0
# メモ化再帰
if (x_min > x_max) or (y_min > y_max):
return 0
# if dp[x_min-1][y_min-1][x_max-1][y_max-1] != -1:
# return dp[x_min-1][y_min-1][x_max-1][y_max-1]
# 辞書を使うことでメモリを節約
key = (x_min, y_min, x_max, y_max)
if key in memo:
return memo[key]
memo[key] = 0
for x, y in pos_cranes:
# クレーンが区域内にない場合
if (x < x_min or x_max < x) or (y< y_min or y_max < y):
continue
# (x, y)のクレーンを使うと、金塊が回収されるとともに、区域が4分割される。
# 分割された区域に対して、再帰的に関数を適用する。
amounts_gold = (x_max - x_min + 1) + (y_max - y_min + 1) - 1 \
+ rec_get_golds(x+1, y+1, x_max, y_max) \
+ rec_get_golds(x_min, y+1, x-1, y_max) \
+ rec_get_golds(x_min, y_min, x-1, y-1) \
+ rec_get_golds(x+1, y_min, x_max, y-1) \
max_amounts_gold = max(amounts_gold, max_amounts_gold)
memo[key] = max_amounts_gold
return max_amounts_gold
W, H = map(int, input().split())
N = int(input())
pos_cranes = [list(map(int, input().split())) for _ in range(N)]
# # メモ化再帰用の配列を準備
# dp = [[[[-1] * H for _ in range(W)] for _ in range(H)] for _ in range(W)]
# メモ化再帰用の辞書を準備
memo = {}
print(rec_get_golds(1, 1, W, H))
座標圧縮
解説のスライドにテクニックとして載っている方法です。
99点の配列の中を見ると使われていないところがたくさんあります。
以下を参考にしました。