Hatena::Grouptopcoder

hotpepsiの練習帳

2015-02-11

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

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150211