■

昨日の続き。会社からWebを漁ってみたところ
どうやら、この類の問題は、計画数学の対象となっているようだ。
いくつか面白いサイトがあった。

http://www.misojiro.t.u-tokyo.ac.jp/~tomomi/B4-M2/1998/miyashiro.html
↑Jリーグの対戦日程とか

たとえば昨日さりげなく触れた、最終日は1位と2位が戦って欲しいとか
そういう、盛り上げるための工夫を入れていくと、計算が大変になる。

んで、考え方。はじめにn人総当りを作ってしまって
その後、必要ない対戦日を削る方法が楽なんじゃないかと。
n人総当りの作り方は

このサイトの方式が楽い。
http://www.geocities.co.jp/Berkeley-Labo/6317/league.htm

	A	B	C	D	E	F
A	*	5	4	3	2	1
B	5	*	2	4	1	3
C	4	2	*	1	3	5
D	3	4	1	*	5	2
E	2	1	3	5	*	4
F	1	3	5	2	4	*

とりあえず総当りができたら、左下と右上にいる数字を対戦数に合わせて消す。
理由は左下と右上にあるほど、実力差が大きい対戦になるため。
ためしに1と2を消してみる。

	A	B	C	D	E	F
A	*	5	4	3	*	*
B	5	*	*	4	*	3
C	4	*	*	*	3	5
D	3	4	*	*	5	*
E	*	*	3	5	*	4
F	*	3	5	*	4	*

2位と3位の対決が無くて嫌だ！という場合は2の代わりに3を消せばOK。
これで機械的に作る方法が一応確立された、はず。
奇数人参加の場合はこの状態から更に、Fとの対戦を全て休みにすることで作れる。

この作り方は人数に対して線形にしか計算量が増えないので
JWLのSeason1のように18人参加でも問題なくリーグを組める。
6人程度だと、昨日のように手作業で埋めたほうが綺麗に作れるのは確か。
大人数の場合にはこちらのほうが楽。試合数と参加者がいくつでも柔軟に対応できる。

公平性は疑問点ありまくり。↑の例だとCとDはDのほうが厳しい対戦になっている。
n人総当りを作った後に、いくつか条件を設けて、消す数字を選べば良いとは思うが
万人が納得する条件は難しい。そもそも、公平であるかどうかは
順位1つによる実力の差が、全て等しいという仮定をしないと判断しにくいが
複雑なゲームではその仮定はまずなりたたない。だから公平っぽい雰囲気だけで
満足するべきだと思う。CとDは明らかにDがきついのでそういうところは直す。とか。

とりあえずこんな感じで。