はじめから一般のケースについて解説しようとすると非常に分かりにくくなるため、具体例を中心として解説を行います。一般的な解法については実装例も合わせてご覧ください。

実装例 (Python)

まず、 \(N=2\) の場合について考えます。一例として、 \(M=5\) の場合について解きます。

最初の状態は以下のようになっています。

.1234512345.

ここから \(4\) 回の操作で内側の \(8\) 個の石 (23451234の部分) を外に移動させ、適当な場所に保管しておきます。

.1........5.........23..45..12..34.

取り除いた \(8\) 個の石を上手く内側に戻すことで、以下のように並べることができます。

.1122334455.

以上により、 \(8\) 回の操作で \(N=2,M=5\) の場合を解くことができました。一般に \(N=2\) の場合は、同様の操作により \(2(M-1)\) 回の操作で解くことができます。

続いて、一般の \(N\) について考えます。一例として、 \(N=4,M=5\) の場合を解きます。

最初の状態は以下の通りです。

.12345123451234512345.

まずは先ほどと同様の操作を行うことにより、 \(8 \times 2 = 16\) 回の操作で以下の状態を達成できます。

.11223344551122334455.

ここまでの操作を前半と呼ぶことにします。このような状態になれば、あとは簡単です。色の等しい隣り合う石のペアを \(1\) つずつ動かしていけば、 \(10\) 回で以下の状態を達成できます。

.....................11112222333344445555.

しかしこれでは、 \(16+10=26 \gt 25 = (4+1) \times 5\) となり、回数の制限を満たせません。そこで、前半で行った操作をよく観察してみましょう。分かりやすくするために、中央に空白を入れています。中央の空白より左側を左の塊、右側を右の塊と呼ぶことにします。

.1234512345  1234512345.
↓(4回)
.1........5  1234512345...23..45..12..34.
↓(4回)
.1122334455  1234512345.
↓(4回)
.1122334455  1........5...23..45..12..34.
↓(4回)
.1122334455  1122334455.

これは、以下のようにして操作回数を減らすことができます。

.1234512345  1234512345.
↓(4回)
.1........5  1234512345...23..45..12..34.
↓(4回)
.1122334455  1........5...23..45..12..34.
↓(4回)
.1122334455  1122334455.

左の塊から一度外に取り出した石をそのまま左の塊に戻すのではなく、右の塊の内側の石を左の塊に移動させ、左の塊から取り出した石は右の塊に移動させるようにしました。これにより、前半の操作回数を \(12\) 回に減らすことができました。後半の回数は \(10\) 回だったので、合計 \(22\) 回で並べ替えることができ、回数制限を満たします。

一般の場合にも同様の方法を用いることができます。まず、 \(NM\) 個の石を \(2M\) 個ずつの塊に分けます。ここから上の例と同様のことを行います。一番左の塊の内側の石を取り出した後、左から \(2\) 番目の塊の石を一番左の塊に、 \(3\) 番目の塊の石を \(2\) 番目の塊に、 \(\ldots\) と順に移動させ、最初取り出した一番左の塊の石は一番右の塊に移動させます。このようにすることで、前半の操作を \(\left(\frac{N}{2}+1\right) \times (M-1)\) 回で行うことができます。後半の操作は \(\frac{N}{2} \times M\) 回で行うことができるため、合計 \(NM+M-\frac{N}{2}-1 \le (N+1)M\) 回で行うことができ、条件を達成できます。