ABC 399

Sun, Mar 30, 2025

https://atcoder.jp/contests/abc399

A. Hamming Distance

https://atcoder.jp/contests/abc399/tasks/abc399_a

B. Ranking with Ties

https://atcoder.jp/contests/abc399/tasks/abc399_b

C. Make it Forest

https://atcoder.jp/contests/abc399/tasks/abc399_c

D. Switch Seats

https://atcoder.jp/contests/abc399/tasks/abc399_d

$A_i = A_j = a, (i < j)$ とする。

(1) $i+1=j$ のとき

$a$ が隣接しているので求める整数対の対象にならない

(2) それ以外のとき

求める整数対の候補となるのは

$A_{i-1} = A_{j-1}$ (baba 型)
$A_{i-1} = A_{j+1}$ (baab 型)
$A_{i+1} = A_{j-1}$ (abba 型)
$A_{i+1} = A_{j+1}$ (abab 型)

の4つのケースである。

(2.1) $A_{i+1} = A_{j-1}$ のとき

$i+2 = j$ のとき、同じ数字を参照しているので対象外. ($a b a$ で $b$ を参照しているケース)
$i+3 = j$ のとき、同じ数字が隣接しているので対象外. ($a b b a$ で $b$ を参照しているケース)
それ以外のとき、$(\min(a,b), \max(a,b))$ を答えに追加する

(2.2) それ以外の3ケースのとき

$(\min(a,b), \max(a,b))$ を答えに追加する

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        int N;
        cin >> N;
        vll A(N * 2 + 2);
        rep(i, N * 2) {
            cin >> A[i + 1];
        }
        A[0] = -INF;
        A[N * 2 + 1] = INF;

        vvint ids(N + 1);
        for (int i = 1; i <= N * 2; i++) {
            ids[A[i]].push_back(i);
        }

        set<pair<int, int>> ans;
        for (int a = 1; a <= N; a++) {
            int lid = ids[a][0];
            int rid = ids[a][1];

            // 数字 i が隣接している
            if (lid + 1 == rid)
                continue;

            for (int d1 : {-1, 1}) {
                for (int d2 : {-1, 1}) {
                    if (A[lid + d1] != A[rid + d2])
                        continue;

                    int b = A[lid + d1];

                    if (d1 == 1 && d2 == -1) {
                        // 同じ場所の数字を参照しているとき
                        // 1 2 1 における 2 の場所を見ている
                        if (lid + 2 == rid)
                            continue;

                        // 2 1 1 2 で 2 を調べているときのケースを飛ばす
                        if (lid + 3 == rid)
                            continue;
                    }

                    ans.insert(minmax(a, b));
                }
            }
        }

        cout << ans.size() << endl;
    };

    int t;
    cin >> t;
    rep(i, t) {
        cal();
    }
}