問題の概要

問題文: AIZU ONLINE JUDGE #0033 Ball (玉)
　最初に与えられた1数値の入った10個の玉を、2つの筒に順に振り分ける問題。振り分ける際に、各筒の最上部の玉の値より大きくなければならないとした時、振り分けられるかどうかを判定する。

解答例

1. 貪欲法（グリーディー法; greedy algorithm）を用いた解法

　1つ目の玉から順に見ていき、筒B→筒Cの順番で入れられる時点で入れていく方針。この時、各筒の最上部の値を確認すると、筒Cより筒Bの方が値が常に大きくなる。どちらの筒にも玉を入れられる時には、常に値の大きい筒Bの方に入れることとなるため、筒Cの値を常に最小の値にし続けることができる。

2. 全探索を用いた解法

筒は2本、玉は10個しかないため全組合せでも $2^{10} = 1024$ 通りしかない。したがって、全探索を用いても速度的な問題は一切ない。

2.1 深さ優先探索（DFS: Depth-First Search）を用いた解法（再帰関数版）

　配列balls[]に入力された玉の順序が格納されており、それを引数idxによって順に指定し、条件を満たす限り再帰を続けている。引数b,cは筒B,Cそれぞれの最上部の玉の数値を保持しており、それよりballs[idx]が大きければ問題の条件をみたす。筒BまたはCのいずれかでも成り立つことが分かった場合、trueを返し、どちらも満たさなければfalseを返すようになっている。

2.2 深さ優先探索（DFS: Depth-First Search）を用いた解法（スタック版）

　現在の状態として現在取り扱っている玉のidxと、筒B,Cの最上位の玉の値を tuple<int, int, int> より表現している。それらの状態をスタック stack<tuple<int, int, int> > states に積むことでそれぞれの状態を格納している。条件を満たす限り筒に玉を入れていき、最後まで入れることができる状態が一つでもあれば探索を終了し、YESを出力している。また全ての状態を探索し、どの状態についても最後まで入れることができなかった場合はループを終了し、NOを出力している。

2.3 Bitを利用した二分木に対する全列挙を用いる解法

　10個の玉を筒BとCへ順番に入れていき、現在の各筒の一番上の玉より値が大きいかどうかを確認するという手法で実装している。どの玉をどちらに入れるかは変数bitの2進数によるフラグを利用し、0は筒Bを、1は筒Cを意味している。配列top[]に保持している現在の各筒の一番上の玉の値と比較し、それより小さかった場合は満たさないため次の状態へ移行している。