スーパーコン第１１回大会^{1}

スポーツ・スケジューリング

東京大学情報理工学系研究科松井知己

スーパーコンピューティング・コンテスト（通称，スーパーコン）の第１１回大会が， 8 月 1 日（月）から 5 日（金）までの 5 日間，東京工業大学で行われました．

今年は表題にありますように「スポーツ・スケジューリング」をテーマに課題問題を作成しました．これは今，アルゴリズムの研究者の中でホットな話題の１つです．そこで今回は，このスポーツ・スケジューリングの話を主題にしたいと思います．でも，その前に，重要なコンテストの結果をお知らせしておきましょう．

優勝は Lunatic （岩井・久保田・日坂）でした

スーパーコンは，プログラミング大好きな高校生・高専生の皆さんのチームに東工大に来てもらい，東工大のスパコンを使って課題問題のプログラミングに挑戦してもらうイベントです．（詳しくは最近出版されました「スーパーコン甲子園 [1]」を読んでください！）今年も予選で選抜された精鋭 10 チームが熱い闘いをしました．

今回の課題問題は，あるスポーツの 8 チームがホームグラウンドを巡りながら総当り戦を行うことを想定し，その日程表を作成する問題です．実際に作成するのは，入力として与えられたホームグラウンド間の距離に対し，総移動距離の少ない効率的な日程表を計算するプログラムです．スパコンで制限時間の 3 分間以内に出力しなければなりません．

審査で使ったデータには，男子プロバレーボールのＶリーグのホームグラウンド間の距離を元に作成したものを用いました（表 1） . もちろん，最終審査のときまで，このデータのことは秘密です！このデータに

1http://www.gsic.titech.ac.jp/supercon/supercon2005/

表 1: 審査に使用した距離データ．

A B C D E F G H
A 0 13 27 556 440 246 207 204
B 13 0 35 567 452 259 220 216
C 27 35 0 571 419 264 187 222
D 556 567 571 0 129 859 388 747
E 440 452 419 129 0 651 258 628
F 246 259 264 859 651 0 438 42
G 207 220 187 388 258 438 0 396
H 204 216 222 747 628 42 396 0

対する上位 3 チームの結果が以下の通りです．チーム Lunatix （岩井聡，久保田悠樹，日坂翔馬）の皆さんが，第 2 位以下にかなり差をつけた結果で見事優勝でした．ちなみに，他のデータでも走らせてみましたが，チーム Lunatix のプログラムは安定して良い成績を出していました．立派な優勝プログラムだったといえるでしょう．

コンテストの結果

チーム名学校名総移動距離
Lunatix 筑波大附属駒場高校  21840
UNYUX 麻布高校 23075
yettryby 筑波大附属駒場高校  23597

スポーツ・スケジューリングとは，スポーツの試合日程表を作る問題の総称です．以下，スポーツスケジューリングについて簡単にご紹介します [2]．

本稿ではチームが 2n(偶数) 存在する状況について考えましょう^{2}．まず最初に，全てのチーム対が 1 回ずつ戦う総当たり戦について議論します．すぐ分かるように総試合数は n(2n − 1) となります．各試合は，対戦する 2 チームのどちらかのホームグラウンドで行い，

2チーム数が 2n − 1(奇数) の問題は, 人工的に 2n 番目のチームを作り, チーム 2n と対戦することは, そのチームは休みとすることで対処できる場合もあります．

チーム 1 日目 2 日目 3 日目 4 日目 5 日目 1  3  @4  5  @6  2 2  @5  6  \underline{4}  \underline{3}  @1 3  @1  5  @6  @\underline{2}  4 4  @6  1  @2  5  @3 5  2  @3  @\underline{1}  @\underline{4}  6 6  4  @2  3  \underline{1}  @5 図 1: チーム数 6 のスケジュール

チーム i と j が戦う際，チーム i のホームグラウンドで試合を行うならば, この試合はチーム i のホームゲームであると言い, チーム j のアウェイゲームであると言います. 以下で考えるのは，毎日 n 試合が平行して行われ，全試合は 2n − 1 日で終了するスケジュールです．図 1 は，上記の条件を満たすスケジュールの一例です．スケジュールの各行はチームに対応し，行内の数字は日ごとの対戦相手を表しています．図 1 のスケジュールでは，チーム 1 は 1 日目にチーム 3 と対戦し，以下チーム 4, 5, 6, 2 の順序で試合を行っています．各試合の前にある@の記号は，その試合が対戦相手の本拠地で行われる，すなわち（その行のチームにとって）アウェイゲームことを示しています．例えば，チーム 1 はチーム 4 と 2 日目に試合を行い，この試合はチーム 4 の本拠地で行われる事を示しています．

[figure: 6; 6; 6; 1; 2; 3; 4; 5; 1 日目; 2; 3; 4; 5; 1; 2 日目; 3; 4; 5; 1; 2; 3 日目; 6; 6; 4; 5; 1; 2; 3; 4 日目; 5; 1; 2; 3; 4; 5 日目]図 2: 2n = 6 の基準スケジュール.

このようなスケジュールは，任意の（偶数）チーム数について存在することが知られています．以下でその作り方の一例を示しましょう．図 2 に示すように，チーム 1, 2, …, 2n − 1 を半径 1 の円周上に等間隔に並べ，チーム 2n を円の中心に配置します．平行な矢印を n − 1 本，向きを互い違いに並べ，それと垂直な半径に対応する線分を書いた円盤を用意します．矢印の両端のチームが戦うチーム対を表し，試合は矢印の頭のチームのホームグラウンドで行うとします．この円盤を先ほどの円の上で 1/(2n − 1) 周ずつ回転させて，各日の試合を決定します (図 2 では番号を回転させている)．ただし後述する理由で，半径に対応する線分の矢印は，円盤の回転毎に反転させます^{3}．上記の手続きで作られたスケジュールを，基準スケジュールと呼びます．スケジュールには，図 1 のように基準スケジュールで無いものも存在します．

あるスケジュールにおいて，チーム i が t 日目と t+1 日目の両日ホームゲームを戦うとき， t + 1 日目の試合はチーム i のブレークであると言います．また両日アウェイゲームであるときも， t + 1 日目の試合はチーム i のブレークであると言います．図 1 では，ブレークの場所に下線を引いてあります．チーム i について，ブレークとなっている試合数をチーム i のブレーク数と言い，各チームのブレーク数の総和を単にブレーク数と呼びます^{4}．例えば図 1 では，チーム５のブレーク数は２，ブレーク数は６です．上で述べたように，ブレークにはホームゲームの連続とアウェイゲームの連続の２種類があります．少し考えていただくと分かると思いますが，実はホームの連続でできるブレークの数と，アウェイの連続でできるブレークの数はいつも同じになります．例えば図 1 では，ホームの連続のブレークが３，アウェイの連続のブレークも３となっています．ブレークの多いスケジュールはアウェイゲームの連続が多く，選手の消耗が激しいため望ましくないとされます．

3数学的には以下のように記述される；第 t 日目に戦うチーム対は, {{2n, t}, {t+1, t−1}, {t+2, t−2}, …, {t+n−1, t−n+1}} であり (ただし t−k, t+k はモジュロを取って 1 から 2n−1 の間の値にしたもの), (1) チーム対 {2n, t} の試合のグラウンドは, t が偶数ならば 2n, t が奇数ならば t とし, (2) チーム対 {t + k, t − k} の試合のグラウンドは, k が偶数ならば t − k, k が奇数ならば t + k とする．

4http://www.gsic.titech.ac.jp/supercon/supercon2005/ で公開している本戦課題の文章（2005 年 8 月 1 日版）では，「ブレーク数」の定義に特別なものを用いているので注意されたい．

基準スケジュールは，ブレーク数いつもは 2n − 2 になることが簡単に確認できます．残念ながら， (チーム数が偶数の際は) ブレークの無いスケジュールは存在しませんが，以下の性質が成り立ちます．定理チーム数が 2n の任意のスケジュールにおいて, ブレーク数は 2n − 2 以上である．証明：任意のスケジュールにおいて, 「ホーム・アウェイゲームのどちらを戦っているか」が全ての試合日で同一なチーム対は存在しない．なぜならば, もしこのようなチーム対が存在するならば, このチーム対が戦う試合日が存在しないからである. ブレークを持たないチームがあったとすれば，そのチームはホームゲーム (H) とアウェイゲーム (A) を交互に戦っており，そのような H と A の列は (AHAHAH⋯A)(HAHAHA⋯H) の 2 つしか存在しない. ゆえにブレークを持たないチームは, 最大 2 つしか存在せず，他の 2n − 2 チームは１以上のブレークを持つ．よって任意のスケジュールにおいてブレーク数は 2n − 2 以上である. □

上記の定理から分かるように，基準スケジュールはブレーク数最小のスケジュールである事が保証されています．では実際にはどんなスケジュールが使われているのでしょうか？表 2 に J リーグとセリエ A の例を挙げましょう． H がホームゲーム， A がアウェイゲームを表します．残念ながら J リーグのスケジュールは，ブレーク数の公平性という観点からは，セリエ A のスケジュールより質が悪いようです^{5}．

次に，今回のスーパーコンの本戦課題にもなった，表 2: ホーム (H) ・アウェイ (A) ゲームのパターン

5実際は，各試合日の間に○○杯といった試合が入るので，この表だけから判断を下すのは間違いかもしれません．

J リーグ 2001 年シリーズ前半戦

磐田 : HAHAH\underline{H}AHAHAHAHA 1
市原 : AH\underline{H}AHAH\underline{H}AHAHAH\underline{H} 3
名古屋 : HAHAHAH\underline{H}AHAHAHA 1
浦和 : AH\underline{H}AHAH\underline{H}AHAHA\underline{A}\underline{A} 4
Ｃ大阪 : HAHA\underline{A}HAHAHAHAHA 1
札幌 : AHAHAHA\underline{A}HAHAHAH 1
福岡 : HA\underline{A}HAHA\underline{A}HAHAH\underline{H}A 3
Ｇ大阪 : AHAH\underline{H}AHAHAHAHAH 1
横浜 : HA\underline{A}HAHAHA\underline{A}HAH\underline{H}A 3
神戸 : AH\underline{H}AHAHAHAHAHAH 1
Ｆ東京 : HA\underline{A}HAHAHAHA\underline{A}H\underline{H}A 3
東京Ｖ : AH\underline{H}AHAHAHAH\underline{H}A\underline{A}H 3
柏  : HA\underline{A}HAHA\underline{A}HAHAHAH 2
清水 : AHAHA\underline{A}HAHAHAHAH 1
鹿島 : HA\underline{A}HAHAHAHAHAHA 1
広島 : AH\underline{H}AHAHAH\underline{H}AHA\underline{A}H 3

セリエ A 2000/2001 年シリーズ前半戦

Atalanta : HA\underline{A}HAHAHAHAH\underline{H}AHAH 2
Bari  : HAHAH\underline{H}AHAHAHA\underline{A}HAH 2
Bologna  : AHAHAH\underline{H}AHAHAHAHAH 1
Brescia  : AH\underline{H}AHAHA\underline{A}HAHAHAHA 2
Fiorentina : AHAH\underline{H}AHA\underline{A}HAHAHAHA 2
Inter  : AHAHAH\underline{H}AHAHA\underline{A}HAHA 2
Juventus : AHAHAHAHAHA\underline{A}H\underline{H}AHA 2
Lazio  : AHAH\underline{H}AHAHAHAHAHAH 1
Lecce  : AHAHA\underline{A}HAHAHAH\underline{H}AHA 2
Milan  : HAHAHA\underline{A}HAHAH\underline{H}AHAH 2
Napoli  : HAHAHAHAHAH\underline{H}A\underline{A}HAH 2
Parma  : HA\underline{A}HAHAH\underline{H}AHAHAHAH 2
Perugia  : HAHA\underline{A}HAH\underline{H}AHAHAHAH 2
Reggina  : HAHAHA\underline{A}HAHAHAHAHA 1
Roma  : HAHA\underline{A}HAHAHAHAHAHA 1
Udinese  : HAHAHAHAHAH\underline{H}AHAHA 1
Verona  : AH\underline{H}AHAHAHAHA\underline{A}HAHA 2
Vicenza  : AH\underline{H}AHAHAHAHA\underline{A}HAHA 2

２重総当り戦について簡単に紹介しましょう． 2n チームが 2(2n − 1) 日で，各チーム対が双方のホームグラウンドで 1 回ずつ戦うスケジュールを 2 重総当たり戦と呼びます (総試合数は 2n(2n − 1) となります). 2 重総当たり戦のスケジュールは，（１重）総当り戦のスケジュールの後ろに，ホームとアウェイを反転させたスケジュールを加えることで簡単に作ることもできます．この操作をミラーリングと呼びます．セリエ A ではミラーリングで作った２重総当り戦のスケジュール用いています． J リーグでは，ミラーリングで作った２重総当り戦のスケジュールを，「前半」「後半」の中で日程を入れ替えたものを使用しています^{6}．もちろん，ミラーリングの構造を持たない２重総当り戦のスケジュールも沢山あります．

最後に，カーネギーメロン大学のトリック教授によって公開されている有名なテスト問題である Traveling Tournament Problem (TTP) について簡単にご紹介しましょう [3]． TTP では各チームのホームグラウンド間の距離が与えられます．このとき， 2 重総当り戦スケジュールで以下を満たすものを対象とします． (1) 各チームはホームゲームの連続は高々３回まで， (2) 各チームはアウェイゲームの連続は高々３回まで， (3) 各チーム対は連続して戦わない (i 対 j の直後の j 対 i は禁止)． TTP は， (1)〜(3) の制約を満たすスケジュールの中で，チームの移動距離の総和が最小のものを求めるという問題です．ただし，各チームは自分のホームグラウンドから出発し，すべての試合が終了したあと自分のホームグラウンドに帰ってくるとします． TTP は非常に難しい問題とされており，最適解が得らているのは（たった）８チームの問題例で，それも 20 台の並列計算機を用いて約 4 日間かかって得られています．（現時点では）１０チーム以上の問題例の最適解は分かっていません．興味のある方はホームページ [3] をご覧下さい．今回のスーパーコン本戦課題は，上記の (1) 〜(3) を以下の 2 つ； (SC1) 各チームはホームゲームの連続は高々２回まで， (SC2) 各チームはアウェイゲームの連続は高々３回まで，に変更した TTP の変種でした．ホームページ [3] では， TTP の各問題例に対する歴代の世界記録保持者の名前が発表されています．今回のスーパーコンでは，コンテストという制約上 TTP の変種が出題されましたが，興味を持たれた方は是非 TTP そのものに挑戦してもらいたいと思います．

最後にスポーツスケジューリングの現状について簡単にまとめましょう．アメリカマイナーリーグ（野球）では，総移動距離最小のスケジュールが議論されています．メジャーリーグ（野球）では，ブレークの連続等の不公平が少ないスケジュールと共に， TV 放映権の販売先まで決める問題が解かれています．これについてはトリック教授率いるグループが今年度スケジュール作成の仕事を獲得したことが話題になりました^{7}．先の日本プロ野球リーグ制の議論を見ても分かるように，日本のプロスポーツ界はマネージメント面において大きな転換期を迎えようとしています．今後数年間の内に，スケジュール作成を含めた収益管理等について詳細に議論されるようになることは間違いないと筆者は予想しています．皆さんも，贔屓のチームがスケジュールで損をしていないか，是非確かめてみて下さい．そして「良い（悪い）」スケジュールとは何なのか，考えて見てください．こんな身近な所にもワクワクするような数学が潜んでいます．

6なぜ単純なミラーリングを使っていないのか，理由は不明です．ただ，単純なミラーリングで作ったスケジュールは，前半後半の継ぎ目の部分でブレークが発生しやすい傾向があります．

参考文献

[1] 松田裕幸，渡辺治，「スーパーコン甲子園」，日本評論社， 2005 年．

[2] 宮代隆平，松井知己，「スポーツスケジューリング」 , オペレーションズ・リサーチ， 50(2)， pp. 119–124, 2005．

[3] http://mat.gsia.cmu.edu/TOURN/

7朝日新聞 2005 年 4 月 11 日