ARC 042 C - おやつ

irisruneです。今回も忙しいので過去に解いた問題の解説になります。

atcoder.jp

ナップサック問題の亜種なので簡単…ということはなく少し頭を使う必要がありそうです。

package main

import (
    "fmt"
    "sort"
)

const INF = 1000000000

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

type Snack struct {
    a int
    b int
}

type Snacks []Snack

func (s Snacks) Len() int {
    return len(s)
}

func (s Snacks) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func (s Snacks) Less(i, j int) bool {
    return s[i].a < s[j].a
}

func main() {
    var n, p int
    fmt.Scan(&n, &p)

    var snacks Snacks = make([]Snack, n)
    for i := range snacks {
        fmt.Scan(&snacks[i].a, &snacks[i].b)
    }
    sort.Sort(snacks)

    ansLine := make([]int, p+1)
    for i := range ansLine {
        switch i {
        case 0:
            ansLine[i] = 0
        default:
            ansLine[i] = -INF
        }
    }

    for _, s := range snacks {
        for i := p; i >= s.a; i-- {
            ansLine[i] = maxInt(ansLine[i], ansLine[i-s.a]+s.b)
        }
        ansLine[0] = maxInt(ansLine[0], s.b)
    }

    ans := 0
    for _, a := range ansLine {
        ans = maxInt(ans, a)
    }
    fmt.Println(ans)
}

公式解説の解法は（部分点解法はともかく）よくわからないのでいわゆる天才解法だと自分は思いました。

自分の解法を説明すると、

1. おやつを値段でソートする。
2. 値段が安いおやつから選んで普通にナップサック問題を解く。
3. 値段が0の場合の満足度を今まで選んだおやつの満足度の最大値にする。

という流れになります。ポイントは3.で、最終的に選ぶおやつの中から一番値段の安いおやつの値段を0円とみなす、というアルゴリズムを実現しています。これは、

• 値段を0円とみなすおやつは、それより値段の安い（あるいは同じ）おやつより満足度が高い（あるいは同じ）。
• 値段を0円とみなすおやつより値段の高い（あるいは同じ）おやつについてのみナップサック問題（動的計画法）のアルゴリズムを適用する。

以上2点を満たすことにより実現できることが言えます。よって問題を解くことができました。

…実際は解いた当時も試行錯誤して完成したコードで、割と解説に困ってるのが見て取れると思います。書いた後で解説記事があるのを見つけたので読んでみましたが、公式解説の解法をわかりやすく説明されていると思いました。

雑記

• 割とJuliaでAtCoderやるのも何とかなりそうな気がしたので来週のどこかで扱うかもしれません。