Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-01-10

SRM372 Div1 Easy: RoadConstruction

| 05:52 | SRM372 Div1 Easy: RoadConstruction - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM372 Div1 Easy: RoadConstruction - naoya_t@topcoder SRM372 Div1 Easy: RoadConstruction - naoya_t@topcoder のブックマークコメント

  • なんかはまった。
  • 最初deque使ってて分からなくなったのでvectorにした。STL練習大会。
  • Case#0でEが出てくれないとかで更にはまる
  • 結局55分もかけてるorz... System Testは通ったけど102.66点は痛い
class RoadConstruction {
 public:
  int getExitTime(vector<string> currentLanes) {
    int n=sz(currentLanes);
    vector<vector<pair<bool,char> > > lanes(n);
    int cars=0;
    rep(i,n){
      int l=sz(currentLanes[i]);
      rep(j,l){
        char c = currentLanes[i][j];
        lanes[i].push_back(make_pair(false,c));
        cars++;
      }
    }
    rep(t,cars){
      bool exitable=true;
      tr(lanes,it){
        if(it==(lanes.end()-1)){
          if(it->front().second=='D') return t;
          it->erase(it->begin());
          if(sz(*it)==0) lanes.erase(it);
          goto next;
        }else if(exitable){
          if(it->front().first){
            if(it->front().second=='D') return t;
            it->erase(it->begin());
            if(sz(*it)==0) lanes.erase(it);
            goto next;
          } else {
            it->front().first=true;
          }
        }
      }
   next:;
    }
    return -1;
  }
};

SRM373 Div1 Easy: StringFragmentation

| 04:51 | SRM373 Div1 Easy: StringFragmentation - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM373 Div1 Easy: StringFragmentation - naoya_t@topcoder SRM373 Div1 Easy: StringFragmentation - naoya_t@topcoder のブックマークコメント

  • 幅も高さも10000までなので、ポイント数を上限(高々9998)から1ptずつデクリメントしつつ(8ptまで)全て試せる
  • Passed System Test223.65点
  • 9'46''
#define sz(a)  int((a).size())
#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 StringFragmentation {
 public:
  int largestFontSize(string text, int width, int height) {
    vector<string> words=split(text);
    int n=sz(words);
    int longest=0;
    tr(words,it) longest=max(sz(*it),longest);
    int pt_max=(10000/longest)-2;
    for(int pt=pt_max;pt>7;pt--){
      int x=0,y=pt*2;
      rep(i,n){
        const string word=words[i];
        int w=sz(word)*(pt+2);
        x+=w;
        if(x>width){
          y+=pt*2; x=w;
          if(x>width) goto next;
        }
        x+=(pt+2);
      }
      if(y<=height) return pt;
   next:;
    }
    return -1;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090110