\(N\) が奇数の場合には，公式解説の方法が最大長の trail を与えることが証明できます．

グリッドの上三角領域内に最大長の path をとる問題に言い換えます．行番号，列番号が適当な parity にあるマスに注目し，そのような点を特殊マスと呼びましょう．

\(4\) 回に \(1\) 回は特殊マスを通らなければいけないことから，公式解説の方法で作った path が最大長であることが確認できます．詳細は次の図を見ながら考えてみてください．

\(N=13\) の図．

偶数 \(N\) の場合については，公式解説の方法が最大長であるか否かは私は短時間では証明できませんでした．何か分かったらぜひ教えてください．（yukicoder No.540「格子点と経路」 などと似た設定なので簡潔に証明できる可能性もあるのではないかと思っています．）