Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-05-05

UnluckyIntervals (SRM438 DIV1 Easy)

| 01:10 | UnluckyIntervals (SRM438 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - UnluckyIntervals (SRM438 DIV1 Easy) - TopCoder煮ブログ

本番 の System Test のときにだいたいの方針は理解したので書き下していくだけ。にも関わらず時間がかかる。だめだなぁ。

submit したら、Test Case 4 で落ちる。{2}, 1 というもの。前後 n 個はチェックしていたはずだが、n - 1 しか見ていなかった。境界条件で落とされた。んむー。境界条件に迷わされないために、ちょっと多めに計算しておいたほうがよいんだろうな。

ソース。無駄が多い。

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;

struct Unluckyness
{
  long long count;
  int number;

  Unluckyness(){}
  Unluckyness(long long c, int n): count(c), number(n){}

  bool operator<(const Unluckyness& rhs) const{
    if (count != rhs.count) return count < rhs.count;
    if (number < rhs.number) return true;
    return false;
  }
};

class UnluckyIntervals {
public:
  vector <int> getLuckiest(vector <int> luckySet, int n)
  {
    luckySet.push_back(0);
    luckySet.push_back(INT_MAX);
    sort(luckySet.begin(), luckySet.end());

    set<Unluckyness> s;

    int N = luckySet.size();
    int min = 0;
    for(int i = 0; i < N - 1; i++){
      long long num0 = (i == 0 ? INT_MIN : luckySet[i - 1]);
      long long num1 = luckySet[i];
      long long num2 = luckySet[i + 1];
      for(int j = -n; j < 0; j++){
        long long v = num1 + j;
        if (v <= min) continue;

        long long count = (v - num0) * (num1 - v) - 1LL;
        s.insert(Unluckyness(count, v));
        min = v;
      }
      s.insert(Unluckyness(0LL, num1));
      min = num1;
      for(int j = 1; j < n + 1; j++){
        long long v = num1 + j;
        if (v <= min || v >= num2) continue;

        long long count = (v - num1) * (num2 - v) - 1LL;
        if (num2 == INT_MAX) count = LLONG_MAX;
        Unluckyness u(count, v);
        s.insert(u);
        min = v;
      }
    }

    vector<int> ret;
    s.erase(s.begin());
    for(int i = 0; i < n; i++){
      ret.push_back(s.begin()->number);
      s.erase(s.begin());
    }
    return ret;
  }
}