クリプトHFTとか競プロとか

競技プログラミングや仮想通貨に関することを中心にブログを書いていきます.

JOI 2012 C - 夜店 【Python/C++で解説】

情報オリンピック2012/2013の本戦での3問目の「夜店」を解説を読みながらACすることができたので,自分なりの解説を残しておこうと思います.

問題リンク:

atcoder.jp

問題概要

N個の夜店があり,インデックスが小さい順に遊んでいく.

各夜店には遊ぶと得られる楽しさA_iと遊ぶのに必要な時間B_iが設定されている.

JOIくんは時刻0から時刻Tまでの間に夜店をめぐる.

しかし,時刻Sには大きな花火があがるので遊ばないでおく.

JOIくんが実現できる楽しさの和の最大値を求めよ.

重要な制約

 1 \leq N \leq 3000

 1 \leq T \leq 3000

 0 \leq S \leq T

考察

まず簡単な全探索を考えます.

各店を遊ぶ/遊ばないの2通りを決めて,条件を満たすかを調べていくと全探索が可能です.

このアルゴリズムの計算量は O(2^{N}) なので N \leq 20 の場合の部分点(10点) を得ることができます.

ここで問題文をよく見ると,時刻 Sまでの最大の楽しさは,

dp[i+1][j] := 店iまで見て,時刻jまでに実現できる最大の楽しさの和

とすることでO(NS)で求められることがわかります.*1

時刻Sまでの答えは簡単に求められることがわかったので,時刻Sから時刻Tまでの解を求めることを考えます.

上のDPテーブル上で時刻SからTまでの答えを考えるときには,普通にナップサックするだけでは答えが求められません(どこの店まで訪れたかわからないため).

新たなDPテーブルとしてdp2dp2[i][j] := 時刻j から店 i~Nを訪れたときに実現できる最大の楽しさの和 とします.

そうすることによって,答えをdp[i+1][S] + dp2[i][S]とすることができます.

ここで,遷移を考えます.普段のナップサックではdp[0][0]で選択肢が最小ですが,dp2テーブルの遷移はdp2[N][T]が一番選択肢が少なく, dp2[0][S]が一番多い選択肢を持ちます.

DPの遷移でmaxを使う特性上,選択肢が多い方から少ない方へ遷移することは難しく,今回は選択肢が少ない方から多い方へ遷移することにします.

すると,遷移は

 j - B_{i-1} \leq Tのとき dp2[i-1][j] = max(dp2[i-1][j] , dp2[i][j+B[i-1]] + A[i-1]) そうでないとき dp2[i-1][j] = dp2[i-1][j]としてDPテーブルを更新することができます.

よって答えは dp[i][S] + dp2[i+1][S]の和の最大値となります.

実装

*1:これがわからない場合,「ナップサックDP」などで検索してみるといいでしょう