ABC216 D - Pair of Balls
https://atcoder.jp/contests/abc216/tasks/abc216_d
コンテスト中はシミュレーションすることで解答を求めたのですが、 トポロジカルソートで解けるというツイートも見たので考察しました。
解説
ある筒の中に上から { x, y, z } とボールが入っていたとします。 このとき、(各色のボールは2つしかないため)zを取り出すためにはyを取り出す必要があり、yを取り出すためにはxを取り出す必要があります。 したがって、x -> y -> zという依存関係があることになります。 これを全ての筒について見ていくと、依存関係のグラフを構築することができます。
全てのボールが取り出せるかどうかは、この依存関係のグラフがトポロジカルソート可能であるかと同値になります。 したがって、入力からグラフを構築し、トポロジカルソートを試してみることで解答がわかります。