AOJ #0033 Ball (玉)
問題の概要
問題文: AIZU ONLINE JUDGE #0033 Ball (玉)
最初に与えられた1数値の入った10個の玉を、2つの筒に順に振り分ける問題。
振り分ける際に、各筒の最上部の玉の値より大きくなければならないとした時、振り分けられるかどうかを判定する。
解答例
1. 貪欲法(グリーディー法; greedy algorithm)を用いた解法
1つ目の玉から順に見ていき、筒B→筒Cの順番で入れられる時点で入れていく方針。 この時、各筒の最上部の値を確認すると、筒Cより筒Bの方が値が常に大きくなる。 どちらの筒にも玉を入れられる時には、常に値の大きい筒Bの方に入れることとなるため、筒Cの値を常に最小の値にし続けることができる。
2. 全探索を用いた解法
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[]に保持している現在の各筒の一番上の玉の値と比較し、それより小さかった場合は満たさないため次の状態へ移行している。
3. その他の解説サイト
- [貪欲法版] Ball (AOJ 0033) by Respect2D
- [再帰関数版DFS] aoj 0033 - Ball - srupのメモ帳
- [スタック版DFS] AOJ 0033 Ball - 無気力な大学生の痴れ事
- [Bitを利用した二分木に対する全列挙] AOJ 0033 - Ball - ゴリラ系情報系男子高校生の日記
総評
基本的な問題のため、様々な解法がある。 競技プログラミング初心者にとって、うってつけの練習問題だと思う。
以上のソースコードは以下のGithub上にて参照可能です。 https://gist.github.com/farma11/c34af9de7c9a184dc7a0a576455851f1