topcoder

naoya_t@topcoder

2009-04-29

SRM233 Div1 Easy: PipeCuts

過去問, 練習, Tutorials | 04:15 |

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

特に何ということもなく。
こういうのを「やるだけ」とか言うのか
224.33poitns (9'49''), Passed system test
この回なら２問submitして２問とも通った計算
３問目に手を出すためにはもっと速く！→反復練習。あと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

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

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してるけど、この分量だとコメント部分を投稿前に消したりとかしなくても大丈夫そうなので、あと１分前後早く出せると思う
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;
  }
};

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