문제

www.acmicpc.net/problem/5009


알고리즘

2-SAT, 이분탐색


풀이

우리가 결정해야 할 것은 아이들의 호감리스트를 반영한 아이들의 반 배정입니다. 언뜻 보면 선생님이 3명이여서 아이들이 결정해야할 선생님이 세 사람 같아 보이지만 실제론 두 사람입니다. 이유는 작년에 담당했던 선생님은 선택사항이 아니기 때문입니다.

문제 조건중 “반에 속하는 모든 학생은 학생들이 좋아하는 순서에서 상위 T위 안에 있어야 한다.“는 달리 말해서 T위를 초과하는 학생과는 다른 반이 되어야 함을 의미합니다. 다른 반으로 배정하기 위해선 두 학생의 이전 선생님이 누구인지 알아야 하며, 이에 따라 반배정을 진행해주면 됩니다.

각 선생님 번호가 0 , 1 , 2라고 할 때, T(x)는 이전 선생님 + 1 을 선택한다는 의미이고, F(x)는 이전선생님 -1을 선택한다는 의미입니다. 즉 각 아이마다 두 선택지를 모델링할 수 있는 2-SAT으로 풀면 됩니다. 마지막으로 우리가 제외할 아이들(T위 초과하는 학생들)은 연속되어있으므로 이분탐색으로 T의 범위를 좁혀 나갈 수 있습니다. 시간복잡도는 이분탐색 한 번마다 SCC를 사용하므로 $O(Nlog(N+E)$ 입니다.

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

#define T(x) (x<<1)
#define F(x) (x<<1|1)

int N,SC,VC;
int prv[200];
int child[200][199];

vector<vector<int>> adj;
vector<int> discovered, sccid;
stack<int> st;
int scc(int here) {
    int ret = discovered[here] = VC++;
    st.emplace(here);

    for (auto there : adj[here]) {
        if (discovered[there] == -1) ret = min(ret, scc(there));
        else if (sccid[there] == -1) ret = min(ret, discovered[there]);
    }

    if (ret == discovered[here]) {
        while (1) {
            int t = st.top();st.pop();
            sccid[t] = SC;
            if (t == here) break;
        }
        ++SC;
    }
    return ret;
}

void OR(int u, int v) {
    adj[u ^ 1].emplace_back(v);
    adj[v ^ 1].emplace_back(u);
}

void AOA(int a, int b, int c, int d) {
    OR(a, c);	OR(a, d);
    OR(b, c);	OR(b, d);
}

bool ok(int t) {
    VC = SC = 0;
    adj.clear();
    adj.resize(N << 1);
    discovered = sccid = vector<int>(N << 1, -1);

    rep(i, N) {
        for (int j = t;j < N-1;++j) {
            int A = i;
            int B = child[i][j];

            if (prv[A] == prv[B])
                AOA(T(A), F(B), F(A), T(B));
            else if ((prv[A] + 1) % 3 == prv[B])
                OR(T(A), F(B));
            else
                OR(F(A), T(B));
        }
    }

    rep(i, N << 1) if (discovered[i] == -1) scc(i);
    for (int i = 0;i < N << 1;i+=2) if (sccid[i] == sccid[i ^ 1]) {
        return false;
    }
    return true;
}
int main() {
    FAST;
    cin >> N;
    rep(i, N) {
        cin >> prv[i];
        rep(j, N - 1) {
            cin >> child[i][j];
            --child[i][j];
        }
    }

    int lo = 0;
    int hi = N-1;
    int best;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (ok(mid)) {
            best = mid;
            hi = mid - 1;
        }
        else lo = mid + 1;
    }
    cout << best;
    return 0;
}