Codeforces Round #720 (Div. 2) C: Nastia and a Hidden Permutation

問題解説 Codeforces

codeforces.com

想定解とは異なると思われる解法で解きました。

問題概要

(インタラクティブ問題)

1, 2, \cdots, n の順列 p _ 1, p _ 2, \cdots, p _ n がある。この順列を質問をして当てたい。質問では、整数 t, i, j, x \ (1 \leq t \leq 2, 1 \leq i, j \leq n, i \neq j, 1 \leq x \leq n - 1) を質問し、 t=1 ならば \max(\min(x, p _ i), \min(x + 1, p _ j)) の値を、 t=2 ならば \min(\max(x, p _ i), \max(x + 1, p _ j)) の値を知ることができる。

質問を \displaystyle{\left\lfloor\frac{3n}{2}\right\rfloor+30} 回以下行い、順列 p を答えよ。

解法

n 個の要素を \displaystyle{\left\lceil\frac{n}{2}\right\rceil} 個のペアに分け、定数個の例外を除いて各ペアについて 3 回の質問で値を特定します。以下、ペアになっている要素を p _ a, p _ b とします。

何個かの t, x の値について p _ a, p _ b の値と得られる値の関係を調べる実験を行うと、 t=1, x=n-1 や t=2, x=1 のときに得られる値の種類が最も多くなるので、それらの質問をします。具体的には、 t=1, x=n-1 を質問した答えを r _ 1、 t=2, x=1 を質問した答えを r _ 2 とし、 r _ 1, r _ 2 の値で場合分けします。なお、場合分けは番号が小さいものをより優先するとします。

(1) r _ 2 = 1 のとき

r _ 2 = 1 より \min(\max(1, p _ a), \max(2, p _ b)) = 1 ですが、 \max(2, p _ b)=1 となることはないので \max(1, p _ a)=1 です。従って p _ a=1 となります。また、 r _ 1 = \max(\min(n-1, 1), \min(n, p _ b)) = \max(1, \min(n, p _ b)) = p _ b なので、 p _a = 1, p _ b = r _ 1 となります。

(2) r _ 1 = n のとき

r _ 1 = n より \max(\min(n - 1, p _ a), \min(n, p _ b)) = n ですが、 \min(n - 1, p _ a) = n となることはないので \max(n, p _ b) = n です。従って p _ b = n となります。また、 r _ 2 = \min(\max(1, p _ a), \max(2, n)) = \min(\max(1, p _ a), n)) = p _ a なので、 p _ a = r _ 2, p _ b = n となります。

(3) 3 \leq r _ 1, r _ 2 \leq n - 2 のとき

r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) \leq n - 2 より p _ a, p _ b \leq n - 2, r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) \geq 3 より p _ a, p _ b \geq 3 なので 3 \leq p _ a, p _ b \leq n - 2 が成立します。よって、 r _ 1 = \max(p _ a, p _ b), r _ 2 = \min(p _ a, p _ b) より (p _ a, p _ b) としてあり得る組は (p _ a, p _ b) = (r _ 1, r _ 2), (r _ 2, r _ 1) の 2 通り存在します。

そこで、 t=1, x=r _ 2 として質問すると、答えが (p _ a, p _ b) = (r _ 1, r _ 2) のときは \max(\min(r _ 2, p _ a),\min(r _ 2 + 1, p _ b)) = \max(\min(p _ b, p _ a), \min(p _ b + 1, p _ b) = \max(p _ b, p _ b) = p _ b = r _ 2, (p _ a, p _ b) = (r _ 2, r _ 1) のときは \max(\min(r _ 2, p _ a), \min(r _ 2 +1, p _ b)) = \max(min(p _ a, p _ a), \min(p _ a + 1, p _ b)) = p _ a = r _ 1 となり、 r _ 1 \neq r _2 なのでこれらを判別することができます。

(4) r _ 1 = n - 1, r _ 2 = 2 のとき r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) \lt n より p _ b \lt n が、 r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) \gt 1 より p _a > 1 がわかります。また、 p _ a, p _ b \leq n - 2 のときは r _ 1 = \max(p _ a, p _ b) \leq n - 2 より矛盾が生じ、 p _ a, p _ b \geq 3 のときは r _ 2 = \min(p _ a, p _ b) \geq 3 より矛盾が生じるため、 (p _ a, p _ b) としてあり得る組は (p _ a, p _ b) = (n, 1), (n, 2), (n - 1, 1), (n - 1, 2), (2, n - 1) の 5 通り存在します。

t=1, x=1 として質問したときの答えを r _ 3、 t=2, x=n-1 として質問したときの答えを r _ 4 とすると、 (p _ a, p _ b) = (n, 1), (n, 2), (n - 1, 1), (n - 1, 2), (2, n - 1) のとき (r _ 3, r _ 4) はそれぞれ (r _ 3, r _ 4) = (1, n), (2, n), (1, n - 1), (2, n - 1), (2, n - 1) となるので、 (r _ 3, r _ 4) = (2, n - 1) とならない最初の 3 通りは判別することはできます。

また、 t=1, x=2 として質問したときの答えを r _ 5 とすると、 (p _ a, p _ b) = (n - 1, 2), (2, n - 1) のときそれぞれ r_5 = 2, 3 となり、残りの 2 通りも判別することができます。

(5) r _ 1 = r _ 2 = 2 のとき r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) \leq 2 より p _ a, p _ b \leq 2 であり、 p _ a = 1 のときは r _ 2 = \min(\max(1, 1), \max(2, p _ b)) = 1 \leq 2 と矛盾が生じるので p _ a = 2 です。 p は順列より p _ a \neq p _ b なので p _ b = 1 です。

(6) r _ 1 = r _ 2 = n - 1 のとき r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) \geq n - 1 より p _ a, p _ b \geq n - 1 であり、 p _ b = n のときは r _ 1 = \min(\max(n - 1, p _ a), \max(n, n)) = n \leq n - 1 と矛盾が生じるので p _ b = n - 1 です。 p は順列より p _ a \neq p _ b なので p _ a = n です。

(7) 3 \leq r _ 1 \leq n - 2, r _ 2 = 2 のとき r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) \leq n - 2 より p _ a, p _ b \leq n - 2、 r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) \geq 2 より p _ a \geq 2 です。また、 p _ a, p _ b \geq 3 のときは r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) = \max(p _ a, p _ b) \geq 3 \gt 2 と矛盾が生じ、 p _ a = 2, p _ b \leq 2 のときは r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) = \max(p _ a, p _ b) \leq 3 \lt 3 と矛盾が生じるので、 (p _ a, p _ b) としてあり得る組は (p _ a, p _ b) = (r _ 1, 1), (r _ 2, 2), (2, r _ 2) の 3 通り存在します。

t = 1, x = 1 として質問したときの答えを r _ 3、 t = 1, x = 2 として質問したときの答えを r _ 4 とすると、 (p _ a, p _ b) = (r _ 1, 1), (r _ 2, 2), (2, r _ 2) のとき (r _ 3, r _ 4) はそれぞれ (r _ 3, r _ 4) = (1, 2), (2, 2), (2, 3) となり、これらを判別することができます。

(8) r _ 1 = n - 1, 3 \leq r _ 2 \leq n - 2 のとき r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) \geq 3 より p _ a, p _ b \geq 3、 r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) \leq n - 1 より p _ b \leq n - 1 です。また、 p _ a, p _ b \leq n - 2 のときは r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) = \max(p _ a, p _ b) \leq n - 2 \lt n - 1 と矛盾が生じ、 p _ a \geq n - 1, p _ b = n - 1 のときは r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) = \min(p _ a, p _ b) \geq n - 1 \gt n - 2 と矛盾が生じるので、 (p _ a, p _ b) としてあり得る組は (p _ a, p _ b) = (n, r _ 2), (n - 1, r _ 2), (r _ 2, n - 1) の 3 通り存在します。

t = 2, x = n - 1 として質問したときの答えを r _ 3、 t = 2, x = n - 2 として質問したときの答えを r _ 4 とすると、 (p _ a, p _ b) = (n, r _ 2), (n - 1, r _ 2), (r _ 2, n - 1) のとき (r _ 3, r _ 4) はそれぞれ (r _ 3, r _ 4) = (n, n - 1), (n - 1, n - 1), (n - 1, n - 2) となり、これらを判別することができます。

以上より、次に示す方法で p _ a, p _ b を特定することができます。

t = 1, x = n - 1 として質問したときの答えを r _1、 t = 2, x = 1 として質問したときの答えを r _ 2 とする。

(1) r _ 2 = 1 のとき、 p _ a = 1, p _ b = r _ 1

(2) r _ 1 = n のとき、 p _ a = r _ 2, p _ b = n

(3) 3 \leq r _ 1, r _ 2 \leq n - 2 のとき、 t = 1, x = r2 として質問し、その答えを r _ 3 とすると

(3-1) r _ 3 = r _ 2 のとき、 p _ a = r _ 1, p _ b = r _ 2

(3-2) そうでないとき、 p _ a = r _ 2, p _ b = r _ 1

(4) r _ 1 = n - 1, r _ 2 = 2 のとき、 t = 1, x = 1 として質問しその答えを r _ 3、 t = 2, x = n - 1 として質問しその答えを r _ 4 とする。

(4-1) r _ 3 = 1, r _ 4 = n のとき、 p _ a = n, p _ b = 1

(4-2) r _ 3 = 2, r _ 4 = n のとき、 p _ a = n, p _ b = 2

(4-3) r _ 3 = 1, r _ 4 = n - 1 のとき、 p _ a = n - 1, p _ b = 1

(4-4) r _ 3 = 2, r _ 4 = n - 1 のとき、 t = 1, x = 2 として質問しその答えを r _ 5 とする。

(4-4-1) r _ 5 = 2 のとき、 p _ a = n - 1, p _ b = 2

(4-4-2) そうでないとき、 p _ a = 2, p _ b = n - 1

(5) r _ 1 = r _ 2 = 2 のとき、 p _ a = 2, p _ b = 1

(6) r _ 1 = r _ 2 = n - 1 のとき、 p _ a = n, p _ b = n - 1

(7) 3 \leq r _ 1 \leq n - 1, r _ 2 = 2 のとき、 t = 1, x = 1 として質問しその答えを r _ 3 とする。

(7-1) r _ 3 = 1 のとき、 p _ a = r _ 1, p _ b = 1

(7-2) そうでないとき、 t = 1, x = 2 として質問しその答えを r _ 4 とする。

(7-2-1) r _ 4 = 2 のとき、 p _ a = r _ 1, p _ b = 2

(7-2-2) そうでないとき、 p _a = 2, p _ b = r _ 1

(8) r _ 1 = 2, 3 \leq r _ 2 \leq n - 1 のとき、 t = 2, x = n - 1 として質問しその答えを r _ 3 とする。

(8-1) r _ 3 = n のとき、 p _ a = n, p _ b = r _ 2

(8-2) そうでないとき、 t = 2, x = n - 1 として質問しその答えを r _ 4 とする。

(8-2-1) r _ 4 = n - 1 のとき、 p _ a = n - 1, p _ b = r _ 2

(8-2-2) そうでないとき、 p _a = r _ 2, p _ b = n - 1

(p _ a, p _ b) の値を特定するのに 3 回以上質問しなければならないときもありますが、そのような場合でも 5 回以内の質問で特定することができ、このケースは十分小さい定数回しか出現しないため、クエリ数の上限以内で p のすべての要素が特定できます。

実装

codeforces.com

#include <bits/stdc++.h>
using namespace std;
int main(){
  int T;
  cin >> T;
  for (int i = 0; i < T; i++){
    int n;
    cin >> n;
    vector<pair<int, int>> P;
    for (int j = 0; j < n / 2; j++){
      P.push_back(make_pair(j * 2, j * 2 + 1));
    }
    if (n % 2 == 1){
      P.push_back(make_pair(n - 2, n - 1));
    }
    int m = P.size();
    vector<int> p(n);
    for (int j = 0; j < m; j++){
      int a = P[j].first;
      int b = P[j].second;
      cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << n - 1 << endl;
      int res1;
      cin >> res1;
      cout << "? " << 2 << ' ' << a + 1 << ' ' << b + 1 << ' ' << 1 << endl;
      int res2;
      cin >> res2;
      if (res2 == 1){
        p[a] = 1;
        p[b] = res1;
      } else if (res1 == n){
        p[a] = res2;
        p[b] = n;
      } else if (3 <= res1 && res1 <= n - 2 && 3 <= res2 && res2 <= n - 2){
        cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << res2 << endl;
        int res3;
        cin >> res3;
        if (res3 == res2){
          p[a] = res1;
          p[b] = res2;
        } else {
          p[a] = res2;
          p[b] = res1;
        }
      } else if (res1 == n - 1 && res2 == 2){
        cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << 1 << endl;
        int res3;
        cin >> res3;
        cout << "? " << 2 << ' ' << a + 1 << ' ' << b + 1 << ' ' << n - 1 << endl;
        int res4;
        cin >> res4;
        if (res3 == 1 && res4 == n){
          p[a] = n;
          p[b] = 1;
        } else if (res3 == 2 && res4 == n){
          p[a] = n;
          p[b] = 2;
        } else if (res3 == 1 && res4 == n - 1){
          p[a] = n - 1;
          p[b] = 1;
        } else {
          cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << 2 << endl;
          int res5;
          cin >> res5;
          if (res5 == 2){
            p[a] = n - 1;
            p[b] = 2;
          } else {
            p[a] = 2;
            p[b] = n - 1;
          }
        }
      } else if (res1 == 2 && res2 == 2){
        p[a] = 2;
        p[b] = 1;
      } else if (res1 == n - 1 && res2 == n - 1){
        p[a] = n;
        p[b] = n - 1;
      } else if (res1 < n - 1 && res2 == 2){
        cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << 1 << endl;
        int res3;
        cin >> res3;
        if (res3 == 1){
          p[a] = res1;
          p[b] = 1;
        } else {
          cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << 2 << endl;
          int res4;
          cin >> res4;
          if (res4 == 2){
            p[a] = res1;
            p[b] = 2;
          } else {
            p[a] = 2;
            p[b] = res1;
          }
        }
      } else if (res1 == n - 1 && res2 > 2){
        cout << "? " << 2 << ' ' << a + 1 << ' ' << b + 1 << ' ' << n - 1 << endl;
        int res3;
        cin >> res3;
        if (res3 == n){
          p[a] = n;
          p[b] = res2;
        } else {
          cout << "? " << 2 << ' ' << a + 1 << ' ' << b + 1 << ' ' << n - 2 << endl;
          int res4;
          cin >> res4;
          if (res4 == n - 1){
            p[a] = n - 1;
            p[b] = res2;
          } else {
            p[a] = res2;
            p[b] = n - 1;
          }
        }
      }
    }
    cout << "!";
    for (int j = 0; j < n; j++){
      cout << ' ' << p[j];
    }
    cout << endl;
  }
}