AtCoder Begginer Contest 265 E - Warp (兼参加記録)
コンテスト中AC:A〜D
A〜Dで特に書くことがないので、コンテスト後に解いたE問題について書いておきます(解説AC)。
問題
E - Warp
公式解説
Editorial - AtCoder Beginner Contest 265
コンテスト中に考えていた誤りの解法
コンテスト中は、全体の移動方法から、壁に経由する移動方法を引こうと思いました。
まず、全体の移動方法はです。
次に、壁を経由する移動方法を考えます。 ワープの方法を上から移動1,2,3と呼ぶことにします。
原点から移動1を回、移動2を回、移動3を回行った後に到達する座標をとすると、
という風に計算でき、一意に決定されます。
この座標が壁であるとした時に、から前述の移動回数でを通るような移動方法が何通りあるか数え上げてみます。
まず、からに移動する方法の総数ですが、それぞれ個、個、個ある3種類のボールを1列に並べる方法の総数に等しいので、
通りです。
に到着後の残りは、どのような移動方法をとってもよいので、通りです。
従って、求めたい移動方法の総数は、
です。
あとは、を全探索して、上記を計算し、全体から引いていけば良い、と思いましたが、これは
誤りです。
なぜなら、の他にも壁を通過している可能性があるため、重複して数え上げている可能性があるからです。
正しい解法
公式解説を参考に、座標ではなく各移動方法の移動回数を情報として持った、メモ化再帰で解きました。
:移動1を回、移動2を回、移動3を回行った場合の移動方法の総数
とおきます。
という式でを計算できるので、から開始してメモ化再帰することで、で全て計算できます。
となるようなを全て足せばそれが答えとなります。
操作回数が同じなら辿り着く座標が同じであることから状態がと少ないことがポイントでした。