AOJ 0033 Ballの解法
問題
問題URLはこちら 玉 | Aizu Online Judge
こんな問題でした(図はリンク先を参照してください)
図のように二股に分かれている容器があります。1 から10 までの番号が付けられた10 個の玉を容器の開口部 A から落とし、左の筒 B か右の筒 C に玉を入れます。板 D は支点 E を中心に左右に回転できるので、板 D を動かすことで筒 B と筒 C のどちらに入れるか決めることができます。開口部 A から落とす玉の並びを与えます。それらを順番に筒 B 又は筒 Cに入れていきます。このとき、筒 B と筒 C のおのおのが両方とも番号の小さい玉の上に大きい玉を並べられる場合は YES、並べられない場合は NO と半角大文字で出力して終了するプログラムを作成してください。ただし、容器の中で玉の順序を入れ替えることはできないものとします。また、続けて同じ筒に入れることができるものとし、筒 B, C ともに10 個の玉がすべて入るだけの余裕があるとします。
解法
筒Bと筒Cで条件に入る方に入れつつ、一番上のボール(=最大値)を更新って感じのコードを書きました。どちらも条件を満たしている時、適切な方にボールを入れる処理が必要だと思ったのですが、筒Bに優先的に入れるようにコード書いてSubmitしてみたら、一発でAcceptいただきました。
常に大きいボールが筒Bに入る
今回の問題では同じ数は存在しないため、筒Bに入るボールは既に筒Bに入っているボールより大きなボール、筒Cに入るボールは既に筒Bに入っているボールより小さなボールとなります。
つまり、新しく入るボールは大きな値から判定をしていることになるため、常に最適な筒にボールが入っていることになっていました。
