Hatena::Grouptopcoder

peryaudoのTopCoder日記

 | 

2016-02-14

WaterTank

| 18:14

#include <vector>
#include <iostream>

using namespace std;

class WaterTank {
 public:
  double minOutputRate(vector<int> t, vector<int> x, int C) {
    double l = 0.0, r = 1e9;

    vector<double> t_d, x_d;
    for (int i = 0; i < t.size(); ++i) {
      t_d.push_back(t[i]);
      x_d.push_back(x[i]);
    }

    for (int i = 0; i < 100; ++i) {
      double center = (l + r) / 2.0;
      if (IsOk(t_d, x_d, C, center)) {
        r = center;
      } else {
        l = center;
      }
    }

    return l;
  }

  bool IsOk(vector<double>& t, vector<double>& x, double C, double R) {
    double cur = 0;

    for (int i = 0; i < t.size(); ++i) {
      cur = max(0.0, cur + t[i] * (x[i] - R));
      if (cur >= C) {
        return false;
      }
    }
    return true;
  }
};

にぶたんじゃ精度的にダメだったりする?とか思って損した。

FiringEmployees

| 16:16

#include <vector>

using namespace std;

class FiringEmployees {
 public:
	int fire(vector<int> manager, vector<int> salary, vector<int> productivity) {
    vector<vector<int>> subs(manager.size() + 1);
    for (int i = 0; i < manager.size(); ++i) {
      subs[manager[i]].push_back(i + 1);
    }

    vector<int> scores(manager.size() + 1);
    for (int i = 0; i < salary.size(); ++i) {
      scores[i + 1] = productivity[i] - salary[i];
    }

    return RecurMaximize(0, scores, subs);
  }

  int RecurMaximize(int cur, vector<int>& scores, vector<vector<int>>& subs) {
    int ans = scores[cur];
    for (auto&& e : subs[cur]) {
      ans = max(ans, ans + RecurMaximize(e, scores, subs));
    }
    return ans;
  }
};

こういうクッソ簡単な回もあるんだなあ(そして今のTCの状況を考えると笑えない問題設定)

OrderOfOperations

| 15:42

自力で略

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

const auto INF = 1000000000;

class OrderOfOperations {
 public:
  int minTime(vector<string> s) {
    vector<int> insts;
    for (auto&& str : s) {
      int inst = 0;
      for (int i = 0; i < str.size(); ++i) {
        if (str[i] == '1') {
          inst = inst | (1 << i);
        }
      }

      insts.emplace_back(inst);
    }

    vector<int> dp(1 << 21, INF);
    dp[0] = 0;

    for (int i = 0; i < dp.size(); ++i) {
      for (auto&& inst : insts) {
        const auto pops = inst & ~i;
        const auto pop_counts = __builtin_popcount(pops);
        dp[i | pops] = min(dp[i | pops], dp[i] + pop_counts * pop_counts);
      }
    }

    const auto fin = accumulate(
        insts.begin(),
        insts.end(),
        0,
        [](int lhs, int rhs) {
          return lhs | rhs;
        });
    return dp[fin];
  }
};


BearFair

| 15:06

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class BearFair {
 public:
   string isFair(int n, int b, vector<int> upTo, vector<int> quantity) {
     vector<pair<int, int>> hints;
     for (int i = 0; i < upTo.size(); ++i) {
       hints.emplace_back(upTo[i], quantity[i]);
     }
     sort(hints.begin(), hints.end());

     if (hints.back().first == b && hints.back().second != n) {
       return "unfair";
     }

     if (hints.back().first != b) {
       hints.emplace_back(b, n);
     }

     vector<tuple<int, int, int>> sections;  // <l, r, k>
     sections.emplace_back(1, hints[0].first + 1, hints[0].second);
     for (int i = 1; i < hints.size(); ++i) {
       sections.emplace_back(
           hints[i - 1].first + 1, hints[i].first + 1,
           hints[i].second - hints[i - 1].second);
     }

     for (auto&& s : sections) {
       if (get<2>(s) > get<1>(s) - get<0>(s)) {
         return "unfair";
       }
     }

     vector<vector<bool>> dp(sections.size() + 1, vector<bool>(n + 1, false));
     dp[0][0] = true;
     for (int i = 1; i <= sections.size(); ++i) {
       const auto l = get<0>(sections[i - 1]);
       const auto r = get<1>(sections[i - 1]);
       const auto k = get<2>(sections[i - 1]);

       const auto even_limit = (r - l) / 2 + (r % 2 == 0 && (r - l) % 2 == 1);
       const auto odd_limit = (r - l) / 2 + (l % 2 == 0 && (r - l) % 2 == 1);

       for (int j = 0; j <= k; ++j) {
         if (j > even_limit)
           continue;
         if (k - j > odd_limit)
           continue;
         for (int cur_even = 0; cur_even <= n; ++cur_even) {
           if (cur_even - j >= 0) {
             dp[i][cur_even] = dp[i][cur_even] | dp[i - 1][cur_even - j];
           }
         }
       }
     }

     return dp.back()[n / 2] ? "fair" : "unfair";
   }
};

ある偶数nについて、偶数要素がn/2個、奇数要素がn/2個あり、下界が1、上界がbであ

る数列を考える。

q個のヒントが与えられ、upTo[i]以下の数がquantity[i]個存在するという意味である。

ある数とある数の間に何数あるかをupTo, quantityから算出できる。

=> vector<pair<int, int>>に入れてsort // <upTo, quantity>

=> .back().first == n && .back().second != b then "unfair" else .emplace_back

n, bもupTo, quantity = {n, b}という番兵に変換できる <1>

偶数奇数が同数という条件を満たせるか

=> vector<tuple<int, int, int>> // <l, r, k> に変換

各区間が[l, r) = k要素あるとする

  • 1455430058* k <= r - l, そもそもこれを満たしてないのがいたらアウト <2>

=> if k > r - l then "unfair"

l, rから偶数奇数を何個まで含めるかが決まる

偶数要素の上限 (r - l) / 2 + (r % 2 == 0 && (r - l) % 2 == 1)

奇数要素の上限 (r - l) / 2 + (l % 2 == 0 && (r - l) % 2 == 1)

vector<vector<bool>> dp(sections, vector<bool>(n, false));

dp[i][j] = i番目までのセクションで偶数要素i個を作れるか

for (int i = 0; i < k; ++i)

iとk - i 要素上限をチェックしてダメだったらcontinue

その中でkによって、偶数+奇数=kの範囲内で含める偶数要素個数の自由度が決まる

その自由度中で各区間を要素にDPして偶数個数=n/2にできればfair, さもなくばunfair

 |