Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-30

SRM379 div2 (過去問)

12:29

ぐだぐだとながら作業でやってしまったため, どの問題もかなり時間がかかってしまいました. 集中してやらないと時間がもったいないですね.

Easy - DownloadingFiles

いくつかのファイルをダウンロードする. スピードと残り時間が与えられる. あるファイルのダウンロードが完了すると, 開いた帯域を残りのファイルに割り振ることができる. すべてのファイルがダウンロード完了する時間を求める.

問題文中で, ファイルのダウンロードする順序や帯域の割り当て方は解に影響しないと保証されていたので, 機械的に処理するだけです. ダウンロードが完了するごとに帯域を残りのファイルに適当に割り当てます.

class DownloadingFiles {
public:
  double actualTime(vector <string> tasks) {
    double ret = 0;
    vector <pair <double, double> > t;

    for (int i=0; i<tasks.size(); i++) {
      int speed = 0, time = 0;
      sscanf(tasks[i].c_str(), "%d %d", &speed, &time);
      t.push_back(make_pair(time, speed));
    }

    for (int i=0; i<t.size(); i++) {
      double free = 0;
      double minus = 0;
      double time = 100000;
      int pos = 0, pos2 = 0;
      
      for (int j=0; j<t.size(); j++)
        if (t[j].first > 0 && t[j].first < time) {
          time = t[j].first;
          pos = j;
        }

      ret += t[pos].first;
      minus = t[pos].first;

      for (int j=0; j<t.size(); j++) {
        t[j].first -= minus;
        if (t[j].first <= 0) {
          free += t[j].second;
          t[j].second = 0;
        }
        if (t[j].first > 0)
          pos2 = j;
      }

      t[pos2].first = t[pos2].first * t[pos2].second / (t[pos2].second + free);
      t[pos2].second = t[pos2].second + free;
    }

    return ret;
  }
};

Medium - SellingProducts

商品の値段を決める. 顧客ごとに値段とコストが与えられる. ある顧客は値段以下の商品なら購入する. 利益は 売値 - コスト. 利益が最大になるよう売値を決定する.

売値よりコストが上回っていたらその顧客には売らないという, greedy っぽい単純なアルゴリズムで大丈夫です. 売値の候補は "price" の各要素の値だけしかありえないので, それらをすべて調べます.

class SellingProducts {
public:
  int optimalPrice(vector <int> price, vector <int> cost) {
    int max_profit = 0;
    int opt_price = INT_MAX;

    for (int i=0; i<price.size(); i++) {
      int profit = 0;
      for (int j=0; j<price.size(); j++)
        if (price[j] >= price[i] && price[i] > cost[j])
          profit += price[i] - cost[j];

      if (profit == max_profit && opt_price > price[i]) {
        opt_price = price[i];
      } else if (profit > max_profit) {
        opt_price = price[i];
        max_profit = profit;
      }
    }

    if (max_profit == 0) opt_price = 0;

    return opt_price;
  }
};