競技プログラミング用 知識集積所
ARC200C - Movie Theater
最終更新：
sport_programming
-
view
問題
必要知識
簡単な内容は省略
- 特になし
考え方
とりあえず、2人だけの場合で考えてみる。
| できごとの順 | Aが右の場合の不満度 | Bが右の場合の不満度 | |||
|---|---|---|---|---|---|
| A来る | A帰る | B来る | B帰る | 0 | 0 |
| A来る | B来る | A帰る | B帰る | 1 | 1 |
| A来る | B来る | B帰る | A帰る | 0 | 2 |
できごとの順は実質この3パターンしかなく、しかも、うち2つはAとBがどう座ろうとも不満度は変化しない。
つまり、A来る、B来る、B帰る、A帰るの順になっている場合にのみ必ずAを右の席に座らせるようにすればよく、他は普通に辞書順最小を作ればよい。
つまり、A来る、B来る、B帰る、A帰るの順になっている場合にのみ必ずAを右の席に座らせるようにすればよく、他は普通に辞書順最小を作ればよい。
では、3人以上の場合。
この場合、まずは同じように、A来る、B来る、B帰る、A帰るの順になっている人間関係を探す。
例えば入力例の3つめの場合、
この場合、まずは同じように、A来る、B来る、B帰る、A帰るの順になっている人間関係を探す。
例えば入力例の3つめの場合、
- 人1は人2より左
- 人1は人6より左
- 人3は人1より左
- 人3は人2より左
- 人3は人4より左
- 人3は人6より左
- 人5は人2より左
- 人5は人4より左
という関係があることを見つける。
あとは、これを満たす席番号の辞書順最小を見つければいい。
あとは、これを満たす席番号の辞書順最小を見つければいい。
人1から考える場合、「人1より左にいなきゃいけない人が1人いるので、人1は席2」とできる。
しかし、次に人2を考えるときに、「人2より左にいなきゃいけない人が3人いる」まではいいが、そこからが問題。
それぞれの人が人1の左にいなきゃいけないのかそうでもないのかを考えなければならず、処理が大変になっていく。
しかし、次に人2を考えるときに、「人2より左にいなきゃいけない人が3人いる」まではいいが、そこからが問題。
それぞれの人が人1の左にいなきゃいけないのかそうでもないのかを考えなければならず、処理が大変になっていく。
そこで、席6から考えることにする。
席6に座ってもいい人は人2と人4と人6なので、人6を座らせる。
席5に座ってもいい人は人2と人4なので、人4を座らせる。
席4に座ってもいい人は人2だけなので、人2を座らせる。
席3に座ってもいい人は人1と人5なので、人5を座らせる。
席4に座ってもいい人は人1だけなので、人1を座らせる。
席4に座ってもいい人は人3だけなので、人3を座らせる。
席6に座ってもいい人は人2と人4と人6なので、人6を座らせる。
席5に座ってもいい人は人2と人4なので、人4を座らせる。
席4に座ってもいい人は人2だけなので、人2を座らせる。
席3に座ってもいい人は人1と人5なので、人5を座らせる。
席4に座ってもいい人は人1だけなので、人1を座らせる。
席4に座ってもいい人は人3だけなので、人3を座らせる。
これは、次に座ってもいい人の一覧をpriority_queue（未作成）で持っておき、1人座るごとにもう考えなくていい制約を消していくと実現できる。
