sf(n)の値は以下の通り。ROOT_MAXはMAXの平方根。2以上、MAXまでの素因数の和が格納される。使えるカセットテープの長さ(録音時間)と、録音したい曲のリストが与えられ、すべての曲が入るだけの、最も短いカセットテープを探せ。実例を見たほうが分かりやすい。3本のテープが使える。録音時間はそれぞれ56,90,120分。出力結果を見てみよう。詳しいことは問題文に述べてないので、常識的に考えて問題を解いてみた。録音時間の長いカセットテープは120分だと思う。それはA面+B面での録音時間。片面ではその半分しか録音できない。曲の数は最大30とした。本問題にBFS(幅優先探索)を使った。QUE;と定義し、1曲目はA面録音として、2曲目以降はA面に、またはB面に録音するように探索キューを展開していく。n曲目においては、検索キューに存在しているn-1曲目までの組合せすべてに対し、次の操作を経て、再びキューに入れる。*/すべての曲の探索キューを作成した後、短いテープの順に、A面もB面も録音時間に収まるものが探索キューにあるかどうかを調べる。感想DPによる方法も考えてみたが、配列はとてつもなく大きいので断念した。今回のBFS探索法は強引的な面もあったが、実行時間がゼロ秒になっているので、本問題に使えることは間違いなさそう。