Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-04-29

SRM233 Div1 Easy: PipeCuts

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

SRMのEasy問題にも手を出した

  • 特に何ということもなく。
  • こういうのを「やるだけ」とか言うのか
  • 224.33poitns (9'49''), Passed system test
  • この回なら2問submitして2問とも通った計算
  • 3問目に手を出すためにはもっと速く!→反復練習。あとfor関連のマクロの整備とか
#define sz(a)  int((a).size())
#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 forr(var,from,to) for(int var=(from);var<=(to);var++) 

class PipeCuts {
 public:
  double probability(vector <int> weldLocations, int L) {
    int n=sz(weldLocations);
    sort(all(weldLocations));
    int nC2=n*(n-1)/2,cnt=0;
    rep(i,n-1){
      int a=weldLocations[i];
      forr(j,i+1,n-1){
        int b=weldLocations[j]-a, c=100-weldLocations[j];
        //printf("[%d,%d/%d] %d %d %d\n", i,j,n, a,b,c);
        if(a>L || b>L || c>L) cnt++;
      }
    }
    return (double)cnt/nC2;
  }
};

SRM233 Div1 Medium: SmartWordToy

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

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

  • 典型的なBFSの例
  • 状態数が26^4しかない。隣のstateへの移動コストは全て1
  • priority queue使ってみますた
  • 優先順位の逆転方法、というかソートの向きの設定方法を思い出せないのでステップ数を負にして入れている。(←よくやる)
  • 自作split()使ってます
  • 197.58points (59'47'') デバッグコメント類を削除して(というか BEGIN CUT HERE / END CUT HEREで囲んで)submitしてるけど、この分量だとコメント部分を投稿前に消したりとかしなくても大丈夫そうなので、あと1分前後早く出せると思う
  • Passed system test
class SmartWordToy {
  inline int state(int ch0,int ch1,int ch2,int ch3){
    return ((ch0-'a') << 15) | ((ch1-'a') << 10) | ((ch2-'a') << 5) | (ch3-'a');
  }
  inline int state_ch(int state,int pos){
    return (state >> (15 - 5*pos)) & 0x1f; // 0-25
  }
  int str2state(const string str){
    return state(str[0],str[1],str[2],str[3]);
  }
/*
  string state2str(int state){
    stringstream ss;
    rep(i,4) ss << 'a'+state_ch(state,0);
    return ss.str();
  }
*/
  int incr(int state, int pos){
    int ofs=15-5*pos;
    int ch=state_ch(state,pos);
    state &= ~(0x1f << ofs);
    int newstate=state|(((ch+1)%26)<<ofs);
    return newstate;
  }
  int decr(int state, int pos){
    int ofs=15-5*pos;
    int ch=state_ch(state,pos);
    state &= ~(0x1f << ofs);
    int newstate=state|(((ch+25)%26)<<ofs);
    return newstate;
  }
     
 public:
  int minPresses(string start, string finish, vector <string> forbid) {
    int s_state=str2state(start), f_state=str2state(finish);

    vector<int> passed(1048576,INT_MAX);
    tr(forbid,it){
      vector<string> ss = split(*it);
      int al=sz(ss[0]), bl=sz(ss[1]), cl=sz(ss[2]), dl=sz(ss[3]);
      rep(a,al){
        rep(b,bl){
          rep(c,cl){
            rep(d,dl){
              int st=state(ss[0][a], ss[1][b], ss[2][c], ss[3][d]);
              passed[st]=-1;// forbidden
            }
          }
        }
      }
    }
    if(passed[f_state]==-1) return -1;

    priority_queue<pair<int,int> > pq;
    pq.push(make_pair(0,s_state));

    while (!pq.empty()) {
      int step=-pq.top().first, st=pq.top().second, st_;
      pq.pop();
      if(st==f_state) return step;
      if(step < passed[st]){
        passed[st]=step;

        step++;
        rep(i,4){
          st_ = incr(st,i);
          if(passed[st_]>step) pq.push(make_pair(-step,st_));

          st_ = decr(st,i);
          if(passed[st_]>step) pq.push(make_pair(-step,st_));
        }
      }
    }
    return -1;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090429