HackerRank Weekly Challenges - Week 4 4問目
problem statement(コンテストページ)
problem statement
$N$ 要素の配列 $\{A_k\}_{k=1}^N$ が与えられる.
その各要素を頂点に持つ二分探索木を全て考える.
$2$ つの整数 $\alpha, \beta$ が与えられるので,各二分探索木の重さは,$\alpha \times$ 深さが偶数のノードの値の和 $+ \beta \times$ 深さが奇数のノードの値の和,で定める.
全ての考えうる二分探索木の重さの和を ${\rm mod}\ 1000000009\ (10^9+9)$ で求める問題.
二分探索木とは,各親ノードは左の子ノード,右の子ノードを持つことができ(持たなくても良い),親のノードの整数は,左の子ノードの整数以上であり,右の子ノードの整数以下でなければいけない,というもの.
配列 $\{A_k\}_{k=1}^N$ をソートしておくと,各部分木は,配列の連続した区間になる.
ということで,状態を(連続した部分列,その部分列の親の深さは奇数か偶数か)を状態にして,その部分列が部分木になることが何回あるか,その部分木の $1$ 回当たり答えへの影響を計算するDPをする.
このDPは,各連続する部分に対して,どの要素をルートにするかで場合分けして計算すれば良い.
配列 $\{A_k\}_{k=1}^N$ に同じ要素が複数ある場合も,あまり気にしなくてもうまく行ってることがわかる.
時間計算量は $O(N^3)$ になる.
#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)
#define ll long long
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 reader(int *x, int *y){reader(x);reader(y);}
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 MD 1000000009
int T, N;
int alpha, beta, A[200];
ll dp[200][200][3];
int main(){
int i, j, k, l;
ll res, tmp1, tmp2;
reader(&T);
while(T--){
reader(&N);
reader(&alpha, &beta);
rep(i,N) reader(A+i);
sort(A, A+N);
rep(l,N) rep(i,N-l){
j = i+l;
dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = 0;
REP(k,i,j+1){
tmp1 = tmp2 = 1;
if(k!=i) tmp1 = dp[i][k-1][2];
if(k!=j) tmp2 = dp[k+1][j][2];
dp[i][j][0] += A[k] * tmp1 % MD * tmp2 % MD;
dp[i][j][2] += tmp1 * tmp2 % MD;
if(k!=i){
dp[i][j][0] += dp[i][k-1][1] * tmp2 % MD;
dp[i][j][1] += dp[i][k-1][0] * tmp2 % MD;
}
if(k!=j){
dp[i][j][0] += dp[k+1][j][1] * tmp1 % MD;
dp[i][j][1] += dp[k+1][j][0] * tmp1 % MD;
}
}
rep(k,3) dp[i][j][k] %= MD;
}
res = dp[0][N-1][0] * alpha - dp[0][N-1][1] * beta;
res %= MD;
if(res < 0) res += MD;
writer((int)res, '\n');
}
return 0;
}
Current time: 2024年03月29日07時02分14秒
Last modified: 2014年09月23日00時52分49秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w4
トップページに戻る
Logged in as: unknown user (not login)