👌

ABC 285 E Work or Rest 解説

2023/01/16に公開

Python

解説のDPは少し自分にはわかりにくかったので、自分が解いた方法をまとめておきます。

サイクルを考える

次の曜日を考えなくてはならない可能性があるので、簡単にするため、週の最初は休日であると仮定します。

この仮定があっても、求められる最大値は変化しません。
これは、ある並びの休日、平日( $D$ )をそのまま横にスライドしていって( $E$ )も、得られる生産量が変化しないからです。

D_i=\{Rest,Work\}\\ E=\{D_p,D_{p+1},\cdots,D_{N-1},D_N,D_1,D_2,\cdots,D_{p-2},D_{p-1}\}\\ productivity(D) = productivity(E)

そこで、週はかならず休日から始まると仮定します。
このとき、週は必ず休日+複数の平日からなる小要素に分解できます。

この星では休日までの近さしか評価軸に入らないようなので、連休をあげる必要性はありません。そのため、かならず以下のような形式を取るはずです。

D=\{(Rest,Work,\cdots,Work),(Rest,Work,\cdots,Work),\cdots,(Rest,Work,\cdots,Work)\}

ところでこの小要素の種類は $2,3,\cdots,N$ までの長さしか存在しません。小要素全体での生産量は単にループしてあげれば求めることができます。

それぞれのサイクルについて、生成される生産量を考えるのに必要なオーダは $O(N^2)$ になります。

ここまでをコードに書くとこんな感じです。

    cycle_costs = {}
    for rest_cycle in range(2, N + 1):  # O(N^2)
        cycle_sum = 0
        for i in range(rest_cycle - 1):
            x = i
            y = rest_cycle - i - 2
            cycle_sum += A[min(x, y)]
        cycle_costs[rest_cycle] = cycle_sum

cycle_costsにサイクルあたりの生産量を入れています。

サイクルの組を考える

次に得られた小要素の合計で週を構成してあげなければなりません。
これは、いわゆるナップサック問題です。

適当なサイクルの組み合わせで、週の合計がNになるようにしてあげたときの最大の合計を求めてあげればよいです。

これも、 $O(N^2)$ で可能なので求まります。

    costs = [-1] * (N + 1)
    costs[0] = 0
    for cycle in cycle_costs:
        cc = cycle_costs[cycle]
        for i in range(len(costs)):
            if i + cycle > N:
                break
            if costs[i] != -1:
                costs[i+cycle] = max(costs[i+cycle],costs[i] + cc)
    print(max(costs))

最終的な解

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    cycle_costs = {}
    for rest_cycle in range(2, N + 1):  # O(N^2)
        cycle_sum = 0
        for i in range(rest_cycle - 1):
            x = i
            y = rest_cycle - i - 2
            cycle_sum += A[min(x, y)]
        cycle_costs[rest_cycle] = cycle_sum
    costs = [-1] * (N + 1)
    costs[0] = 0
    for cycle in cycle_costs:
        cc = cycle_costs[cycle]
        for i in range(len(costs)):
            if i + cycle > N:
                break
            if costs[i] != -1:
                costs[i+cycle] = max(costs[i+cycle],costs[i] + cc)
    print(max(costs))

    return


# Generated by 2.12.0 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

余談

DPの最後の要素だけみたらひとつだけWAで、最大値を見たらACで引っかかりました。

変化しているのはここだけ

    print(max(costs)) # AC
    print(costs[-1]) # WA

これはつまり、うまくサイクルで割り切れない日が存在した時に、休日が連続するにもかかわらず休みを入れてあげたほうが、そこに仕事の日を入れるよりも効率が良いということになります。

わかるような、わからないような。どんなテストケースならそんなことがありえるのかわかってません。

サイクルを考える

サイクルの組を考える

最終的な解

余談

Discussion