geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Begginer Contest 265 E - Warp (兼参加記録)

コンテスト中AC:A〜D
A〜Dで特に書くことがないので、コンテスト後に解いたE問題について書いておきます(解説AC)。

問題
E - Warp

公式解説
Editorial - AtCoder Beginner Contest 265

コンテスト中に考えていた誤りの解法

コンテスト中は、全体の移動方法から、壁に経由する移動方法を引こうと思いました。
まず、全体の移動方法は3^Nです。

次に、壁を経由する移動方法を考えます。 ワープの方法を上から移動1,2,3と呼ぶことにします。

原点から移動1をp回、移動2をq回、移動3をr回行った後に到達する座標を(s,t)とすると、

s = pA+qC+rE
t = pB+qD+rF

という風に計算でき、一意に決定されます。

この座標が壁であるとした時に、(0,0)から前述の移動回数で(s,t)を通るような移動方法が何通りあるか数え上げてみます。

まず、(0,0)から(s,t)に移動する方法の総数ですが、それぞれp個、q個、r個ある3種類のボールを1列に並べる方法の総数に等しいので、

\frac{(p+q+r)!}{p!q!r!}

通りです。
(s,t)に到着後の残りは、どのような移動方法をとってもよいので、3^{N-p-q-r}通りです。

従って、求めたい移動方法の総数は、

\frac{(p+q+r)!}{p!q!r!}\times 3^{N-p-q-r}

です。
あとは、p,q,rを全探索して、上記を計算し、全体から引いていけば良い、と思いましたが、これは 誤りです。

なぜなら、(s,t)の他にも壁を通過している可能性があるため、重複して数え上げている可能性があるからです。

正しい解法

公式解説を参考に、座標ではなく各移動方法の移動回数を情報として持った、メモ化再帰で解きました。

f(p,q,r):移動1をp回、移動2をq回、移動3をr回行った場合の移動方法の総数

とおきます。

f(p,q,r) = f(p-1,q,r)+f(p,q-1,r)+f(p,q,r-1)

という式でf(p,q,r)を計算できるので、f(N,N,N)から開始してメモ化再帰することで、O(N^3)で全て計算できます。

p+q+r=Nとなるようなf(p,q,r)を全て足せばそれが答えとなります。

操作回数が同じなら辿り着く座標が同じであることから状態がO(N^3)と少ないことがポイントでした。

https://atcoder.jp/contests/abc265/submissions/34257627