ABC271F 精進メモ - こゃーその雑記

コンテスト中にTLE解法を投げていた。

成約が小さいので全探索できそうな雰囲気を感じる。が、本当に全探索してしまうと、 ${}_{2(N - 1)} C_{N - 1}$ 通り、 $N = 20$ なら約 $3.5 × 10^{10}$ 通りあるため、間に合わない。

そこで、スタートとゴール*1から半分ずつに分けて、真ん中まで全探索させてみる（半分全列挙）。この場合、スタートからN-1回だけ進んだ真ん中までの通り数は約 $2^{N -1} \le 2^{19} = 5.2 × 10^5$ 通りなので、これは列挙できる。

スタートとゴールから辿ったものが出揃った後、「マス(i, j)で値がaになる」場合の数を辞書で管理しておけば、 $O(1)$ で参照することができるため、「スタート→マス(i, j)までの通り数」×「マス(i, j)→ゴールまでの通り数」を足し上げて行けばOK。

ちなみに、対称的に実装すると真ん中のマスについて、両方で考慮される or されないになるが、適宜マスの値の排他的論理和を取ってあげて調整すればOK。

*1:反対から辿っても同じ結果になるため、「ゴールから左か上に移動する」として計算する