読者です 読者をやめる 読者になる 読者になる

Codeforces Technocup F: Dirty plates

概要

スタックが3こある

1 -> 2はa個まで一気に運べて、2 -> 3はb個まで一気に運べる。sortできるか?

解法

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

空白

まず、愚直にシミュレーションすることを考える

一番重要な事実は、2個目のスタックは常に2重階段みたいになっているということ

つまり、2個目のスタックを前から見ていくと、値が減るか、もしくは1増えるかしかない(これを想像すると2重階段というのが伝わってくれると信じます)

すると、かなり正しい操作というのは少ないのでは?という気持ちになる

なんと驚くことに、場合分けをすると次する操作が一意に定まることが示せて、適当に実装してもO(N2)になる。

場合分けの詳細は省く、僕は12パターンになった。(177行 3547byte)

頑張って全てのパターンに対し正確な実装を行えば通すことができる。