問題
atcoder.jp
提出解答
atcoder.jp
問題の概要
行 
列のマスがある. 上から 
列目, 左から 
列目のマスを 
と呼ぶ.
には整数 
が書かれている.
高橋くんは 
にいる. 高橋くんは以下の行動を繰り返して, 
を目指す.
- (存在する) 左隣のマスか (存在する) 下隣のマスに移動する.
高橋くんの移動の方法のうち, 
を含めた高橋くんが通ったマスに書かれている整数が全て異なるような移動の方法の数を求めよ.
制約
解法
このような移動は下の移動を 
回, 右の移動を 
回行うとマス に到達できる. また, に到達できる方法は下の移動を 回, 右の移動を 回することである.
よって, 合計 
回の移動の方法のうち, 下に移動する 
回がいつかを指定し, 実際にそのような移動の方法は条件を満たすかどうかを調べれば良い.
見るべき経路の数は
であり, これは最大で 
のときの 
通りであり, 各経路に関して 
時間で判定できる.
よって, 
時間で数え上げることができる.
