hotpepsiの練習帳

SRM 645

21:50

Div1 Easy (250) JanuszTheBusinessman

問題

• ホテルを経営している
• 宿泊客の到着日と出発日の配列が与えられる
• 宿泊客に特別なサービスをすると、良いレビューを残してくれる
• 特別なサービスを受けた宿泊客に居合わせた宿泊客も良いレビューを残してくれる
• 全員が良いレビューを残すために必要な特別サービスの最小値を求める

方針

• 蟻本の区間スケジューリング問題のようなやつ
• 出発日が一番早い人から貪欲に処理していけばよさそう
• 良いレビュアーではない人のうちの一番早い出発日に宿泊していて、出発日が一番遅い人に特別サービスを与える
• その範囲内の人を良いレビュアーにする
• Failed System Test
• すでに良いレビュアーだが、それ以降の区間で特別サービスを与えたほうがよいケースを見落としていた
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_645/JanuszTheBusinessman.cpp

結果

x-- +1 50pts 162nd/471 rating 1426 -> 1492 (+66)

easyはDPできるかと思ったが無理だった。

貪欲のコーナーケース難しい。

http://togetter.com/li/769406