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)はこう書ける。
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と思うと簡単かも。