🐕

Codejam2022 Round1B: Controlled Inflation

2022/05/08に公開

Python

問題

N人の顧客が持っているP個の製品に空気を入れる。各製品の空気圧に合わせるために、空気入れ装置のボタン押し下げを行う場合、全製品に空気入れを行うための押し下げ操作の最少回数は幾つになるか？ただし、顧客の順番入れ替えはNGだが、各顧客の製品並び替えはOK。また装置の初期値は０。

アルゴリズム

各顧客に対しては、昇順に入れるか、もしくは降順に入れると、最も少ない操作回数で行えそう。ただし、i+1番目の顧客に遷移するときに、i番目の顧客の最後の値との差分によっては昇順または降順のどちらが最少になるかは変わるので、昇順で遷移する場合、降順で遷移する場合をメモしながら、最終的にN番目まで終わった時に少ない方を解とする。

実装

$dp_{i,0}$ をi番目を昇順で処理した時の操作回数、 $dp_{i,1}$ をi番目を降順で処理したときの操作回数として、動的計画法の考え方で実装する。
$dp_{i+1,0}$ は、以下のいずれかの最小値として更新。

$dp_{i,0}$ に、i番目の最後の値（i番目の最大値）とi+1番目の最初の値（i+1番目の最小値）との差分、i+1番目の中での操作回数を加えたもの
$dp_{i,1}$ に、i番目の最後の値（i番目の最小値）とi+1番目の最初の値（i+1番目の最小値）との差分、i+1番目の中での操作回数を加えたもの

同じように、 $dp_{i+1,1}$ は、以下のいずれかの最小値として更新。

$dp_{i,0}$ に、i番目の最後の値（i番目の最大値）とi+1番目の最初の値（i+1番目の最大値）との差分、i+1番目の中での操作回数（最大値と最小値の差分）を加えたもの
$dp_{i,1}$ に、i番目の最後の値（i番目の最小値）とi+1番目の最初の値（i+1番目の最大値）との差分、i+1番目の中での操作回数を加えたもの

i番目の最後の値は $l_0$ と $l_1$ として、それぞれ最大値、最小値を保持していく。また、各顧客の空気圧リストは、その間をどのように分割しても、最小値と最大値の差分が操作回数になるので、最小値と最大値だけ保持しておく。

def get_min_max_pressure(n):
    min_max_ps = []
    for _ in range(n):
        ps = list(map(int, input().split()))
        min_max_ps.append([min(ps), max(ps)])
    return min_max_ps


T = int(input())
for t in range(1, T + 1):
    N, P = list(map(int, input().split()))
    min_max_ps = get_min_max_pressure(N)
    dp = [[0, 0] for _ in range(N + 1)]
    l0, l1 = 0, 0
    for i, min_max_p in enumerate(min_max_ps):
        min_p, max_p = min_max_p
        diff_min_max_p = max_p - min_p
        dp[i+1][0] = min(
            dp[i][0] + abs(l0 - min_p) + diff_min_max_p,
            dp[i][1] + abs(l1 - min_p) + diff_min_max_p
        )
        dp[i+1][1] = min(
            dp[i][0] + abs(l0 - max_p) + diff_min_max_p,
            dp[i][1] + abs(l1 - max_p) + diff_min_max_p
        )
        l0 = max_p
        l1 = min_p
    print('Case #{}: {}'.format(t, min(dp[N][0], dp[N][1])))

問題

アルゴリズム

実装

Discussion