Codeforces Technocup F: Dirty plates
概要
スタックが3こある
1 -> 2はa個まで一気に運べて、2 -> 3はb個まで一気に運べる。sortできるか?
解法
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
空白
まず、愚直にシミュレーションすることを考える
一番重要な事実は、2個目のスタックは常に2重階段みたいになっているということ
つまり、2個目のスタックを前から見ていくと、値が減るか、もしくは1増えるかしかない(これを想像すると2重階段というのが伝わってくれると信じます)
すると、かなり正しい操作というのは少ないのでは?という気持ちになる
なんと驚くことに、場合分けをすると次する操作が一意に定まることが示せて、適当に実装してもO(N2)になる。
場合分けの詳細は省く、僕は12パターンになった。(177行 3547byte)
頑張って全てのパターンに対し正確な実装を行えば通すことができる。