1. 問題
 使えるカセットテープの長さ(録音時間)と、録音したい曲のリストが与えられ、すべての曲が入るだけの、最も短いカセットテープを探せ。

2. 実例
 実例を見たほうが分かりやすい。

56 90 120 ← 3本のテープが使える。録音時間はそれぞれ56,90,120分。
20m 44s ← ここからは曲のリスト(m:分、s:秒)
4m 36s
7m 18s
13m 8s
9m 6s
8m 12s
% ← 入力の終了

出力結果を見てみよう。

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曲目までの組合せすべてに対し、次の操作を経て、再びキューに入れる。

que[y].no = n;  /* n番目の曲 */
que[y].side = 'A';  /* A面に録音する */
que[y].a = que[x].a + recordTimen;  /* 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 + recordTimen;  /* B面での録音時間 */
que[y+1].prev = x;  /* 前へのポインタ */

すべての曲の探索キューを作成した後、短いテープの順に、A面もB面も録音時間に収まるものが探索キューにあるかどうかを調べる。

4. 感想
 DPによる方法も考えてみたが、配列はとてつもなく大きいので断念した。今回のBFS探索法は強引的な面もあったが、実行時間がゼロ秒になっているので、本問題に使えることは間違いなさそう。

Comments are closed.

Post Navigation