Hatena::Grouptopcoder

shnyaの参戦記録

2011-05-31練習

うーん・・・、今回は全体的に自力で解けてなくてよくない。。。

SRM 470 Div1 Medium 00:35  [http://www.topcoder.com/stat?c=problem_statement&pm=10735&rd=14153:title=SRM 470 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10735&rd=14153:title=SRM 470 Div1 Medium] - shnyaの参戦記録

上下にn個づつ点があり、上下の点同士をランダムに結んでいった時、直線の交わる数の期待値を求める問題。

一部の直線は最初から引かれている。

解き方わからなかった・・・。DPっぽくできるかな?と思ってたけど、そう甘くなかった。正解のひとつは上部の2点のペアを全て列挙し、各ペアごとに確率を計算、加算していく。

class DrawingLines {
public:
  double countLineCrossings( int n, vector <int> startDot, vector <int> endDot ) {
    vector<int> u(n),d(n),u2(n);
    for(int i = 0; i < int(startDot.size()); ++i){
      u[startDot[i]-1] = 1;
      u2[startDot[i]-1] = endDot[i]-1;
    }
    for(int i = 0; i < int(startDot.size()); ++i)
      d[endDot[i]-1] = 1;

    vector<int> f(n);
    partial_sum(d.begin(), d.end(),f.begin());
    long double siz = n  - startDot.size();
    int siz2 = startDot.size();
    long double res = 0.0;
    for(int i = 0; i < n; ++i){
      for(int j = i+1; j < n; ++j){
        if(u[i] && u[j]){
          res += (u2[i] > u2[j]) ? 1 : 0;
        }else if(u[i]){
          res += (u2[i] - (f[u2[i]] - 1)) / siz;
        }else if(u[j]){
          res += (n - u2[j] - 1  - (siz2 - f[u2[j]])) / siz;
        }else{
          res += 0.5;
        }
      }
    }
    return res;
  }
};

SRM 468 Div1 Easy 00:35  [http://www.topcoder.com/stat?c=problem_statement&pm=10762&rd=14183:title=SRM 468 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10762&rd=14183:title=SRM 468 Div1 Easy] - shnyaの参戦記録

T9入力をシミュレートする問題。各文字入力ごとに候補を絞り込むように計算してSubmit、Failed System Test。。

#文字の入力があった時の挙動が間違えてた・・・。

class T9 {

  std::vector<std::string>
  split(const std::string &str, const std::string &delim){
    std::vector<std::string> res;
    size_t current = 0, found, delimlen = delim.size();
    while((found = str.find(delim, current)) != std::string::npos){
      res.push_back(string(str, current, found - current));
      current = found + delimlen;
    }
    res.push_back(std::string(str, current, str.size() - current));
    return res;
  }

  vector<string> remove_dict(const vector<string> &d, size_t k){
    vector<string> d2;
    for(int i = 0; i < int(d.size()); ++i){
      if(d[i].size() == k){
        d2.push_back(d[i]);
      }
    }
    sort(d2.begin(), d2.end());
    return d2;
  }

  string rec(int k, const string &key, const vector<string> &part, vector<string> &dict){
    if(key == "") return "";
    if(dict.size() == 1) return dict[0];
    if(k == int(key.size())) return remove_dict(dict,k)[0];
    if(key[k] == '#' || key[k] == '*'){
      int sum = 0;
      for(size_t i = k; i < key.size(); i++){
        if(key[i] == '#'){
          sum++;
        }else if(key[i] == '*'){
          sum += 5;
        }
      }
      return remove_dict(dict,k)[sum];
    }
    int l = key[k] - '0' - 1;
    string p = part[l];
    vector<string> dict2;
    for(int j = 0; j < int(dict.size()); j++){
      for(int i = 0; i < int(p.size()); i++){
        if(p[i] == dict[j][k]){
          dict2.push_back(dict[j]);
        }
      }
    }
    return rec(k+1,key,part,dict2);
  }

public:
  string message( vector <string> part, vector <string> dict, vector <string> keystrs ) {
    string keystr = accumulate(keystrs.begin(), keystrs.end(), string(""));
    vector<string> v = split(keystr,"0");
    ostringstream oss;
    for(int i = 0; i < int(v.size()); ++i){
      oss << rec(0,v[i],part,dict);
      if(i != int(v.size())-1) oss << " ";
    }
    return oss.str();
  }
};

SRM 468 Div1 Medium 00:35  [http://www.topcoder.com/stat?c=problem_statement&pm=10765&rd=14183:title=SRM 468 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10765&rd=14183:title=SRM 468 Div1 Medium] - shnyaの参戦記録

0 - N-1までの各都市をそれぞれ、自動車を使うか、飛行機を使うかを選択して、目的地に着く時間を最小にする問題。ただし飛行機を使えるのはk回まで。連続して飛行機を使う場合はkを消費しない。


DP・・・は、メモリ使用量的に厳しい。

差分配列を考えれば、その中で部分和が最大となる範囲は、珠玉のプログラミングに書かれている分割統治法で求められO(nlogn)*Kで間に合うはず、ということでプログラミング。

いくらやってもシステムテストが通らない・・・orz

で、結局あきらめて、通らなかったコードが下。

class RoadOrFlightHard {
  pair<LLI,pair<LLI,LLI> > rec(const vector<LLI> &v, LLI l, LLI u){
    LLI k = (l + u) / 2;
    LLI sumu = 0, sumui = k, maxsumu = 0;
    if(l > u){
      return make_pair(-1,make_pair(u-1,l+1));
    }
    if(l == u){
      return make_pair(v[l],make_pair(l-1,u+1));;
    }
    for(LLI i = k; i <= u; i++){
      sumu += v[i];
      if(sumu > maxsumu){
        sumui = i;
        maxsumu = sumu;
      }
    }
    LLI suml = maxsumu, sumli = k, maxsuml = maxsumu;
    for(LLI i = k-1; i >= l; i--){
      suml += v[i];
      if(suml > maxsuml){
        sumli = i;
        maxsuml = suml;
      }
    }
    return max(make_pair(maxsuml,make_pair(sumli-1,sumui+1)),max(rec(v,l,k-1),rec(v,k+1,u)));
  }

public:
  long long minTime( int _N, int _roadFirst, int _roadProd, int _roadAdd, int _roadMod, int _flightFirst, int _flightProd, int _flightAdd, int _flightMod, int _K ) {
    LLI N = _N, roadFirst = _roadFirst, roadProd = _roadProd,
      roadAdd = _roadAdd, roadMod = _roadMod, flightFirst =  _flightFirst,
      flightProd = _flightProd, flightAdd = _flightAdd,
      flightMod = _flightMod, K = _K;
    vector<LLI> v(N);
    LLI road = roadFirst % roadMod, flight = flightFirst % flightMod, roadSum = road;
    v[0] = road - flight;
    for(int i = 1; i < N; i++){
      flight = (((flight*flightProd) % flightMod) + flightAdd) % flightMod;
      road = (((road*roadProd) % roadMod) + roadAdd) % roadMod;
      v[i] = road - flight;
      roadSum += road;
    }
    queue<pair<LLI,LLI> > Q;
    Q.push(make_pair(0,N-1));
    vector<LLI> res;
    int count = 0;
    while(!Q.empty()){
      pair<LLI,LLI> p = Q.front();
      count++;
      Q.pop();
      if(p.first > p.second) continue;
      pair<LLI,pair<LLI,LLI> > pp = rec(v,p.first,p.second);
      if(pp.first <= 0){
        continue;
      }else{
        res.push_back(pp.first);
        if(count < 32){
          Q.push(make_pair(p.first,pp.second.first));
          Q.push(make_pair(pp.second.second,p.second));
        }
      }
    }
    sort(res.begin(),res.end(),greater<LLI>());
    for(LLI i = 0; i < K && i < int(res.size()); i++){
      roadSum -= res[i];
    }
    return roadSum;
  }
};

Editorial見て、DPのメモリの使用量はこういう場合に効率化できるということを思い知りました。。

LLI dp[2][2][42];

class RoadOrFlightHard {

public:
  long long minTime( int _N, int _roadFirst, int _roadProd, int _roadAdd, int _roadMod, int _flightFirst, int _flightProd, int _flightAdd, int _flightMod, int _K ) {
    LLI N = _N, roadFirst = _roadFirst, roadProd = _roadProd,
      roadAdd = _roadAdd, roadMod = _roadMod, flightFirst =  _flightFirst,
      flightProd = _flightProd, flightAdd = _flightAdd,
      flightMod = _flightMod, K = _K;
    LLI road = roadFirst % roadMod, flight = flightFirst % flightMod;
    vector<LLI> flightTime(1,flight),roadTime(1,road);
    for(int i = 1; i < N; i++){
      flight = ((flight*flightProd) + flightAdd) % flightMod;
      road = ((road*roadProd) + roadAdd) % roadMod;
      flightTime.push_back(flight);
      roadTime.push_back(road);
    }
    memset(dp,0,sizeof(dp));
    for (int i = N - 1; i >= 0; --i) {
      const int me = i % 2, old = 1 - me;
      for (int fl = 0; fl < 2; ++fl){
        for (int k = 0; k <= K; ++k){
          LLI& best = dp[me][fl][k];
          best = dp[old][0][k] + roadTime[i];
          if (fl == 1)
            best = min(best, dp[old][fl][k] + flightTime[i]);
          else if (k > 0)
            best = min(best, dp[old][1][k-1] + flightTime[i]);
        }
      }
    }
    return dp[0][0][K];
  }
};

SRM 467 Div1 Easy 00:35  [http://www.topcoder.com/stat?c=problem_statement&pm=10823&rd=14151:title=SRM 467 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10823&rd=14151:title=SRM 467 Div1 Easy] - shnyaの参戦記録

教授がくるのが遅いので、定期的に抜けだして遊んでいた場合、抜けだした時に運悪く教授がくる確率を求めよ、という問題。

問題自体は一見簡単。

でも引っ掛けがひどい。。。

この問題の正解率が低い理由がすごくわかる。。

でもまぁこの問題に限らず、練習でもSystem Test Failedばっかりなのでなんとかしていきたい。。

頑張れば条件分岐だけで、ループ使わずにいけると思うけど、ループ使った方が記述がシンプルになるので使ってみた。

class LateProfessor {
public:
  double getProbability( int wait, int walk, int late, int best, int worst ) {
    if(late - walk > 0) return 0.0;
    int T = wait + walk;
    int min = 0,cnt = 0;
    for(int i = best, t = best % T; i < worst; i++, t++){
      if(t == T) t = 0;
      if(wait <= t && t < T - late)
        min++;
      cnt++;
    }
    if(best == worst){
      int t = best % T;
      if(wait < t && t <= T - late)
        return 1.0;
      else
        return 0.0;
    }
    return (long double) min/cnt;
  }
};

SRM 467 Div1 Medium 00:35  [http://www.topcoder.com/stat?c=problem_statement&pm=10239&rd=14151:title=SRM 467 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10239&rd=14151:title=SRM 467 Div1 Medium] - shnyaの参戦記録

下記の式で与えられるSuperSumを求める問題。

SuperSum(0 , n) = n, for all positive n.
SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... + SuperSum(k-1 , n), for all positive k, n.

1 <= k <= 50
1 <= n <= 1000000000

ノートに向かって1時間程悩むがギブアップ。Editorial見ると答えはパスカルの三角形になっているらしい。。。

こういう問題の場合、小さい集合で簡単にコード書いて計算してみるのがよさそうな気がしてきた。

剰余ライブラリは下記URLに書かれた先輩方から頂きました。

http://topcoder.g.hatena.ne.jp/n4_t/20100416/1271392320

http://topcoder.g.hatena.ne.jp/cafelier/20100416/1271391378

typedef long long int LLI;

LLI M = 1000000007LL;

LLI MUL(LLI x, LLI y) { return x*y % M; }
LLI POW(LLI x, LLI e) { LLI v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
LLI DIV(LLI x, LLI y) { return MUL(x, POW(y, M-2)); }

LLI C(LLI n, LLI k) { LLI v=1; for(LLI i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }

class SuperSum {
public:
   int calculate( int k, int n ) {
     return C(n+k,k+1);
   }
};

SRM 466 Div1 Medium 03:44  [http://www.topcoder.com/stat?c=problem_statement&pm=10863&rd=14150:title=SRM 466 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10863&rd=14150:title=SRM 466 Div1 Medium] - shnyaの参戦記録

N行5列の各セルごとに重複なく数字が書かれたくじがあり、ランダムに5個の1<k<5*Nとなる数字を選んだ際に、1行に3個以上選ばれた数字があった場合は当たりくじとなる。

Nが与えられた時、くじの当たる確率を求めよ。

この問題は、あまり確率系の問題が得意とはいえないのに一発でアクセプトされてちょっと嬉しかった。

くじが当たらない組み合わせは、

(1個の数字が選択された行数, 2個の数字が選択された行数) = (5,0)
(1個の数字が選択された行数, 2個の数字が選択された行数) = (3,1)
(1個の数字が選択された行数, 2個の数字が選択された行数) = (1,2)

の3通りだけ。ので状態数も少ない。

まだ1つも数字が選択されていない行から数字が選択された場合と、1個の数字が選択された行で再度選択された場合でそれぞれ再帰する。

全探索してもたかだがO(2^5)程度なので、全探索で解く。

class LotteryPyaterochka {
  long double rec(int k, vector<int> &v, int N){
    if(k == 0) return 1.0;
    long double res = 0.0;
    for(int i = 0; i < 2; i++){
      if(v[i] == 0) continue;
      long double a = v[i] * (5 - i);
      v[i]--;
      v[i+1]++;
      if(v[1] + v[2] <= N)
        res += a * rec(k-1,v,N);
      v[i+1]--;
      v[i]++;
    }
    return res;
  }

public:
   double chanceToWin(int N) {
     vector<int> v(3);
     v[0] = N;
     long double div = 1.0;
     for(int i = 0; i < 5; i++)
       div *= (5*N - i);
     return (1.0 - rec(5,v,N)/div);
   }
};