naoya_t@topcoder

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;
  }
};