hotpepsiの練習帳

SRM 579

02:11

Div1 Easy (250) UndoHistory

問題

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

方針

• 現在行が出力行の一部になっていれば、そのまま入力してもよい
• そうでない場合は、履歴から持ってくる必要がある
• そのまま入力するコストと、履歴から持ってきたコストの小さいほうの合計
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_579/UndoHistory.cpp

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の練習になった。