数セミ見てたら、
スーパーコン2005の話が。
http://www.gsic.titech.ac.jp/supercon/supercon2005/
8チームあって、ホーム＆アウェー方式の総当り、
の試合を行うとき、
総移動距離をできるだけ小さくするような
日程を作るという問題。
これを見て、
すべての可能な日程について調べればいいんだが、
たぶんそれは無理である。
じゃあ、その日程は何種類あるか、
まずそれを調べたい。
2チームの場合
試合を、
(1 2)
などと表す。
左がホームのチームとする。
(1 2), (2 1)
あるいは、
(2 1), (1 2)
の2通りしかない。
4チームの場合
総試合数は、4*3=12。
1節に2試合ずつ行われるから、全6節。
まず、1のチームの日程を適当に決める。
これは全部で6!通りある。
残りの試合はホームかアウェーか決めればいいだけだから、
全部で6!*2*2*2=5760通り。
ここではブレークルールは考えていない。
6チームの場合
総試合数は、6*5=30。
1節に3試合ずつ行われるから、全10節。
まず、1のチームの日程を適当に決める。
これは全部で10!通りある。
ここからが難しい。
残り20試合のホームとアウェーは考えずにあてはめる。
これで、210=1024の重複がある。
1節ずつ、3通りの組み合わせがあるから、
310=59049通りを調べてOKのものをカウントする。
といっても、すぐにアウトになるものも多いので、
ここまでは調べなくてもいいと思う。
これならプログラムを書いて調べられるか？
でも、8チームの場合は？
