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

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

出力結果を見てみよう。

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

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

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

Comments are closed.

Post Navigation