HackerRank Weekly Challenges - Week 4 4問目 - Roy and alpha-beta trees

Source

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)$ になる.

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)

#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: 2017年09月26日01時55分20秒
Last modified: 2014年09月23日00時52分49秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w4
トップページに戻る

Logged in as: unknown user (not login)

ログイン: