2009-05-17

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

SRM219 Div1 Easy: HealthFood

問題文の３つ目のTestCaseが全然通らないのでおかしいなあと色々試行錯誤
...
cCpって何だよ
２番目の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

過去問, 練習, Tutorials | 23:03 |

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:各人が好物を既に１つ以上食べているか(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

過去問, 練習, Tutorials | 18:40 |

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

BFSの例
そんなに難しくない
最初のsubmit: 262.33points (34'29'')
南北の道を横断している途中に東西の道を縦断できてしまうバグでfailed
直したはず (#2のところ) が直ってなくてfailed
１つ外の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 |

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

unused codeの削除が足りず, save/compile/submit直前までを３回ループ。時間もったいない！
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;
  }
};

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

		2009/05
日	月	火	水	木	金	土
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

naoya_t@topcoder

2009-05-17

SRM219 Div1 Easy: HealthFood

SRM219 Div1 Medium: TurntableService

SRM222 Div1 Medium: WalkingHome

SRM222 Div1 Easy: GroceryBagger