組 \((X,Y)\) の代わりにマス \((X,Y)\) にコマを置くと考えることで、問題を \(2\) 次元グリッド上にコマを置く問題と言い換えて考えます。

\(N \le M\) としても一般性を失いません。

\(3X_i + Y_i\) の最小値は \(4\)、最大値は \(3N+M\) であるため、\(3N+M-3\) が \(K\) の上界となることがわかります。また、\(N=M\) かつ \(N\) が偶数である時以外はこの上界が達成可能です。

まず、\(N=M\) かつ \(N\) が偶数である場合を除いて考えます。 例えば、以下のような構築が最適解を与えます。

oooxxxxxxxxxxxx
oooxxxxxxxxxxxx
oooooxxxxxxxxxx
xxoooxxxxxxxxxx
xxoooooxxxxxxxx
xxxxoooxxxxxxxx
xxxxooooooooooo

\(3X+Y\) は、以下のように移動することで \(1\) 増えます。

• \((i,j)\) から \((i,j+1)\) に移動する。
• \((i,j)\) から \((i+1,j-2)\) に移動する。

上記の \(2\) 個の移動を使い、\((1,1)\) から全ての o のみを通って \((N,M)\) にたどり着くことができるため、全ての o について \(3X+Y\) は異なり、かつ o の個数は \(3N+M-3\) であることが証明できました。 \(X+3Y\) についても、盤面の外に出てしまいますが、同様にして全ての o について \(X+3Y\) が異なることが証明できます。

\(N=M\) かつ \(N\) が偶数である場合も、同じ構築をすることで最適解が構築できます。

oooxxx
oooxxx
ooooox
xxooox
xxoooo
xxxxoo

ですが、上記のように \((N-1,N+1)\) のマスが存在しないため \((N-1,N), (N-1,N+1),(N,N-1)\) と移動する時に o を置ける個数が \(1\) 減ってしまいます。

以下、この場合最適解は \(3N+M-4\) であることを証明します。

\(N=2\) である場合は、全てのマスに置くことができるため \(3N+M-4 = NM\) となり最適解です。

\(N \ge 4\) である場合について考えます。 \((3,1)\) から以下の \(4\) 通りの移動によって到達できる盤面の中のマスの集合を \(S\) とします。ただし、盤面の外を経由して盤面の中に戻ってくるような移動もできることとします。

• \((i,j)\) から \((i+1,j-3)\) に移動する。
• \((i,j)\) から \((i+3,j-1)\) に移動する。
• \((i,j)\) から \((i-1,j+3)\) に移動する。
• \((i,j)\) から \((i-3,j+1)\) に移動する。

\(S\) の要素の \(3X+Y\) の種類数は \(\frac{N}{2}\) ですが、\(X+3Y\) の種類数は \(\frac{N}{2}-1\) であるため、\(3N+M-3\) に加えて更に \(1\) 評価を改善でき、\(3N+M-4\) が \(K\) の上界となることがわかります。

よって、この問題を \(\mathrm{O}(N+M)\) で解くことができました。

出題準備の際に maspy さんに他の問題以上に多大なご助力を頂きました。ありがとうございます。