Hatena::Grouptopcoder

thorikawa@top coder

topcoder id: the_poly
|

2013-01-13

TopCoder - SRM566 Div1

06:28 | はてなブックマーク - TopCoder - SRM566 Div1 - thorikawa@top coder

AC/Opened/Unopened 1476->1488

250のバグ取りに時間を取られすぎた。

250 PenguinSledding

以下に場合分けできる。

1) 1つの頂点から全てのパスが出ている場合

2) パスが三角形をなす場合

1)のケースは、各頂点iから出ているパスの数をjとしたときに、その頂点からパスが出ているパターンは2のj乗ありえる。全体を合計した時に、パスが1つの場合は、パスの数分だけ重複、パスが0の場合は、頂点の数-1だけ重複するのでその分後から引いてやる。

2)は普通に数え上げる。

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
#include <cmath>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define rep(i,j,n) for((i)=(j); (i)<(int)(n);(i)++)
#define pb push_back 
#define mp make_pair 

typedef long long ll;
typedef vector <int> vi;
typedef pair <int, int> pii;

class PenguinSledding {
public:
long long countDesigns(int n, vector <int> checkpoint1, vector <int> checkpoint2) {
  int m = checkpoint1.size();
  int i,j,k;
  int memo[52][52]={0};
  REP(i,m){
    int a = checkpoint1[i]-1;
    int b = checkpoint2[i]-1;
    memo[a][b]=1;
    memo[b][a]=1;
  }

  ll res=0;
  REP(i,n){
    ll r=0;
    REP(j,m){
      if(checkpoint1[j]==i+1 || checkpoint2[j]==i+1){
        r++;
      }
    }
    ll t = std::pow((long double)2,(long double)r);
    res += t;
  }
  ll tri=0;
  REP(i,n) REP(j,i) REP(k,j) {
    if (memo[i][j] && memo[j][k] && memo[i][k]) tri++;
  }
  return res - (ll)m - (ll)n + (ll)1LL + tri;
}

500 PenguinEmperor

要復習。city日分だけ「i日でj移動する場合の数」を予め求めておき、あとは日数がcityの倍数になるようにキープしつつ(余りの分は後で足す)、バイナリツリーみたいなことをやればいいと思ったが実装しきれなかった。

解いた。まずi日でj移動する場合の数をDPで求め、さらにそれからn*(2^i)日でj移動する場合の数をDPで求めて、最後に繰り返し二乗法で、daysPassed分の場合の数を求めてやれば、計算量O(log(days/n)*(n^2))で解ける。もっと綺麗にかけると思う。っていうか書きたい。

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define rep(i,j,n) for((i)=(j); (i)<(int)(n);(i)++)

typedef long long ll;

const ll MOD = 1000000007LL;

ll d[352][352] = {0LL};
// e[i][j] := the number of journeys that take n*(2^i) and j step
ll e[65][352] = {0LL};
ll f[65][352] = {0LL};

class PenguinEmperor {
public:
int countJourneys(int n, long long days) {
  int i,j,k;

  REP(i,352) REP(j,352) d[i][j] = 0LL;
  REP(i,65) REP(j,352) e[i][j] = 0LL;
  REP(i,65) REP(j,352) f[i][j] = 0LL;
  
  d[0][0] = 1LL;
  rep(i,1,n+1) REP(j,n) {
    int prev1 = (j-i+n)%n;
    int prev2 = (j+i+n)%n;
    if (prev1 == prev2) d[i][j] = d[i-1][prev1];
    else d[i][j] = (d[i-1][prev1] + d[i-1][prev2])%MOD;
  }

  // initialize e[0][x]
  REP(j,n) {
    e[0][j] = d[n][j];
  }
  // calculate e[i][j]
  rep(i,1,65) REP(j,n) {
    REP(k,n){
      // move j via k
      int step = (j-k+n)%n;
      e[i][j] += (e[i-1][k]*e[i-1][step]) %MOD;
      e[i][j] %= MOD;
    }
  }
                   
  ll a = days/n;
  ll r = days%n;

  int base2[65] = {0};
  i = 0;
  REP(i,65){
    base2[i] = a%2;
    a/=2;
  }

  REP(j,n){
    f[0][j] = d[r][j];
  }

  REP(i,64) REP(j,n) {
    int cycles = base2[i];
    if (cycles == 0) {
      // don't move
      f[i+1][j] = f[i][j];
    } else {
      // move n*(2^i)days
      REP(k,n){
        // move j via k
        int step = (j-k+n)%n;
        f[i+1][j] += (f[i][k]*e[i][step]) % MOD;
        f[i+1][j] %= MOD;
      }
    }
  }
  return f[64][0];
}

2011-04-18

SRM 401 Div1

14:32 | はてなブックマーク - SRM 401 Div1 - thorikawa@top coder

練習

250 FIELDDiagrams

n列で、かつ最上行のボックスの数がiの場合の数を求める関数をd(n,i)とすると、d(n,i)=d(n-1,1)+d(n-1,2)+....+d(n-1,min(i,n-1))なので、メモ化再帰で解く。

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define rep(i,j,n) for((i)=(j); (i)<(int)(n);(i)++)

using namespace std;
typedef long long ll;

ll memo[40][40];

ll d(int n, int i){
  if(n==1){
    return 1;
  }
  if(memo[n][i]) return memo[n][i];
  ll r=0;
  int k;
  int m=min(i,n-1);
  REP(k,m+1){
    r+=d(n-1,k);
  }
  //printf("%d,%d return %d\n", n, i, r);
  memo[n][i]=r;
  return r;
}

class FIELDDiagrams {
public:
long long countDiagrams(int f) {
  ll r=0;
  int j,k;
  REP(j,40) REP(k,40) memo[j][k]=0;
  for(int i=1;i<=f;i++){
    r+=d(f,i);
  }
  return r;
}

2011-04-16

SRM 503 Div1

03:47 | はてなブックマーク - SRM 503 Div1 - thorikawa@top coder

250Passed System Test
500Opened
1000UnOpened

250 ToastXToast

かなり悩むが、組み合わせが存在しない場合以外で考えらるケースとして、

undertoastedの最大値がovertoastedの最小値以上の場合でも、undertoastedの最大値を持つToastと、overtoastedの最小値をもつToastの、2つのToastがあれば十分。

それ以外の場合は、当然1つのToastで十分。

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define rep(i,j,n) for((i)=(j); (i)<(int)(n);(i)++)

using namespace std;

class ToastXToast {
public:
int bake(vector <int> u, vector <int> o) {
  sort(u.begin(), u.end());
  sort(o.begin(), o.end());
  int us=u.size();
  int os=o.size();
  int miu=u[0];
  int mio=o[0];
  int mau=u[us-1];
  int mao=o[os-1];
  if(miu>=mio) return -1;
  if(mau>=mao) return -1;
  if(mau<mio) return 1;
  else return 2;
}

KingdomXCitiesandVillages

本番では解けず。

期待値の線形性より、各村について、距離が近い村・Cityを順番に見ていき、(その距離になる確率)*(距離)を足すことで、期待値を求められる。

(その距離になる確率)については村である場合は、その村が自分よりも前にconnectされている確率を求めていく必要がある。(本番ではこれがうまく求められなかった。)

この(その距離になる確率)を考えるときに、逆に自分より前にn個の村がconnectされていない確率を考えると、その確率は1/(n+1)だから、差分を取って、その距離になる確率は1/n-1/(n+1)になる。

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
#include <cmath>

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define rep(i,j,n) for((i)=(j); (i)<(int)(n);(i)++)

using namespace std;

typedef long long ll;

struct P {
  bool isv;
  double dist;
};

bool cmp(const P& p1, const P& p2){
  if(p1.dist > p2.dist) return true;
  else return false;
}

double dist(int x1, int y1, int x2, int y2){
  return std::pow((double)(::pow(x1-x2,2)+::pow(y1-y2,2)), 0.5);
}

class KingdomXCitiesandVillages {
public:
double determineLength(vector <int> cx, vector <int> cy, vector <int> vx, vector <int> vy) {
  int nc = cx.size();
  int nv = vx.size();
  vector< vector <P> > pv(nv);
  int i,j,k;
  double r=0;
  REP(i,nv){
    REP(j,nc){
      double d = dist(cx[j],cy[j],vx[i],vy[i]);
      P *p = (P*)malloc(sizeof(P));
      p->isv = false;
      p->dist = d;
      pv[i].push_back(*p);
    }
    REP(j,nv){
      if (j==i) continue;
      double d = dist(vx[j],vy[j],vx[i],vy[i]);
      P *p = (P*)malloc(sizeof(P));
      p->isv = true;
      p->dist = d;
      pv[i].push_back(*p);
    }
    std::sort(pv[i].begin(), pv[i].end(), cmp);
    std::reverse(pv[i].begin(), pv[i].end());
    k=0;
    double e=0;
    double parent=1;
    int m=1;
    while(k<nc+nv-1){
      int vc=0;
      int cc=0;
      double dist=pv[i][k].dist;
      int l;
      for(l=k;dist==pv[i][l].dist;l++){
        if (pv[i][l].isv) vc++;
        else cc++;
      }
      k=l;
      if(cc>0){
        e+=parent*dist;
        break;
      }else{
        for(int i=0; i<vc; i++){
          double pp = (double)1/(double)m/(double)(m+1);
          e+=pp*dist;
          parent-=pp;
          m++;
        }
      }
    }
    r+=e;
  }
  return r;
}

SRM 402 Div1

23:10 | はてなブックマーク - SRM 402 Div1 - thorikawa@top coder

250 RandomSort

練習。配列の数が8個と少ないので、1手順ずつ実行して再帰で求める。

メモ化しないと計算量が爆発して死ぬので、配列をキーにしてメモ化するが、最初stringstreamに一個ずつ数を文字列として足していったら、その部分で異常に時間を食って{8,7,6,5,4,3,2,1}のケースで死んだ。ビット列をキーにするようにしたらつるりと行った。(8以下の数*8個までなので一つの数字を4ビットで表してもint型に収まる。)

教訓:stringstreamは遅いので使うな。

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define rep(i,j,n) for((i)=(j); (i)<(int)(n);(i)++)

using namespace std;
typedef vector<int> vi;

map<int, double> memo;

int n;

int getkey(vi& in){
  int ss=0;
  int i;
  REP(i,n){
    ss=(ss<<4)+in[i];
  }
  return ss;
}

double e(vi& in){
  int i,j,k;
  int key=getkey(in);
  if(memo[key]){
    return memo[key];
  }
  int c=0;
  double r=0;
  vi newin(n);
  REP(i,n){
    REP(j,i){
      if(in[i]<in[j]){
        //swap
        REP(k,n) newin[k]=in[k];
        int tmp=newin[j];
        newin[j]=newin[i];
        newin[i]=tmp;
        c++;
        r+=(1+e(newin));
      }
    }
  }
  if(c){
    memo[key]=r/(double)c;
    return memo[key];
  }
  return 0;
}

class RandomSort {
public:
double getExpected(vector <int> p) {
  int i,j;
  n=p.size();
  memo.clear();
  return e(p);
}

2011-04-11

SRM 502 Div1

00:46 | はてなブックマーク - SRM 502 Div1 - thorikawa@top coder

250 TheLotteryBothDivs

Suffixの一部が、別のSuffixを包含するものは除外して、残ったものでできる場合の数を足し合わせる。

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
#include <assert.h>
#include <cmath>

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define rep(i,j,n) for((i)=(j); (i)<(int)(n);(i)++)

using namespace std;

class TheLotteryBothDivs {
public:
double find(vector <string> gs) {
  sort(gs.begin(), gs.end());
  int n = gs.size();
  vector<int> flag(n);
  int i,j;
  REP(i,n){
    REP(j,i){
      int index=i;
      string s1 = gs[i];
      string s2 = gs[j];
      if (s1.size()<s2.size()){
        string t=s2;
        s2=s1;
        s1=t;
        index=j;
      }
      if(s1.substr(s1.size()-s2.size(), s2.size()) == s2){
        // s1 contain s2
        printf("flag[%d](%s - %s)=1\n", i, s1.c_str(), s2.c_str());
        flag[index]=1;
      }
    }
  }

  double r = 0.0;
  REP(i,n){
    if(flag[i]!=1){
      int s=gs[i].size();
      r+=pow(10.0, -1*(s));
    }
  }
  return r;
}

500 TheProgrammingContestDivOne

A>B <=> ABの順で解いたときの得点>BAの順で解いたときの得点

と定義すると、順序集合として定義できる。

あとはソートした順で問題をピックアップして解けば良いので、最後に解いた問題番号と、解き終わった秒数でDP

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define rep(i,j,n) for((i)=(j); (i)<(int)(n);(i)++)

using namespace std;
typedef long long ll;

struct P {
  int mp, ppm, rt;
} ps[51];

bool cmp(const P& p1, const P& p2){
  return ((ll)p1.rt*(ll)p2.ppm) < ((ll)p2.rt*(ll)p1.ppm);
}

//vector<P> ps;

ll memo[100001][51];

ll dp(int t, int i){
  if(i==-1){
    return 0;
  }
  if(memo[t][i]!=-1){
    return memo[t][i];
  }
  P p = ps[i];
  ll r;
  if(t-p.rt<0){
    // no time to solve
    r=dp(t, i-1);
  }else{
    r=max(((ll)p.mp-((ll)p.ppm*(ll)t)) + dp(t-p.rt, i-1), dp(t, i-1));
  }
  memo[t][i]=r;
  return r;
}

class TheProgrammingContestDivOne {
public:
int find(int T, vector <int> maxPoints, vector <int> pointsPerMinute, vector <int> requiredTime) {
  int n = maxPoints.size();
  int i,j;
  REP(i,100001){
    REP(j,51){
      memo[i][j]=-1;
    }
  }
  REP(i,n){
    ps[i].mp = maxPoints[i];
    ps[i].ppm = pointsPerMinute[i];
    ps[i].rt = requiredTime[i];
  }
  sort(ps, ps+n, cmp);
  int r=-1;
  REP(i,T+1){
    REP(j,n){
      int t=dp(i,j);
      r=max(r,t);
    }
  }
  return r;
}

JonniJonni2011/08/29 20:25That's really shwerd! Good to see the logic set out so well.

TitiaTitia2011/09/01 01:05Kewl you slhoud come up with that. Excellent!

ownaskcrmfqownaskcrmfq2011/09/02 16:48B8KUV3 <a href="http://pknxxkgeayhy.com/">pknxxkgeayhy</a>

oiatopqzpoiatopqzp2011/09/02 21:344PRph0 , [url=http://cfuluhblmlqo.com/]cfuluhblmlqo[/url], [link=http://vfbaywfqpgyt.com/]vfbaywfqpgyt[/link], http://hjsoypgfnifk.com/

2011-04-10

Sortの練習

23:02 | はてなブックマーク - Sortの練習 - thorikawa@top coder

Merge Sort

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

typedef vector<int> vi;

vi merge(vi& a, vi& b){
  int an = a.size();
  int bn = b.size();
  a.push_back(INT_MAX);
  b.push_back(INT_MAX);
  int ia=0, ib=0;
  vi r;
  while(ia < an || ib < bn){
    if(a[ia] < b[ib]){
      r.push_back(a[ia]);
      ia++;
    }else{
      r.push_back(b[ib]);
      ib++;
    }
  }
  return r;
}

vi merge_sort(vi& a){
  int n = a.size();
  if(n<=1) return a;
  vi h1(a.begin(), a.begin()+n/2);
  vi h2(a.begin()+n/2, a.begin()+n);
  vi r1 = merge_sort(h1);
  vi r2 = merge_sort(h2);
  return merge(r1, r2);
}

int main (int argc, char* argv[]) {
  vi arrayvec;
  ifstream ifs(argv[1]);
  int num;
  ifs >> num;
  int temp;
  for(int i=0; i<num; i++){
    ifs >> temp;
    arrayvec.push_back(temp);
  }
  ifs.close();
  vi r = merge_sort(arrayvec);
  for(int i=0; i<r.size(); i++){
    cout << i << ":" << r[i] << endl;
  }
}

Quick Sort

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

typedef vector<int> vi;

int pivot(vi& a){
  int n=a.size();
  for (int i=1; i<n; i++){
    if (a[i] != a[0]){
      return max(a[0], a[i]);
    }
  }
  return a[0];
}

vi quick_sort(vi& a){
  // choose pivot
  int n = a.size();
  if (n<=1){
    return a;
  }
  int p = pivot(a);

  int r=n-1;
  int last = 0;
  for(int i=0; i<=r; i++){
    if(a[i]>=p){
      last = i-1;
      bool find_pair = false;
      for(int j=r; j>=i; j--){
        if(a[j]<p){
          //swap i and j
          find_pair = true;
          int temp = a[i];
          a[i] = a[j];
          a[j] = temp;
          r = j-1;
          last = r;
          break;
        }
      }
      // pair not found
      if (!find_pair) break;
    }
  }
  // divide by last
  if (last == -1) last = 0;
  vi h1(a.begin(), a.begin()+last+1);
  vi h2(a.begin()+last+1, a.begin()+n);
  vi r1 = quick_sort(h1);
  vi r2 = quick_sort(h2);
  r1.insert(r1.end(), r2.begin(), r2.end());
  return r1;
}

int main (int argc, char* argv[]) {
  vi arrayvec;
  ifstream ifs(argv[1]);
  int num;
  ifs >> num;
  int temp;
  for(int i=0; i<num; i++){
    ifs >> temp;
    arrayvec.push_back(temp);
  }
  ifs.close();
  vi r = quick_sort(arrayvec);
  for(int i=0; i<r.size(); i++){
    cout << i << ":" << r[i] << endl;
  }
}

GweneldaGwenelda2011/08/30 08:51With the bases ldaoed you struck us out with that answer!

ocvejceeuldocvejceeuld2011/08/30 16:479b10Zh <a href="http://nnzpnsouqbxo.com/">nnzpnsouqbxo</a>

yqbdxwuyqbdxwu2011/09/01 16:332RSlrO , [url=http://valgkoyqhyna.com/]valgkoyqhyna[/url], [link=http://aeuxfmcnvulh.com/]aeuxfmcnvulh[/link], http://bgqzllbpbroj.com/

ofypctpaccoofypctpacco2011/09/03 18:295WQZ6k <a href="http://kbgavupjoxoy.com/">kbgavupjoxoy</a>

lxfxgnvlxfxgnv2011/09/04 02:11EA1RQ1 , [url=http://clxpdognbnor.com/]clxpdognbnor[/url], [link=http://sggpccrhyxox.com/]sggpccrhyxox[/link], http://mluzdtnyvesl.com/

|