A - Amazing Trick

이 문제는 순열 조건을 만족하는 두 개의 순열 \( p_1 \)과 \( p_2 \)를 찾는 것이 목표다. 주어진 배열 \( a \)에 대해, 모든 \( i \)에서 \( p[i] \neq i \)이고 \( p[i] \neq a[i] \)인 순열 \( p \)를 무작위로 생성하여 유효성을 검사한다. 난수 셔플을 여러 번 시도한 후 조건을 만족하면 이를 기반으로 \( p_1 \)과 \( p_2 \)를 구성한다.

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 5;
random_device rd;
mt19937 gen(rd());

int N, arr[MAX], perm[MAX], invA[MAX], p1[MAX], p2[MAX];

void solveTask() {
    cin >> N;
    for (int i = 1; i <= N; ++i) cin >> arr[i];
    iota(perm + 1, perm + N + 1, 1);

    bool found = false;
    for (int trial = 0; trial < 200 && !found; ++trial) {
        shuffle(perm + 1, perm + N + 1, gen);
        bool valid = true;
        for (int i = 1; i <= N; ++i) {
            if (perm[i] == i || perm[i] == arr[i]) {
                valid = false;
                break;
            }
        }
        if (valid) found = true;
    }

    if (!found) {
        cout << "Impossible\n";
        return;
    }

    cout << "Possible\n";
    for (int i = 1; i <= N; ++i) invA[arr[i]] = i;
    for (int i = 1; i <= N; ++i) p1[i] = invA[perm[i]];
    for (int i = 1; i <= N; ++i) invA[arr[p1[i]]] = i;
    for (int i = 1; i <= N; ++i) p2[i] = invA[i];

    for (int i = 1; i <= N; ++i) cout << p1[i] << " ";
    cout << "\n";
    for (int i = 1; i <= N; ++i) cout << p2[i] << " ";
    cout << "\n";
}

D - Dominoes

격자 내 빈 칸들 사이에 도미노를 배치할 수 있는 경우의 수를 계산하는 문제이다. 격자를 이분 그래프로 모델링하고, 각 연결 가능한 인접 쌍을 간선으로 표현한다. 최대 유량 알고리즘(Dinic)을 사용해 매칭 수를 구한 후, 잔여 네트워크에서 도달 가능한 정점을 탐색하여 전체 가능한 쌍의 수를 보정한다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;
const int MAXE = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int LIMIT = 1e6;

int H, W, nodeID[MAXN][MAXN], totalNodes;
string grid[MAXN];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int source, sink, level[MAXN], ptr[MAXN];
vector<array<int, 3>> edges;
vector<int> adj[MAXN];

void addEdge(int u, int v, int cap) {
    adj[u].push_back(edges.size());
    edges.push_back({v, cap, 0});
    adj[v].push_back(edges.size());
    edges.push_back({u, 0, 0});
}

bool bfsLevels() {
    fill(level, level + MAXN, -1);
    queue<int> q;
    q.push(source);
    level[source] = 0;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int idx : adj[u]) {
            auto& [v, cap, flow] = edges[idx];
            if (cap > flow && level[v] == -1) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[sink] != -1;
}

int dfsAugment(int u, int minCap) {
    if (u == sink || !minCap) return minCap;
    for (int& i = ptr[u]; i < adj[u].size(); ++i) {
        int idx = adj[u][i];
        auto& [v, cap, flow] = edges[idx];
        if (level[v] == level[u] + 1 && cap > flow) {
            int pushed = dfsAugment(v, min(minCap, cap - flow));
            if (pushed) {
                flow += pushed;
                edges[idx ^ 1][2] -= pushed;
                return pushed;
            }
        }
    }
    return 0;
}

int computeMaxFlow() {
    int total = 0;
    while (bfsLevels()) {
        fill(ptr, ptr + MAXN, 0);
        while (int pushed = dfsAugment(source, INF)) {
            total += pushed;
        }
    }
    return total;
}

void solveDomino() {
    cin >> H >> W;
    for (int i = 1; i <= H; ++i) {
        cin >> grid[i];
        grid[i] = " " + grid[i];
    }

    int blackCount = 0, whiteCount = 0;
    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            if (grid[i][j] == '.') {
                if ((i + j) % 2 == 0) {
                    nodeID[i][j] = ++blackCount;
                } else {
                    nodeID[i][j] = ++whiteCount;
                }
            }
        }
    }

    if (1LL * blackCount * whiteCount >= LIMIT) {
        cout << LIMIT << "\n";
        return;
    }

    totalNodes = blackCount + whiteCount;
    source = 0, sink = totalNodes + 1;
    edges.clear();
    for (int i = 0; i <= sink; ++i) adj[i].clear();

    for (int i = 1; i <= blackCount; ++i) {
        addEdge(source, i, 1);
    }
    for (int i = 1; i <= whiteCount; ++i) {
        addEdge(blackCount + i, sink, 1);
    }

    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            if (grid[i][j] == '.' && (i + j) % 2 == 0) {
                for (int d = 0; d < 4; ++d) {
                    int ni = i + dx[d], nj = j + dy[d];
                    if (ni < 1 || ni > H || nj < 1 || nj > W) continue;
                    if (grid[ni][nj] != '.') continue;
                    int u = nodeID[i][j], v = nodeID[ni][nj];
                    addEdge(u, blackCount + v, 1);
                }
            }
        }
    }

    computeMaxFlow();
    int result = blackCount * whiteCount;
    vector<bool> reachable(totalNodes + 2, false);

    for (int start = 1; start <= blackCount; ++start) {
        fill(reachable.begin(), reachable.end(), false);
        queue<int> q;
        q.push(start);
        reachable[start] = true;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int idx : adj[u]) {
                auto& [v, cap, flow] = edges[idx];
                if (edges[idx ^ 1][2] > 0 && !reachable[v]) {
                    reachable[v] = true;
                    q.push(v);
                }
            }
        }

        for (int end = 1; end <= whiteCount; ++end) {
            if (!reachable[blackCount + end]) {
                result++;
            }
        }
    }

    cout << min(result, LIMIT) << "\n";
}

G - Game of Questions

비트마스크 DP를 활용해 질문 집합에 대한 확률을 계산하는 문제다. 각 비트마스크 \( S \)에 대해, 해당 질문 조합이 선택될 수 있는 확률을 전파하며 업데이트한다. 포함-배제 원리를 응용하여, 특정 조건을 만족하는 부분집합의 기여도를 반영한다.

const int BITS = 17;
double dp[1 << BITS];
int countMask[1 << BITS], subsetSum[1 << BITS];

void solveQuestions() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int mask = 0;
        for (int j = 0; j < m; ++j) {
            if (s[j] == '1') mask |= (1 << j);
        }
        countMask[mask]++;
    }

    int full = (1 << m) - 1;
    copy(countMask, countMask + (1 << m), subsetSum);

    for (int i = 0; i < m; ++i) {
        for (int mask = full; mask >= 0; --mask) {
            if (mask & (1 << i)) {
                subsetSum[mask ^ (1 << i)] += subsetSum[mask];
            }
        }
    }

    dp[full] = 1.0;
    double answer = 0.0;

    for (int mask = full; mask > 0; --mask) {
        if (!(mask & 1)) continue;
        int remaining = n;
        int complement = mask ^ full;
        for (int sub = complement; ; sub = (sub - 1) & complement) {
            remaining -= countMask[sub] + countMask[sub ^ mask];
            if (sub == 0) break;
        }

        if (remaining == 0) {
            answer += dp[mask];
        } else {
            vector<int> subsets;
            unordered_map<int, int> tempCount;
            for (int sub = mask; sub; sub = (sub - 1) & mask) {
                tempCount[sub] = subsetSum[sub];
                subsets.push_back(sub);
            }

            for (int i = 0; i < m; ++i) {
                if (mask & (1 << i)) {
                    for (int j = subsets.size() - 1; j >= 0; --j) {
                        int sub = subsets[j];
                        if (!(sub & (1 << i))) {
                            tempCount[sub] -= tempCount[sub | (1 << i)];
                        }
                    }
                }
            }

            for (int j = subsets.size() - 1; j >= 0; --j) {
                int sub = subsets[j];
                dp[sub] += dp[mask] * tempCount[sub] / remaining;
            }
        }
    }

    cout << fixed << setprecision(12) << answer << "\n";
}

I - Interactive Factorial Guessing

인터랙티브 환경에서 숨겨진 숫자 \( x \)를 추측해야 하며, \( x! \)의 특정 자릿수 값을 질의할 수 있다. 사전에 \( 1 \)부터 \( 6000 \)까지의 모든 팩토리얼을 자리수 단위로 저장하고, 각 질의를 통해 가능한 후보군을 좁혀간다. 정보 이득이 최대가 되는 자릿수를 선택하여 효율적으로 추론한다.

const int MAX_X = 6000;
const int DIGITS = 20000;
int factorialDigits[MAX_X + 1][DIGITS];
int frequency[10];

void precomputeFactorials() {
    factorialDigits[0][0] = 1;
    for (int i = 1; i <= MAX_X; ++i) {
        copy(factorialDigits[i - 1], factorialDigits[i - 1] + DIGITS, factorialDigits[i]);
        for (int j = 0; j < DIGITS; ++j) {
            factorialDigits[i][j] *= i;
        }
        for (int j = 0; j < DIGITS - 1; ++j) {
            if (factorialDigits[i][j] >= 10) {
                factorialDigits[i][j + 1] += factorialDigits[i][j] / 10;
                factorialDigits[i][j] %= 10;
            }
        }
    }
}

int queryDigit(int pos) {
    cout << "? " << pos << endl << flush;
    int response;
    cin >> response;
    return response;
}

void solveInteractive() {
    vector<int> candidates;
    for (int i = 1; i <= MAX_X; ++i) {
        candidates.push_back(i);
    }

    vector<int> pivotPoints = {1601, 1483, 1692, 2017, 1543, 1524, 1467, 1786, 1456, 1600};

    for (int round = 0; round < 2 && candidates.size() > 1; ++round) {
        int pos = pivotPoints[queryDigit(pivotPoints[0])];
        int value = queryDigit(pos);
        vector<int> updated;
        for (int x : candidates) {
            if (factorialDigits[x][pos] == value) {
                updated.push_back(x);
            }
        }
        candidates = updated;
    }

    while (candidates.size() > 1) {
        int bestPos = 0, minFreq = INT_MAX;
        for (int d = 0; d < DIGITS; ++d) {
            fill(frequency, frequency + 10, 0);
            int maxCount = 0;
            for (int x : candidates) {
                int digitVal = factorialDigits[x][d];
                frequency[digitVal]++;
                maxCount = max(maxCount, frequency[digitVal]);
            }
            if (maxCount < minFreq) {
                minFreq = maxCount;
                bestPos = d;
            }
        }

        int observed = queryDigit(bestPos);
        vector<int> filtered;
        for (int x : candidates) {
            if (factorialDigits[x][bestPos] == observed) {
                filtered.push_back(x);
            }
        }
        candidates = filtered;
    }

    cout << "! " << candidates[0] << endl << flush;
    string verdict;
    cin >> verdict;
}