SRM489 Div1Hard

Algorithm TopCoder

時間が数分足りなくてだめだったのでPracticeで解き直してみた

#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

#define MOD 1000000007

class AppleTrees
{
	long long dp[40][2][1600];
	int N;
public:
	int gcd(int p, int q)
	{
		while(q>0){
			int tmp = p%q;
			p = q;
			q = tmp;
		}
		return p;
	}
	
	int C(int p, int q)
	{
		int tmp[40];
		for(int i=0;i<q;i++) tmp[i] = p-i;
		for(int i=q;i>=1;i--){
			int i2 = i, g;
			for(int j=0;j<q;j++){
				if((g = gcd(i2, tmp[j])) > 1){
					tmp[j] /= g;
					i2 /= g;
				}
			}
		}
		
		long long ret = 1;
		for(int i=0;i<q;i++){
			ret *= tmp[i];
			ret %= MOD;
		}
		
		return ret;
	}
	
	int theCount(int D, vector<int> r)
	{
		sort(r.begin(), r.end());
		N = r.size();
		
		int t = 0;
		dp[0][t][0] = 1;
		
		for(int i=1;i<N;i++){
			for(int j=0;j<N;j++)
				for(int k=0;k<1600;k++) dp[j][1-t][k] = 0;
			
			for(int j=0;j<N;j++)
				for(int k=0;k<1600;k++){
					//make a new island
					if(j<N-1){
						dp[j+1][1-t][k] += dp[j][t][k] * (j+2);
						dp[j+1][1-t][k] %= MOD;
					}
					
					//join 2 islands
					if(j>0&&k+2*r[i]<1600){
						dp[j-1][1-t][k+2*r[i]] += dp[j][t][k] * j;
						dp[j-1][1-t][k+2*r[i]] %= MOD;
					}
					
					//append to the end
					if(k+r[i]<1600){
						dp[j][1-t][k+r[i]] += dp[j][t][k] * 2*(j+1);
						dp[j][1-t][k+r[i]] %= MOD;
					}
				}
			t = 1-t;
		}
		
		int sum = 0;
		for(int i=0;i<1600;i++) sum += dp[0][t][i];
		printf("%d\n", sum);
		
		long long ret = 0;
		for(int i=0;i<1600;i++){
			ret += C(D-i+N-1, N) * dp[0][t][i];
			ret %= MOD;
		}
		
		return (int)ret;
	}
};

int gcd(int p, int q) は、言うまでもなく最大公約数を求める関数。
int C(int p, int q) は、組み合わせ C(p, q) をMODで割った余りを求める関数。

解法

非常に直感的になって説明しづらいけど…

まず、木の植える順序が決まっていたら答えは簡単に求まる。すぐに、「木の間の距離の和」の最小値は決まる。その最小値において、Dに対して余分な距離は、適当にどこかに分けてやればよい。C(D - 距離の和の最小値 + N - 1, N) で求められる。
木の植える順序が決まっていなくても、「距離の和の最小値」が決まっていたらこれで答えは出る。ここで、それぞれの「距離の和の最小値」になるような並べ方が何通りあるかを求めたい。

今、「島」という概念を勝手に導入する。「島」とは、木の１つ以上の並びである。それぞれの島について、「距離の和の最小値」がある。木を、必要な最小値が小さい順に植えていくとするとき、島を使うと、次の３通りの操作のどれかであるとわかる。そして、この３通りの操作を許すとき、操作によってできる（最終的に単一の島になったときの）木の並び方は、普通に木を並べたときの並べ方と同一であることがわかる。

  1. どこかにその木だけからなる島を作る。
  2. どこかの島の端にその木を付け足す。
  3. 隣り合っている島をその木を仲介としてくっつける。

操作２，３を行うときには、その島の「距離の和の最小値」はいくらか増える。しかし、操作の対象の島には「その木より、必要な最小値が小さい」木しか存在しないため、その時植える木にのみこの値の増分は依存する。
ここで、「植えた木の本数」「島の数」「距離の和の最小値」に対して「場合の数」を覚えておけば、DPでこの場合の数を順次計算することができる。

これで、それぞれの「距離の和の最小値」になるような並べ方が何通りあるかは出たので、最初に言ったように組み合わせの数を考えて答えを求めればよい。