練習会 SRM 233 DIV 1

練習だと何故か出来る俺

Easy PipeCuts

長さ100のパイプをある二点で切る。切る場所の候補が渡されるので、切ったあとのパイプの長さがL以上になる確率がなんたらかんたら。

数える。

#define rep(i, c)   for(int i = 0; i < c; ++i)
#define reps(i,s,c) for(int i = s; i < c; ++i)
#define all(c)    (c).begin(), (c).end()
#define each(i, c)  for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)

#define EPS 1e-9

using namespace std;

class PipeCuts {
public:
  double probability(vector <int> weldLocations, int L) {
    int p = 0, N = weldLocations.size();
    sort(all(weldLocations));
    rep(i,N) {
      reps(j, i+1, N) {
        if(weldLocations[i] > L ||
           weldLocations[j] - weldLocations[i] > L ||
           100 - weldLocations[j] > L)
          ++p;
      }
    }
    return 2.0*p / (N*(N-1));
  }
};

Medium SmartWordToy

四つのアルファベットからなる文字列があって、これのうち一個のアルファベットを前後のアルファベットに変えるスイッチがあるから、何回押せば目的の文字列に変えることができるか。

ただのBFS。

#define rep(i, c)   for(int i = 0; i < c; ++i)
#define reps(i,s,c) for(int i = s; i < c; ++i)
#define all(c)    (c).begin(), (c).end()
#define each(i, c)  for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)

#define EPS 1e-9

using namespace std;

int state_[26][26][26][26];

inline int& state(string s) {
  return state_[s[0]-'a'][s[1]-'a'][s[2]-'a'][s[3]-'a'];
}

class SmartWordToy {
public:
  int minPresses(string start, string finish, vector <string> forbid) {
    memset(state_, -1, sizeof(state_));
    each(s, forbid) {
      istringstream ss(*s);
      string a, b, c, d;
      ss >> a >> b >> c >> d;
      each(i,a)each(j,b)each(k,c)each(l,d)
        state_[*i-'a'][*j-'a'][*k-'a'][*l-'a'] = -2;
    }
    queue<string> Q;
    state(start) = 0;
    Q.push(start);
    while(!Q.empty()) {
      string t = Q.front(); Q.pop();
      int press = state(t);
      if(press == -2) continue; // forbidden
      if(t == finish) return press;
      rep(i, 4) {
        reps(j, -1, 2) {
          if(j != 0) {
            string n = t;
            n[i] = (n[i] - 'a' + j + 26) % 26 + 'a';
            int& st = state(n);
            if(st == -1 || press + 1 < st) {
              st = press + 1;
              Q.push(n);
            }
          }
        }
      }
    }
    return -1;
  }
};

Hard DiskCut

一枚の円盤を切る。切る機械は中心から円周に向かってしか切ることができない。また、切るときの円盤の面積ぶんのコストがかかる。ここで、円盤をそれぞれ何%に切り分ければよいかが与えられるので、最小のコストを求めなさい。

最初、面積1でパーセンテージが {10, 20, 30, 40} のときに何で最小コストが 2.9 になるのか分からなかったが、40を切り取る(コスト2)、30を切り取る(コスト0.6)、20を切り取る(コスト0.3)の順でできることに気がつく。

これを逆にすれば10と20をくっつけて30、その30と30をくっつけて60、その60と40をくっつけて100になる。みたいな事を考えて、それで解けてしまった。結局この考え方はハフマン符号化と同じアルゴリズム、つまり貪欲アルゴリズム。

なんとなくーの解法じゃなくて、きちんと証明された解法で解きたいです＞＜

#define rep(i, c)   for(int i = 0; i < c; ++i)
#define reps(i,s,c) for(int i = s; i < c; ++i)
#define all(c)    (c).begin(), (c).end()
#define each(i, c)  for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)

#define EPS 1e-9

using namespace std;

class DiskCut {
public:
  double minCost(int area, vector <int> percent) {
    double res=100.0;
    priority_queue<int, vector<int>, greater<int> > Q;
    each(i, percent) Q.push(*i);
    while(Q.size() > 1) {
      int a = Q.top(); Q.pop();
      int b = Q.top(); Q.pop();
      Q.push(a + b);
      res += a + b;
    }
    return res / (100.0 / area);
  }
};

multisetじゃなくてpriority_queueを使ってるのはただの知識不足です^q^