kmjp's blog

競技プログラミング参加記です

TopCoder SRM 690 Div1 Hard WolfHockeyTeamHard、Div2 Hard WolfHockeyTeamEasy

SRM

そんな単語知らなかった。
https://community.topcoder.com/stat?c=problem_statement&pm=14238
https://community.topcoder.com/stat?c=problem_statement&pm=14239

問題

2*Nのグリッドに対し、0～(2N-1)の整数を1個ずつ入れていく。
このグリッドのパラメータは、各列における大きい方の値を計N並べたものに、各行における最大値を計2個並べた計(N+2)個の整数で表される。
(グリッドの中身が異なっても、パラメータは等しくなるケースがある)

なお、各行の最大値はK以上でなければならない。
条件を満たすパラメータは何通りあるか。

Div1とDiv2の違いはNの上限のみである。

解法

基本的には大きい順に数字を埋めていく。
Kは2N-1以下なので、最初に(2N-1)を置いた時点で1行分はK以上の数字が入ることが確定する。
あとはどのタイミングでもう１行に最初に数字が入るかを考えていく。

Div2解法

O(N^2)のDPで解ける。
f(n,s,row) := 大きい順に2N-1からn+1までグリッドに埋めたとき、各列において1行だけ埋まった列がs個あるような埋め方の組み合わせ数。
row=1ならまだ１つの行しか値が入っておらず、row=0なら２行とも１個は値が入っている。

次の数字nの入れ方は以下の組み合わせがある。

  • row=1、すなわち1行しか値が入っていない場合 ：
    • 1行値が入っている列のもう片方に値を入れる。これはn≧Kである場合のみ可能。
    • どちらの行も値が入ってない列に値を入れる：
      • すでに他の値が入っている行の側に値を入れる。
      • 他の値が入っていない行に値を入れる。これはn≧Kである場合のみ可能。
  • row=0、すなわちもう2行とも何かしらの値が入っている場合：
    • 1行値が入っている列のもう片方に値を入れる。
      • 他の値が入っていない行に値を入れる。どちらの行に値を入れても最終的なパラメータは同じなので、２行候補があっても２倍しない点に注意。
ll dp[2020][2020][2];
ll mo=1000000007;

class WolfHockeyTeamEasy {
	public:
	int count(int N, int K) {
		ZERO(dp);
		dp[2*N][1][1]=2*N;
		int i,l,o;
		for(i=2*N-1;i>=1;i--) {
			FOR(o,2) FOR(l,2*N) if(dp[i+1][l][o]) {
				int did=2*N-i;
				int blank=N-(did+l)/2;
				if (o==1) { // 1 row is empty
					// fill existing column
					if(l && i>K) (dp[i][l-1][0] += dp[i+1][l][1])%=mo;
					// start new column
					if(blank) {
						// same row
						(dp[i][l+1][1] += dp[i+1][l][1]*blank)%=mo;
						// new row
						if(i>K) (dp[i][l+1][0] += dp[i+1][l][1]*blank)%=mo;
						
					}
				}
				else { // both row has entries
					// fill existing column
					if(l) (dp[i][l-1][0] += dp[i+1][l][0])%=mo;
					// start new column
					if(blank) (dp[i][l+1][0] += dp[i+1][l][0]*blank)%=mo;
				}
			}
		}
		return dp[1][0][0];
	}
}

Div1 Hard解法

Twitterで流れてきた解法を参考に解いた。

Nが大きいのでO(N^2)の解法は間に合わないので、もう少し早い解法を考える。

まず、要素がどの行・列に入るか考えるのは面倒なので、基本的に新規の列・行に値を割り当てる場合は左詰・上詰であると仮定する。
最後に行の並び順2!通りと列の並び順N!通りを掛け合わせれば帳尻がある。

2N-1から順に値を埋めて行き、数aで初めて２行目に値が入ったとする。
この入り方は以下の何れかである。

  • すでにaより大きな値が１行入っている列の、もう片方の列にaを入れた。(どの列に入れたかはパラメータに現れないので重複してカウントしないようにする)
  • ２行とも値が入っていない列にaを入れた。

aを入れてしまえば、後はa未満の値を空いたセルに埋めていけば良い。
ただ、２行とも空いている列がいくつか残っている場合、それらに最初に何を入れるかは最終的なパラメータに影響するので、それらを考慮した組み合わせ数を求めなければならない。
これは実質２行分のヤング標準盤の値の埋め方に等しい。
ヤング図形 - Wikipedia

２行とも空いている列がd個、1行だけ空いている列がs個あったとする。
上記記事のフック長の公式によると、その組み合わせは \frac{(s+d)!}{\frac{(s+1)!d!}{s-d+1}}通りとなる。
これは階乗を事前に計算しておけばO(1)で求められるので、全体でO(N)で求められる。

ll mo=1000000007;

const int NUM_=1002001;
ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll modpow(ll a, ll n) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll hook2(int s,int d) {
	if(s<d) return 0;
	if(d==0) return 1;
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	assert(s+d<=NUM_);
	ll rev=fact[d]%mo*fact[s+1]%mo*inv[s-d+1]%mo;
	return fact[s+d]*modpow(rev,mo-2)%mo;
}

class WolfHockeyTeamHard {
	public:
	int count(int N, int K) {
		ll ret=0;
		int i;
		
		if(N==1) return (K==0)?2:0;
		
		for(i=K;i<2*N-1;i++) {
			int upper=2*N-1-i;
			int left=N-upper;
			
			//lower
			if(left>=0) ret += hook2(N-1,left)%mo;
			//new
			if(left>0) ret += hook2(N,left-1)%mo;
			ret %= mo;
		}
		
		return ret*2*fact[N]%mo;
		
	}
}

まとめ

終わってみればDiv1の方がコードが短い。
ヤング標準盤なんて知らなかったよ…。