2016-04-16
SRM 667
https://competitiveprogramming.info/topcoder/srm/round/16547/div/1
Div1 Easy (250) OrderOfOperations
問題
- N個の命令セットとM個のメモリセルがある
- ひとつの命令はいくつかのメモリにアクセスする
- 命令の実行時間は、アクセスされたことのないメモリの2乗である
- 各命令を1回ずつ全て実行するとき、実行時間の最小値を求める
方針
- 各メモリをビットで表す
- 全部のビットを立てるための最小コストを求める
- 最終的なビットマスクからDFSでコストを更新していく
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_667/OrderOfOperations.cpp
結果
o-- 113.86pt 189th/489 rating 1358 -> 1429 (+71)
ビットマスクは減る方向しかないので、使う順番とかどれを使ったのかは管理しなくていい。
探索してない人が意外と多く、チャレンジできたっぽい。
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20160416