I hate Bishop (Very Hard)

$N$が偶数の場合は、"I hate Bishop"の解説を参照してください。 以下、"I hate Bishop"の解説の内容を前提として述べます。 https://mojacoder.app/users/riano/problems/repetition-draw/editorial

結論を先に述べると、$N=7$のとき$8$、$N=9$のとき$9$、$N \geq 11$かつ$N$が奇数のとき$N-1$が答えです。

偶数の場合との違いは、「先手が後手よりも広い自陣を確保しうる」という一点です。 先手の自陣が後手よりも狭い場合は偶数の場合の考察をそのまま適用できますので、 以下、先手のポーンが$k=\frac{N+1}{2}$マス目に置かれる場合に絞って、双方の最善手を求めましょう。

以下、先手のルークの位置、後手のルークの位置をそれぞれのプレイヤー側から、$1,2,3...$とマスに番号を付け、 例えば、先手のルークが一番先手側のマス、後手のルークが後手から見て手前から$2$番目のマスにあるような状況を$(1,2)$と表します。

$N$が偶数の場合の進行は、$(1,1)$→$(2,2)$→...→$(n,n)$でした。 （先手が最後にポーンを動かした後、後手がルークを動かす場合には実際に$(1,1)$という配置で先手番にはなりませんが、マスにどう名づけても本質的な差異はないため問題はありません。） この後、先手は$1～n-1$マス目のいずれかのマスにルークを戻し、 後手も同じ動きをすること「千日手」が成立します。しかし、今回同じような進行をすると、（先手側の「自陣」が$n+1$マスとして）$(n,n)$ の次に例えば$(n+1,1)$のように、後手はマスが足りないため、今までルークを移動したことのある場所に戻す必要が出てきます。 この時、先手はルークを$1$マス目に動かします。後手の着手後に$(1,1)$であれば千日手の成立ですが、後手はパスが出来ないため、ルークを動かさざるを得ず、 この手で千日手を成立させることが出来なくなってしまいます。このように、先手は後手のルークの動きに「対応するマス」にルークを動かせば、安全にゲームを続けることが出来る状況が生まれます。その後は$(1,2)$→$(2,1)$→$(n+1,2)$→$(3,3)$が部分的な最善手となり、ポーンが向かい合ってから$n+5$手でゲームは終了します。

実は、$n\geq 4$の場合、最善の手順は次のようになります。

$(1,1)$→$(2,2)$→$(3,1)$→$(1,3)$→$(4,4)$→...→$(n,n)$→$(n+1,3)$

この後、先手はどこにルークを戻しても、後手の着手によってゲームが終了します。直感的には、先ほどの手順で後手が「ルークを$1$に戻す」時に 先手に$1$という「安全なマス」を与えてしまった状況を、先回りして潰しておく手順です。すなわち、最後の状況で先手は、後手の$3$に対応するマスにルークを動かせれば安全なはずですが、 $3$に対応するマスは$1$であり（$3$手目の後が$(1,3)$となっています）、$1$は既に$2$回訪れたために、後手は$(1,3)$とはできなくても$(1,1)$としてゲームを終了させることが出来る状況になっています。

この手順は$n+2$手で終了します。この手順より良い手順が無いか検証をしましょう。先手にとっては、$(3,1)$のタイミングで$1$に戻らない選択肢があります（それ以外の手は、ほぼ自殺手になるため選択の余地がありません。）が、 それをしてしまうと$(3,1)$→$(4,3)$→$(5,4)$→...→$(n+1,n)$という進行で$1$手早くゲームが終了します。また、後手にとってこの手順が最善であることは、 「$n+1$手で終了する手順が不可能」であることと、$n+2$手で終了する手順が実際に構築できていることから結論付けられます。「$n+1$手で終了する手順が不可能」であることは、 先手のルークが$1～n+1$のマスを動く間、後手は必ず$1$度は「同じマスを$2$度踏む」必要があり（鳩ノ巣原理）、その瞬間、先手も「対応するマスにルークを戻す」ことで、 最低$1$回は「同じマスを$2$度踏む」ことが可能であることより示せます。

以上より、$g(\frac{N+1}{2}) = n+2 = \frac{N+1}{2}$（$N\geq 11\Leftrightarrow n\geq 4$）となります。 （$g(k)$や、後の$f(k)$の意味は"I hate Bishop"の解説を参照してください。先手のポーンが$\frac{N+1}{2}$マス目の時、先手の自陣は$\frac{N+1}{2}-1$マスです。) また、この場合には、先手は一直線にポーンを進めないと後手より広い自陣を確保することは不可能であるため、 $f(\frac{N+1}{2}) = \frac{N+1}{2}-2$です。従って、この時$f(\frac{N+1}{2}) +g(\frac{N+1}{2}) = N-1$であり、 これは他の$k$（ポーンの位置）を選ぶより先手にとって$1$手得であるため、今回の問いの答えとなります。

$n=2,3$の場合は、順に下記の手順が双方にとって最善です（ともに$6$手です）。

$(1,1)$→$(2,2)$→$(3,1)$→$(1,2)$→$(2,1)$→$(3,2)$→$(1,1)(n=2)$

$(1,1)$→$(2,2)$→$(3,1)$→$(1,3)$→$(4,1)$→$(3,3)$→$(1,1)(n=3)$

これらの手順は、分岐を丁寧に検証することで最善であることが示せます。なお、ここまでの考察で無視してきた事実が$1$つ存在しています。それは、本来ルークを最初に動かすのは（今回考えている場合では）後手番であるため、 後手に手が回った時に$(1,x)$（$x$は$1$以外で任意）である局面が実は上記の手順を始める前から既出である、という事実です。しかし、先手が自ら$1$にルークを動かすのは後手が$1$にルークを動かしたときのみでよいため、 この局面が原因となってゲームが終了することは（$n=2$以外では）ありません。$n=2$の場合のみ、上の記述はやや不正確です（後手番の最後の$(1,1)$の直前に実はゲームが終了します）が、先手の手数は同じです。

以上の考察を全てまとめると、 $N=6$のとき$3$、$N=7$のとき$8$、$N=9$のとき$9$、$N \geq 8$かつ$N$が偶数のとき$N-2$、$N \geq 11$かつ$N$が奇数のとき$N-1$が答えです。