Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-17

ログインしたらレーティングが+1して1501になってた

SRM219 Div1 Easy: HealthFood

| 23:46 | SRM219 Div1 Easy: HealthFood - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM219 Div1 Easy: HealthFood - naoya_t@topcoder SRM219 Div1 Easy: HealthFood - naoya_t@topcoder のブックマークコメント

  • 問題文の3つ目のTestCaseが全然通らないのでおかしいなあと色々試行錯誤
  • ...
  • cCpって何だよ
  • 2番目のCは無視すればよい
  • 138.30points (31'30'')
  • ><
  • Passed System Test
class HealthFood {
 public:
  vector <int> selectMeals(vector <int> protein,
                           vector <int> carbs,
                           vector <int> fat,
                           vector <string> dietPlans) {
    int n=sz(dietPlans), m=sz(protein);
    vector<int> ans(n);
    rep(i,n){
      ll p=0,c=0,f=0,t=0;
      string dp = dietPlans[i]; // 0-4 [CcPpFfTt]
      int dpl=sz(dp);
      rep(k,dpl){
        ll mag=1LL << ((3-k)*11);
        switch(dp[k]){
          case 'C': if (!c) c=-mag; break;
          case 'c': if (!c) c=mag; break;
          case 'P': if (!p) p=-mag; break;
          case 'p': if (!p) p=mag; break;
          case 'F': if (!f) f=-mag; break;
          case 'f': if (!f) f=mag; break;
          case 'T': if (!t) t=-mag; break;
          case 't': if (!t) t=mag; break;
        }
      }
      vector<pair<ll,int> > pt(m);
      rep(j,m){
        int calories=9*fat[j] + 5*(protein[j] + carbs[j]); // 1400 < 2048
        ll score = c*carbs[j] + p*protein[j] + f*fat[j] + t*calories;
        pt[j] = make_pair(score,j);
      }
      sort(all(pt));
      ans[i] = pt[0].second;
    }
    return ans;
  }
};

SRM219 Div1 Medium: TurntableService

| 23:03 | SRM219 Div1 Medium: TurntableService - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM219 Div1 Medium: TurntableService - naoya_t@topcoder SRM219 Div1 Medium: TurntableService - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

  • split(), map_atoi() は拙作ライブラリ
  • 1つ以上左(ないし右)に回した各状態、回さずに目の前の料理を取った状態をpriority_queueに追加。
  • 前回が回転なら料理をとる。前回料理を取ったなら回転。(というフラグを渡す)
  • あとはTLEとの戦い
  • priority_queue, map, set などに入れる情報は可能なら単一のintとかに詰めたほうがよい
    • ssssssssssssoooofeeeeeeeeeeeeeee
      • s:そこまでにかかった秒数(<=12bit)
      • o:回転オフセット([0..N-1]<=4bit)
      • f:前回料理を取った(ので回転したい)かどうか(1bit)
      • e:各人が好物を既に1つ以上食べているか(N<=15bit)
class TurntableService {
 public:
  int calculateTime(vector <string> favorites) {
    int n=sz(favorites); // 1-15
    int ful = (1<<n)-1;
    vector<vector<bool> > fav(n);
    rep(i,n){
      vi f = map_atoi(split(favorites[i]));
      fav[i].resize(n); rep(j,n) fav[i][j]=false;
      tr(f,it) fav[i][*it]=true;
    }
    set<int> s;
    priority_queue<int> pq;

    // まずは目の前の料理を取(って回転から始めたい)
    int eaten=0;
    for(int i=0,m=1;i<n;i++,m<<=1) if (fav[i][i]) eaten |= m;
    int nt=(15<<20)|32768|eaten;
    pq.push(-nt);
    // 目の前の料理を取らない(で回転から始めたい)
    pq.push(-32768);
    
    while(!pq.empty()){
      int t=-pq.top(); pq.pop();
      if (found(s,t&0xfffff)) continue;

      int sc=t>>20, ofs=(t>>16)&15, eaten=t&0x7fff;
      s.insert(t&0xfffff);

      if (eaten == ful) return sc;

      if(t&32768){
        // 料理は取らず、[1..n-1]だけ回す
        rep(nofs,n){
          int d=nofs-ofs; if(d==0) continue;
          if(d<0)d=-d; if (n<d*2) d=n-d;
          int nt=((sc+1+d)<<20)|nofs*65536|eaten;
          pq.push(-nt);
        }
      } else {
        // 目の前の料理を取る
        for(int i=0,e=ofs,m=1;i<n;i++,e=(e+1)%n,m<<=1) if (fav[i][e]) eaten |= m;
        int nt=((sc+15)<<20)|ofs*65536|32768|eaten;
        pq.push(-nt);
      }
    }
    return -1;
  }
};

SRM222 Div1 Medium: WalkingHome

| 18:40 | SRM222 Div1 Medium: WalkingHome - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM222 Div1 Medium: WalkingHome - naoya_t@topcoder SRM222 Div1 Medium: WalkingHome - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

  • BFSの例
  • そんなに難しくない
  • 最初のsubmit: 262.33points (34'29'')
  • 南北の道を横断している途中に東西の道を縦断できてしまうバグでfailed
  • 直したはず (#2のところ) が直ってなくてfailed
  • 1つ外のifで分岐させてやっと直った。
    • 横断している道から横にそれたら斜め横断になってしまうということ
  • 教訓:きちんと場合分けしてテストしよう
#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++)
#define found(s,e)  ((s).find(e)!=(s).end())

class WalkingHome {
 public:
  int fewestCrossings(vector <string> m) {
    int w=sz(m[0]),h=sz(m);
    int start_x=-1, start_y=-1, goal_x=-1, goal_y=-1;
    vector<vector<bool> > fu(h);
    rep(y,h) { fu[y].resize(w); rep(x,w) fu[y][x]=true; }
    rep(y,h) rep(x,w) {
      switch(m[y][x]){
        case 'S': start_x=x; start_y=y; break;
        case 'H': goal_x=x; goal_y=y; break;
        case '*':
        case 'F': fu[y][x] = false; break;
        case '|': case '-':
        case '.':
          break;
      }
    }
    priority_queue<pair<int,pair<int,int> > > pq;
    pq.push(make_pair(0,make_pair(start_x,start_y)));
    while(!pq.empty()){
      int sc=-pq.top().first;
      int x=pq.top().second.first, y=pq.top().second.second;
      if (x==goal_x && y==goal_y) return sc;
      pq.pop();
      if(fu[y][x]){
        int cur = m[y][x];
        if (0<=x-1 && cur!='-') { // <
          if (fu[y][x-1]) {
            int nxt=m[y][x-1], nsc=sc;
            switch(nxt){
              case '-': case '*': case 'S': case 'F': break;
              case '|':
                //if (cur=='-') break; // #2
                if (cur!='|') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x-1,y)));
                break;
            }
          }
        }
        if (x+1<=w-1 && cur!='-') { // >
          if (fu[y][x+1]) {
            int nxt=m[y][x+1], nsc=sc;
            switch(nxt){
              case '-': case '*': case 'S': case 'F': break;
              case '|':
                //if (cur=='-') break; // #2
                if (cur!='|') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x+1,y)));
                break;
            }
          }
        }
        
        if (0<=y-1 && cur!='|') { // ^
          if (fu[y-1][x]) {
            int nxt=m[y-1][x], nsc=sc;
            switch(nxt){
              case '|': case '*': case 'S': case 'F': break;
              case '-':
                //if (cur=='|') break; // #2
                if (cur!='-') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x,y-1)));
                break;
            }
          }
        }
        if (y+1<=h-1 && cur!='|') { // v
          if (fu[y+1][x]) {
            int nxt=m[y+1][x], nsc=sc;
            switch(nxt){
              case '|': case '*': case 'S': case 'F': break;
              case '-':
                //if (cur=='|') break; // #2
                if (cur!='-') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x,y+1)));
                break;
            }
          }
        }
      }
      fu[y][x] = false;
    }
    return -1;
  }
};

SRM222 Div1 Easy: GroceryBagger

| 17:49 | SRM222 Div1 Easy: GroceryBagger - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM222 Div1 Easy: GroceryBagger - naoya_t@topcoder SRM222 Div1 Easy: GroceryBagger - naoya_t@topcoder のブックマークコメント

Algorithm Tutorialsで同SRMのMedium問題が例に挙げられていたのだけれど、準備運動代わりにEasyを解いた。

  • unused codeの削除が足りず, save/compile/submit直前までを3回ループ。時間もったいない!
  • 243.89pt (4'30'')
#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++)
#define found(s,e)  ((s).find(e)!=(s).end())

class GroceryBagger {
 public:
  int minimumBags(int strength, vector <string> itemType) {
    map<string,int> m;
    tr(itemType,it){
      if(found(m,*it)) m[*it]++;
      else m[*it]=1;
    }
    int cnt=0;
    tr(m,it){
      cnt += (it->second + strength - 1) / strength;
    }
    return cnt;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090517