UVa #778 – Recording a tape

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探索法は強引的な面もあったが、実行時間がゼロ秒になっているので、本問題に使えることは間違いなさそう。