2015-02-11
SRM 645
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できるかと思ったが無理だった。
貪欲のコーナーケース難しい。
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150211