Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-04-20

SRM438 Div1 Tricky: UnluckyIntervals

05:27 | SRM438 Div1 Tricky: UnluckyIntervals - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM438 Div1 Tricky: UnluckyIntervals - naoya_t@topcoder SRM438 Div1 Tricky: UnluckyIntervals - naoya_t@topcoder のブックマークコメント

  • Easy改めTricky
  • 落とし穴は解ったので書き直してみた
  • luckySetはソートされて与えられると思ってたらそうでない場合があった。思い込み。
  • いくつのintervalにカバーされているかのカウントが正しくなかったようで、うまくいかないケースがあったので単純な方法(掛け算して1を引く)に変更。
  • 同じコードを何度も書いてたのをまとめた
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

class UnluckyIntervals {
 public:
  vector<int> getLuckiest(vector<int> luckySet, int n) {
    int N=sz(luckySet);
    sort(all(luckySet)); /// してなかった

    priority_queue<pair<ll,int> > pq;
    tr(luckySet,it) pq.push(make_pair(0LL,-(*it)));

    vector<pair<ll,ll> > intervals;
    if (1<=luckySet[0]-1) intervals.pb(make_pair(1LL,(ll)luckySet[0]-1));

    rep(i,N-1) {
      int a=luckySet[i], b=luckySet[i+1];
      if (a+1<=b-1) intervals.pb(make_pair((ll)a+1,(ll)b-1));
    }
    intervals.pb(make_pair((ll)luckySet[N-1]+1, LONG_LONG_MAX));

    tr(intervals,it){
      ll a=it->first, b=it->second;
      if (a>b) continue;
      if (b==LONG_LONG_MAX){
        rep(i,n) pq.push(make_pair(-LONG_LONG_MAX,-(a+i)));
      } else if (a==b) { /// ここ(luckyの隙間に1つだけ数がある場合)を無視してた
        pq.push(make_pair(0LL,-a));
      } else {
        for(ll c=0,i=a,j=b,l=1,r=b-a+1; i<=j; i++,j--,l++,r--) {
          ll z = l*r-1;
          pq.push(make_pair(-z,-i)); c++;
          if (i!=j) { pq.push(make_pair(-z,-j)); c++; }
          if (c>n) break;
        }
      }
    }

    vi res;
    rep(i,n){
      pair<int,int> pr = pq.top(); pq.pop();
      res.pb(-pr.second);
    }
    return res;
  }
};

SRM438

05:17 | SRM438 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM438 - naoya_t@topcoder SRM438 - naoya_t@topcoder のブックマークコメント

04.19+.2009

DIVlevel問題名競技中後でSystem Test通過率備考
1 300 UnluckyIntervals 撃沈 o passed 25.76% 0.0
1 500 EndlessStringMachine 間に合わず - - -
1 1000 (FeudaliasWar) - -

300点問題: UnluckyIntervals

  • 時間かかったけど出来た!
  • 落とされた!
  • なんでだ!
  • 落とし穴あった!

500点問題: EndlessStringMachine

  • 間に合わず

1000点問題: (FeudaliasWar)

  • 開いてはみたけど読んでない

Challenge Time

きょうも撃墜大会。赤い人(Savior)が部屋の300点問題を次々撃墜。

0点で室内5位,Div1全体では191/574位

1272→1301

またもや0点でレーティングup...

http://gyazo.com/94c3977525c61067da9187bce85a87f7.png

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090420