金と銀の動きについて

金が、あるマスへ移動する最短ターン数は以下のようになります。

4 4 4 4 4 4 4 4 4
4 3 3 3 3 3 3 3 4
4 3 2 2 2 2 2 3 4
4 3 2 1 1 1 2 3 4
4 3 2 1 0 1 2 3 4
5 4 3 2 1 2 3 4 5
6 5 4 3 2 3 4 5 6
7 6 5 4 3 4 5 6 7
8 7 6 5 4 5 6 7 8

銀が、あるマスへ移動する最短ターン数は以下のようになります。

4 4 4 4 4 4 4 4 4
5 3 3 3 3 3 3 3 5
4 4 2 2 2 2 2 4 4
5 3 3 1 1 1 3 3 5
4 4 2 2 0 2 2 4 4
5 3 3 1 3 1 3 3 5
4 4 2 4 2 4 2 4 4
5 3 5 3 5 3 5 3 5
4 6 4 6 4 6 4 6 4

一見複雑に見えますが、パリティで分けると構造が分かりやすくなります。

4 - 4 - 4 - 4 - 4
- 3 - 3 - 3 - 3 -
4 - 2 - 2 - 2 - 4
- 3 - 1 - 1 - 3 -
4 - 2 - 0 - 2 - 4
- 3 - 1 - 1 - 3 -
4 - 2 - 2 - 2 - 4
- 3 - 3 - 3 - 3 -
4 - 4 - 4 - 4 - 4

- 4 - 4 - 4 - 4 -
5 - 3 - 3 - 3 - 5
- 4 - 2 - 2 - 4 -
5 - 3 - 1 - 3 - 5
- 4 - 2 - 2 - 4 -
5 - 3 - 3 - 3 - 5
- 4 - 4 - 4 - 4 -
5 - 5 - 5 - 5 - 5
- 6 - 6 - 6 - 6 -

解法

集まるマスの偶奇を両方試して、それぞれ二分探索します。つまり、\(t = 0, 1\) それぞれについて、以下の判定問題を考えます。

\(m\) ターン以内にすべての人が同じマスに集まることが出来るか。ただし、集まるマス \((x, y)\) は \((x + y) \mod 2 = t\) が成り立つ。

人 \(i\) が \(m\) ターン以内に \((x + y)\mod 2 = t\) が成り立つマス \((x, y)\) に到達できる条件は、

• \(H_i =\) G のとき
  • \(-m \le x - R_i\)
  • \(-m\le y - C_i \le m\)
  • \((x - R_i) + (y - C_i) \le m\)
  • \((x - R_i) - (y - C_i) \le m\)
• \(H_i =\) S かつ \((R_i + C_i) \mod 2 = t\) のとき
  • \(-m \le x - R_i \le m\)
  • \(-m \le y - C_i \le m\)
• \(H_i =\) S かつ \((R_i + C_i) \mod 2 \ne t\) のとき
  • \(-m +1\le x - (R_i - 1) \le m-1\)
  • \(-m+1 \le y - C_i \le m-1\)

となります。これらの共通部分は、ある整数 \(L_x, R_x, L_y, R_y, A, B\) を用いて、

• \(L_x\le x \le R_x\)
• \(L_y \le y \le R_y\)
• \(x + y \le A\)
• \(x - y \le B\)

と表すことが出来ます。この中に \((x + y) \mod 2 = t\) となる点が存在するかを判定すればよいです。

ある \(y\) に対して、\(x\) の条件は

• \(L_x \le x \le \min(R_x, A - y, B + y)\)
• \((x + y) \mod 2 = t\)

であり、これを満たす \(x\) が存在するなら、\(x = L_x, L_x+1\) のどちらかは条件を満たします。

よって、\(x=L_x, L_x+1\) に対して、条件を満たす \(y\) が存在するかを判定をすれば十分で、これは \(O(1)\) で計算できます。

\(M\) を答えの最大値とすると、一つのテストケースについて、 \(O(N\log M)\) や \(O(N + \log M)\) 時間で計算できます。