[Python] ABC008 D

問題

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点の配列の中を見ると使われていないところがたくさんあります。

以下を参考にしました。

http://mayokoex.hatenablog.com/entry/2016/03/17/123712