保存されている過去のバージョンの一覧

2014年09月23日00時55分43秒
2014年09月23日00時51分01秒

HackerRank Weekly Challenges - Week 4 3問目 - Lucy and Flowers

Source

HackerRank Weekly Challenges - Week 4 3問目
problem statement（コンテストページ）
problem statement

問題概要

ノード数 $1$ 以上の二分探索木であって，各ノードには $1$ から $N$ までの整数のうちのどれかが付けられていて，同じ整数が $2$ 回以上使われないようなものは何通りあるかを ${\rm mod}\ 1000000009\ (10^9+9)$ で求める問題．
二分探索木とは，各親ノードは左の子ノード，右の子ノードを持つことができ（持たなくても良い），親のノードに付けられた整数は，左の子ノードより大きく，右の子ノードより小さくなければいけない，というもの．

解法

まず，$k$ ノードから二分木の個数はカタラン数 $C_k$ で表される．
また，使う整数の種類と二分木の形を決めてしまえば，二分探索木において，各ノードにどの整数を割り振るかは一意に定まる．
よって，答えは，
$\displaystyle \qquad \sum_{k=1}^N \begin{pmatrix} N \\ k \end{pmatrix} C_k$
となる．
カタラン数は適当な漸化式を用いれば，$O(N)$ または $O(N^2)$ 程度で列挙でき，二項係数も $O(N^2)$ で列挙できる．
最終的に，時間計算量 $O(N^2)$ で解くことができる．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

#define ll long long
#define MD 1000000009

template<class T> void getInverseList(int n, T res[], int p){int i;res[1]=1;REP(i,2,n)res[i]=p-((ll)(p/i)*res[p%i]%p);}

template<class T> void getCtalanListSlow(int n, T res[], int md){int i,j;res[0]=res[1]=1%md;REP(i,2,n){res[i]=0;rep(j,i)res[i]=(res[i]+res[j]*res[i-1-j])%md;}}
template<class S, class T> void getCtalanList(int n, S res[], T inv[], int md){int i;res[0]=res[1]=1%md;REP(i,2,n)res[i]=res[i-1]*2LL*(2*i-1)%md*inv[i+1]%md;}

ll inv[6000], cat[5500]; int comb[5100][5100];

int N, T;

int main(){
  int i, j, k;
  ll res[5500];

  getInverseList(6000, inv, MD);
  getCtalanList(5500, cat, inv, MD);

  rep(j,5001) comb[0][j] = 0;
  rep(i,5001) comb[i][0] = 1;
  REP(i,1,5001) REP(j,1,5001) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MD;

  REP(N,1,5001){
    res[N] = 0;
    REP(i,1,N+1) res[N] = (res[N] + cat[i] * comb[N][i]) % MD;
  }

  reader(&T);
  while(T--){
    reader(&N);
    writer((int)res[N], '\n');
  }

  return 0;
}

Current time: 2024年04月23日21時46分18秒
Last modified: 2014年09月23日00時55分43秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w4
トップページに戻る

Logged in as: unknown user (not login)

ログイン：