盤面に関して、良い状態 の条件を振り返ってみましょう。

盤面上のどの縦・横・斜め \(45\) 度のマス目の列を見ても、クイーンが \(2\) つ以上存在しない。

どの縦・横のマス目の列を見ても、クイーンが高々 \(1\) 個存在することを利用してみましょう。クイーンはあらかじめ \(N - 1\) 個置かれており、また与えられる盤面は 良い状態 を満たしているため、クイーンを追加で \(1\) 個配置するときの位置の候補は一意に定まります。より具体的には、

• \(1 \leq x \leq N\) かつ \(x \notin \left\{ r_1, r_2, \ldots, r_{N-1} \right\}\)
• \(1 \leq y \leq N\) かつ \(y \notin \left\{ c_1, c_2, \ldots, c_{N-1} \right\}\)

を満たすマス \((x, y)\) が、追加でクイーンを \(1\) 個配置する位置の唯一の候補です。

あとは、マス \((x, y)\) に実際にクイーンを置けるかどうかを試せばよいです。 \(i = 1, 2, \ldots, N - 1\) のすべてについて、以下の条件がすべて成り立つときにクイーンを追加で \(1\) 個配置できます。

• \(x + y \neq r_i + c_i\)
• \(x - y \neq r_i - c_i\)

これらの条件は、斜め \(45\) 度のマス目の列を確認することに対応しています。

問題全体の計算量は \(O(N)\) となります。

実装例 (C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
using namespace std;

int main() {
    int N; cin >> N;
    // 縦・横・斜めのマス目の列上に存在するクイーンを数える
    vector<int> row(N), col(N), diag1(2*N), diag2(2*N);
    for(int i=0; i<N-1; i++) {
        int r, c; cin >> r >> c;
        r--, c--;
        row[r]++;
        col[c]++;
        diag1[r+c]++;
        diag2[r-c+N]++;
    }

    // クイーンを追加で 1 個配置する唯一の候補がマス (x, y)
    // このコードでは、カウントが 0 になっている箇所を探すことで求めている
    int x = find(row.begin(), row.end(), 0) - row.begin();
    int y = find(col.begin(), col.end(), 0) - col.begin();

    // 斜めのマス目の列をチェック
    bool ok = true;
    ok &= diag1[x+y] == 0;
    ok &= diag2[x-y+N] == 0;
    if(!ok) {
        cout << -1 << endl;
    } else {
        cout << x + 1 << " " << y + 1 << endl;
    }
    return 0;
}