kmjp's blog

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

TopCoder SRM 760 : Div1 Easy Div2 Hard HomeAwayLeague

EasyもMediumも今回簡単目だったけど、しょうもないミスしてたので出なくて助かった。
https://community.topcoder.com/stat?c=problem_statement&pm=15504

問題

Nチーム(偶数)で試合を行う。その際、以下の条件で試合が行われる。

  • 試合は2セット行われる。各セット、1対1の試合がN/2組行われる、すなわち全チームが試合に参加する。
  • 同じチーム同士が2回とも対戦することはない。
  • 各試合は、対戦相手のどちらかの地元で行う。なお、2セット試合を行う過程で、各チーム1回ずつ自分の地元と他チームの地元での試合に参加しなければならない。

Nに対し、試合の組み合わせが何通りあるか求めよ。

解法

F(n) := nチームにおける組み合わせ数
このFを小さい順に埋めていこう。
1~nの番号が振られた頂点がある有向グラフを考えよう。
自身が地元ゲームの際に対戦する相手に対し、有向辺を張ったとする。
すると、各頂点は入次数・出次数が1でないといけないので、いくつかの閉路ができる。
また、この閉路の長さは4以上の偶数でなければいけない(そうしないと同じ相手と2連戦になる)

これを踏まえてF(n)を考えよう。
1番の頂点を含む閉路長がmであるとする。
1番が先にホームゲームを行うか後に行うか…を考えると、F(n)はこう書ける。
 \displaystyle F(n) = 2 {}_{n-1} P {}_{n-1} F(0) + 2 {}_{n-1} P {}_{n-3} F(2) + ... + 2 {}_{n-1} P {}_3 F(n-4)
F(0)=1,F(2)=0として、F(4),F(6),...と順に埋めていこう。
右辺はnを辿る際に乗算と加算を行うだけなので、O(1)で更新できる。

ll mo=1000000007;
ll F[505050];
ll S;
class HomeAwayLeague {
	public:
	int matches(int x) {
		
		ZERO(F);
		F[0]=1;
		int i;
		ll P=0;
		for(i=4;i<=x;i+=2) {
			(P+=F[i-4]*(i-3))%=mo;
			(P*=1LL*(i-1)*(i-2)%mo)%=mo;
			F[i]=2*P%mo;
		}
		
		return F[x];
		
	}
}

まとめ

式は簡単だけど考察はEasyの割にちょっとめんどい。
でもDiv2 Hard 1000ptと思うと簡単かも。