EDPC Y - Grid 2

グリッド2

考え方

ABCでいうと、F問題級。

壁を通らない道順は、全ての通り方から壁を少なくとも $1$ つ通る道順を引けばよい。
それは包除原理より、以下でよい。

全道順
- 指定の壁1つを通る（他は不問）道順×その壁の指定のパターン数分
+ 指定の壁2つを通る（他は不問）道順×その壁の指定のパターン数分
- 指定の壁3つを通る（他は不問）道順×その壁の指定のパターン数分
+ ……

これをもう少しまとめると

指定の壁偶数個を通る（他は不問）道順×その壁の指定のパターン数分
- 指定の壁奇数個を通る（他は不問）道順×その壁の指定のパターン数分

でよいことがわかる。

そこで、スタートとゴールと壁をまとめて注目点としたうえで、各点について以下を求めればよい。

前者は、自分より左上にある全ての点の、「その点までの奇数個の道順 $\times$ その点からの道順」の合計。
その点からの道順は、Comb(移動回数, 右への移動の回数) でよい。
後者も同様。
これで、ゴールマスについて前述の計算をすればよい。

計算量は $O(N^2)$。

入力を受け取る。

h: 3
w: 4
n: 2
壁:
  (2, 2)
  (1, 4)

スタートとゴールと壁をまとめて注目点とし、座標順にソートする。

vec[0]: (1, 1) スタート
vec[1]: (1, 4) 壁
vec[2]: (2, 2) 壁
vec[3]: (3, 4) ゴール

odd[i] を、スタートから vec[i] まで、注目点を奇数個通る道順の総数とする。
even[i] を、スタートから vec[i] まで、注目点を偶数個通る道順の総数とする。

スタートからスタートへの道順は、明らかに奇数個が $1$ 通り、偶数個が $0$ 通り。

odd[0] = 1
even[0] = 0

vec[1] の注目点 (1, 4) までの道順を求める。

vec[0] から vec[1] へは、右に $3$ 回進むだけなので $1$ 通りである。
vec[1] に到着すると、通った注目点の個数の偶奇が入れ替わる。

Comb(3, 3) = 1

even[1] = odd[0] * 1 = 1
odd[1] = 0

vec[2] の注目点 (2, 2) までの道順を求める。

vec[0] から vec[2] へは、下に $1$ 回、右に $1$ 回進むので $2$ 通りである。
vec[1] から vec[2] へは左に戻る必要があるため、移動できない。

Comb(2, 1) = 2

even[2] = odd[0] * 2 = 2
odd[2] = 0

最後に、vec[3] の注目点 (3, 4) までの道順を求める。
これはゴールである。

vec[0] から直接ゴールへ行く道順は、下に $2$ 回、右に $3$ 回進むので $10$ 通りである。

Comb(5, 3) = 10

even[3] += odd[0] * 10
        = 10

vec[1] からゴールへ行く道順は、下に $2$ 回進むだけなので $1$ 通りである。

Comb(2, 0) = 1

odd[3] += even[1] * 1
       = 1

vec[2] からゴールへ行く道順は、下に $1$ 回、右に $2$ 回進むので $3$ 通りである。

Comb(3, 2) = 3

odd[3] += even[2] * 3
       = 6

よって、ゴールでは次の値になる。

even[3] = 10
odd[3] = 1 + 6 = 7

包除原理より、答えは偶数側から奇数側を引いた値である。

even[3] - odd[3] = 10 - 7 = 3

よって答えは $3$ である。

特になし。

特になし。