Hatena::Grouptopcoder

hotpepsiの練習帳

2013-06-02

SRM 579

02:11

Div1 Easy (250) UndoHistory

問題

  • historyバッファを持つエディタがある
  • 現在行の状態は常にhistoryバッファに履歴として残る
  • 任意のhistoryバッファから2クリックで現在行にコピーすることができる
  • enterキーで出力行に入る
  • enterを入力しても現在行の内容はそのまま残る
  • 入力すべき出力行の配列が与えられる
  • キーストロークまたはクリックの合計の最小値を求める

方針

Div1 Medium (450) TravellingPurchasingMan

問題

  • 店がN個、興味のある店がM個ある
  • それぞれの店の開店時間、閉店時間、買い物にかかる時間が与えられる
  • 店Aと店Bが道路で結ばれている場合、移動にかかる時間が与えられる
  • 同じ店では1度しか買い物できない
  • 閉店時間ちょうどに入店してもよい
  • 店(N-1)からスタートして、買い物ができる最大数を求める

方針

  • 行けるか行けないかはWarshall-Floydで求めておく
  • 距離を求めた後は、最初の移動以外は、M個の店の間だけを移動したと思えばいいので、Mを超える店は忘れてよい
  • priority queueで開始時間の早いやつから処理していく
  • (TLE)
  • (終了後)
  • 店の数は16以下なのでbitDPで全て列挙できる
  • dp[行った事のある店の集合(bit)][最後に買い物した店]=最早時刻
  • 初期化として、最初にM個それぞれの店から立ち寄った場合の時刻を求めておく
  • あとはbitマスクを全て列挙する
  • https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_579/TravellingPurchasingMan.cpp

結果

x-- 0pt 563rd/803 rating 1311 -> 1266 (-45)

easyは打ち直さない判定を、1文字だけ打ち直す場合だけにしてしまい撃沈。

mediumはbitDPの練習になった。

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20130602