1. 問題
使えるカセットテープの長さ（録音時間）と、録音したい曲のリストが与えられ、すべての曲が入るだけの、最も短いカセットテープを探せ。
2. 実例
実例を見たほうが分かりやすい。
|
1 2 3 4 5 6 7 8 |
56 90 120 ← 3本のテープが使える。録音時間はそれぞれ56,90,120分。 20m 44s ← ここからは曲のリスト（m:分、s:秒） 4m 36s 7m 18s 13m 8s 9m 6s 8m 12s % ← 入力の終了 |
出力結果を見てみよう。
|
1 2 3 4 5 6 7 8 9 10 |
90 ← 90分のテープを使う Side A ← A面での録音 20m 44s ← 曲のリスト 4m 36s 7m 8s Side B ← B面での録音 13m 8s ← 曲のリスト 9m 6s 8m 12s % ← 出力の終了 |
3. 考え方
詳しいことは問題文に述べてないので、常識的に考えて問題を解いてみた。
一番録音時間の長いカセットテープは120分だと思う。それはA面＋B面での録音時間。片面ではその半分しか録音できない。また、曲の数は最大30とした。
本問題にBFS（幅優先探索）を使った。
構造体
typedef struct {
char no; /* 曲の通し番号 */
char side; /* A面かB面か */
int a, b; /* A面とB面の録音時間 */
int prev; /* 前へのポインタ */
} QUE;
と定義し、1曲目はA面録音として、2曲目以降はA面に、またはB面に録音するように探索キューを展開していく。
つまり、n曲目においては、検索キューに存在しているn-1曲目までの組合せすべてに対し、次の操作を経て、再びキューに入れる。
|
1 2 3 4 5 6 7 8 9 10 |
que[y].no = n; /* n番目の曲 */ que[y].side = 'A'; /* A面に録音する */ que[y].a = que[x].a + recordTime<sub>n</sub>; /* A面での録音時間 */ que[y].b = que[x].b; /* B面での録音時間 */ que[y].prev = x; /* 前へのポインタ */ que[y+1].no = n; /* n番目の曲 */ que[y+1].side = 'B'; /* B面に録音する */ que[y+1].a = que[x].a; /* A面での録音時間 */ que[y+1].b = que[x].b + recordTime<sub>n</sub>; /* B面での録音時間 */ que[y+1].prev = x; /* 前へのポインタ */ |
すべての曲の探索キューを作成した後、短いテープの順に、A面もB面も録音時間に収まるものが探索キューにあるかどうかを調べる。
4. 感想
DPによる方法も考えてみたが、配列はとてつもなく大きいので断念した。今回のBFS探索法は強引的な面もあったが、実行時間がゼロ秒になっているので、本問題に使えることは間違いなさそう。