yukicoder contest 391 - F : Factorial Paths

問題

$(1,1)$ から $(H,W)$ 経路数が $N!$ となるような $H\times W$ のグリッド（ $H,W\leq 2000$ ）を求めよ．

解法

本解説と違ったので書く．

下の図のような感じで，経路数が $n$ となるようなできるだけ小さいグリッドを用意して，それらを左上から順に並べるようにする．

以下のような条件のもとでグリッドを全探索をして，それぞれの経路数を求めたところ， $400$ 以下の各正整数 $k$ に対して，経路数が $k$ となるようなものが見つかった．

サイズが $h\times w (2\leq w\leq h\leq 7)$
黒マスが $5$ 個以下

経路数が同じものが複数個見つかったときは，そのうち $(h,w)$ が最小になるものを採用した． $k\leq 10$ はこんな感じ

1
..
#.

2
..
..

3
...
...

4
..#
...
#..

5
..#
...
...

6
...
...
...

7
....
....
.#..

8
...#
....
#...

9
....
....
#...

10
....
....
....

得られた $400$ 個の長方形のサイズの度数分布はつぎのようになった．

(2, 2): 2
(2, 3): 1
(3, 3): 3
(3, 4): 4
(4, 4): 9
(4, 5): 15
(4, 6): 4
(5, 5): 27
(5, 6): 55
(5, 7): 4
(6, 6): 109
(6, 7): 166
(7, 7): 1

これらを縦横の長さが均等になるように反転させたりしてつなげると， $N=400$ のときに $(H,W)=(1955,1956)$ が構築できた．

最後に $N=10$ の場合のグリッドを示す．

..###################
#..##################
#....################
##....###############
####...##############
#####...#############
######...############
######.....##########
########...##########
########.....########
##########..#########
##########...########
##########.....######
############....#####
#############....####
###############...###
###############...###
###############......
#################....
#################....