Kさんの高校では,土曜日に体育館をいくつかの部が交代で使っている。体育館はネットで二つのコートに仕切ることができるが,同じ時間に利用する部が多いと,一つのコートを二つの部で分け合うことになり,練習がしにくくなる。生徒会で施設の係をしているKさんは,各部から出された利用予定をもとに,時間ごとに体育館を利用する部がいくつあるかを調べることにした。
各部の利用予定は,体育館に入る開始時刻と,体育館を出る終了時刻で表す。時刻はどれも「9時」「13時」のような整数である。Kさんは,9時から始まる1時間,10時から始まる1時間,……のように1日を1時間ずつに区切り,それぞれの1時間に体育館を利用する部の数(以下,部の数と呼ぶ。)を,次の規則で数えることにした。
表1は,ある土曜日の利用予定である。部には1から順に番号を付けてある。
| 部の番号 | 部1 | 部2 | 部3 | 部4 | 部5 | 部6 |
|---|---|---|---|---|---|---|
| 部の名前 | バスケットボール部 | バレーボール部 | 卓球部 | バドミントン部 | ハンドボール部 | 剣道部 |
| 開始時刻 | 9時 | 10時 | 11時 | 13時 | 14時 | 15時 |
| 終了時刻 | 12時 | 13時 | 14時 | 16時 | 17時 | 17時 |
例えば,11時から始まる1時間は,部1・部2・部3の三つが利用しているので,部の数は3である。12時から始まる1時間は,部1が12時に体育館を出るので部1を数えず,部2と部3だけを数えて部の数は2である。同じように数えると,13時から始まる1時間の部の数はア,15時から始まる1時間の部の数はイである。
Kさんは,この規則を不等号で書き表しておくと,後でプログラムにするときに便利だと考えた。
Kさんは,9時から16時までの各時刻について部の数を求め,部の数が最も多い時刻と,そのときの部の数を表示するプログラムを作成した(図1)。体育館は17時に閉めるので,調べる時刻は16時までとした。
(01)行目と(02)行目の配列 Kaishi,Shuryou には,表1の各部の開始時刻と終了時刻を,部の番号の順に格納する。配列の添字は1から始まり,部の番号を表す。例えば,Kaishi[3] は部3(卓球部)の開始時刻11,Shuryou[3] は部3の終了時刻14である。(03)行目では,部がいくつあるかを関数「要素数」で求めて,変数 busu に代入する。
X が [12, 5, 7] のとき,要素数(X)は3を返す。変数 saidai には,それまでに調べた時刻の部の数のうちで最も多いものを入れることにし,(04)行目で0を代入しておく。(05)〜(12)行目の繰り返しでは,変数 jikoku を9から16まで1ずつ増やしながら,その時刻について二つの処理を行う。
一つ目は(06)〜(09)行目で,部の数を数える変数 kazu を0にしてから,部1から部 busu まで順に問1の条件が成り立つかを調べ,成り立つ部があるたびに kazu を増やす。例えば jikoku が12のときは,部2と部3で条件が成り立つので,kazu は2になる。二つ目は(10)〜(12)行目で,kazu をそれまでの最も多い部の数 saidai と比べ,必要であれば saidai を書き換えるとともに,そのときの時刻を変数 saijikoku に記録する。部の数が最も多い時刻が二つ以上ある場合には,その中で最も早い時刻を表示することにした。
図1のプログラムを実行すると,「11時からの1時間:3部」と表示された。Kさんは,11時から始まる1時間は,コートを二つに仕切っても,三つの部のうち二つの部が一つのコートを分け合わなければならないことに気づいた。
Kさんは,図1の結果を,体育館の管理を担当している先生に見せた。
Shuryou の代わりに利用時間数の配列を使うように書き換えます。Kさんは,表1の予定を開始時刻と利用時間数で表し直して,図2のプログラムを作成した。(02)行目の配列 Jikan には,部の番号の順に各部の利用時間数を格納する。例えば,部6は15時から17時まで利用するので,Jikan[6] の値は2である。変数 jikansu は,部の数が3以上となる時刻の個数,すなわち3部以上が重なる時間が何時間あるかを表す。
図2の(09)行目では,jikoku が,部 i が最初に利用する1時間の始まりの時刻以上で,かつ,部 i が最後に利用する1時間の始まりの時刻以下であるかを調べる。(11)行目と(12)行目では,部の数が3以上のときに jikansu に1を加える。(13)行目では,関数「最大値」を用いて saidai を更新する。
図2のプログラムを実行すると,「3部以上の時間:2時間 最大:3部」と表示された。最も多い部の数は,図1の結果と一致した。
次にKさんは,別の土曜日の利用予定でも調べることにした。この日に体育館を利用するのは五つの部である。図2の(01)行目と(02)行目を次のように変更して実行すると,「3部以上の時間:3時間 最大:4部」と表示された。このとき,(10)行目は全部でシス回実行されている。
Kさんは,3部以上が重なる時間について,練習の時間を少しずらしてもらえないか,各部の部長に相談した。その結果,ある部が開始時刻を1時間遅らせてくれることになり,予定を組み直したところ,3部以上が重なる時間を減らすことができた。