　任意の正整数 $n$ は，ある非負整数 $k$ および $k+1$ 以下の正整数 $r$ によって 
$n = \dfrac{k(k+1)}{2} + r$ と一意に表される．この表示を用いると 
$$ \big( f(n), g(n) \big) = \big( k, k - 2(r-1) \big) $$ 
となるため，$xy$ 座標平面上に点 $Q_n \left( \dfrac{f(n)-g(n)}{2}, \dfrac{f(n)+g(n)}{2} \right) = (r-1, k-r+1)$ をとると，$Q_n$ は $x, y$ 座標がともに非負整数である点全体を網羅する．この $Q_n$ について以下が成り立つ．

**補題．** $M(a, b)$ は点 $Q_a$ と点 $Q_b$ のマンハッタン距離に等しい．ただし点 $(x, y)$ と点 $(x^\prime, y^\prime)$ のマンハッタン距離は $|x - x^\prime| + |y - y^\prime|$ で与えられる．

**証明．** 任意の実数 $p, q$ について
$$ \max(|p|, |q|) = \left | \dfrac{p-q}{2} \right | + \left | \dfrac{p+q}{2} \right | $$
が成り立つことに注意すると，$Q_a$ と $Q_b$ のマンハッタン距離
$$ \left | \dfrac{f(a) - g(a) - f(b) + g(b)}{2} \right | + \left | \dfrac{f(a) + g(a) - f(b) - g(b)}{2} \right | $$
と
$$M(a, b) = \max(|f(a) - f(b)|, \ |g(a) - g(b)|)$$ 
が等しいことがわかる．

　いま $Q_1 = (0, 0), \ Q_{100} = (8, 5)$ であり，また $2$ 点 $Q_p(a, b), Q_q(c, d)$ について  $a \leq c$ かつ $b \leq d$ ならば $p \leq q$ であることから，補題と合わせて問題は以下のように言い換えられる．

**問題．** 整数 $1 \lt n_1 \lt n_2 \lt \ldots \lt n_{11} \lt 100$ であって，$Q_{n_1}, \ \dots, \ Q_{n_{11}}$ をこの順に通るような $(0, 0)$ から $(8, 5)$ への最短経路が存在するものはいくつあるか．

　$(0, 0)$ から $(8, 5)$ までの最短経路上の点を辿る順に $(0, 0) = R_0, \ R_1, \dots, \ R_{13} = (8, 5)$ とする．$R_{i-1} R_{i} \perp R_{i} R_{i+1}$ のとき，$R_{i}$ を**角**と呼ぶことにする．このとき，各最短経路について，そこから $(0, 0), \ (8, 5)$ 以外の $1$ 点を除くことで条件を満たす相異なる $11$ 個の格子点の組が得られるが，除いた点が角だった場合に得られる $11$ 個の点の組は，異なるちょうど $2$ つの最短経路から得られてしまう．これより，全ての最短経路について角の個数の総和を $A$，$(0, 0), \ (8, 5)$ 以外の角でない点の個数の総和を $B$ とすると，求めるべき値は $\dfrac{A}{2} + B$ になる．ここで 
$$A + B = 12 \times {}\_{13}\mathrm{C}\_{5} = 15444$$ 
である．また，点 $(0, 0)$ から 点 $(8, 5)$ までの最短経路は「$x$ 軸方向に $1$ だけ右に進む移動」と「$y$ 軸方向に $1$ だけ上に進む移動」をそれぞれ $8, 5$ 回するような移動方法に一対一対応しており，角は「右，上」の順または「上，右」の順に移動している箇所に対応しているから，
$$A = 12 \times {}\_{11}\mathrm{C}\_{4} \times 2 = 7920$$ 
が分かる．これより，$B = 7524$ が従い，求めるべき値は $\mathbf{11484}$ となる．
公式解説
https://onlinemathcontest.com/contests/omc236/editorial/10507
　公式解説と同じように問題を言い換える（再掲しておく）．

**問題．**整数 $1 \lt n_1 \lt \cdots \lt n_{11} \lt 100$ であって，$ Q_{n_1}, \cdots , Q_{n_{11}}$ をこの順に通るような $(0,0)$ から $(8,5)$ への最短経路が存在するものはいくつあるか．

　普通の経路問題であれば，右への移動を $8$ 回，上への移動を $5$ 回，の計 $13$ 個の矢印の並び替えである．このとき始点・終点を除いて，通過する格子点は $12$ 個ある．従って，このうち $1$ 個を取り除けばよいことになる．\
　ここで，「格子点を $1$ 点取り除く」と考えているのが公式解説の方法だが，そうではなく「矢印を $1$ つ変化させる」と考えてみよう．すなわち，以下のように場合分けする．

- 右への移動を $6$ 回，右への長さ $2$ の移動を $1$ 回，上への移動を $5$ 回
- 右への移動を $8$ 回，上への移動を $3$ 回，上への長さ $2$ の移動を $1$ 回
- 右への移動を $7$ 回，上への移動を $4$ 回，右上方向への移動を $1$ 回

このように考えると求めるべき値は
$$\dfrac{12!}{6! \ 5!}+\dfrac{12!}{8! \ 3!}+\dfrac{12!}{7! \ 4!}=\mathbf{11484}$$
公式解説の途中からの別解
https://onlinemathcontest.com/contests/omc236/editorial/10507/726
　非負整数 $n$ に対し，$T(n) = \dfrac{n(n+1)}{2}$ と定義します．また，正整数 $n$ に対し，$n \gt T(x)$ を満たす最大の非負整数 $x$ を $f(n)$ で表し，
$$g(n) = f(n) + 2(T(f(n)) - n + 1)$$ 
と定めます．正整数 $a, b$ に対して
$$M(a, b) = \max(|f(a) - f(b)|, \ |g(a) - g(b)|)$$ 
と定義するとき，$1\lt n_1\lt n_2 \lt \cdots \lt n_{11}\lt 100$ をみたす正整数の組 $(n_1,n_2,\ldots, n_{11})$ について
$$M(1, n_1) + M(n_1, n_2) + \dots + M(n_{10}, n_{11}) + M(n_{11}, 100)$$
の最小値を $m$ とします．このとき，以下の条件を満たす $11$ 個の正整数の組 $(n_1, n_2, \dots, n_{11})$ の個数を解答してください．
- $1 \lt n_1 \lt n_2 \lt \dots \lt n_{11} \lt 100$
- $M(1, n_1) + M(n_1, n_2) + \dots + M(n_{10}, n_{11}) + M(n_{11}, 100) = m$