#1161062 (C++17(gnu拡張)) No.3539 Parentheses Square

• 問題: No.3539 Parentheses Square
• ユーザー: もの
• 提出日時: 2026-04-22 22:08:55
• 言語: C++17(gnu拡張) (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,817 bytes
• コンパイル時間: 4,567 ms
• コンパイル使用メモリ: 247,004 KB
• 実行使用メモリ: 34,952 KB
• 最終ジャッジ日時: 2026-05-08 20:59:39
• 合計ジャッジ時間: 8,617 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
sample	AC * 2 WA * 1
other	AC * 18 WA * 23

ソースコード

#include <bits/stdc++.h>
#include <atcoder/maxflow>

using namespace std;

using ll = long long;

vector<string> GetN(string pattern, int N) {
    int n = pattern.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(n + 1, false));

    dp[n][0] = true;

    for (int i = n - 1; i >= 0; i--) {
        for (int d = 0; d <= n; d++) {
            if (pattern[i] == '(' || pattern[i] == '.') {
                if (d + 1 <= n && dp[i + 1][d + 1]) dp[i][d] = true;
            }
            if (pattern[i] == ')' || pattern[i] == '.') {
                if (d - 1 >= 0 && dp[i + 1][d - 1]) dp[i][d] = true;
            }
        }
    }

    vector<string> res;
    string buffer = "";

    auto dfs = [&](auto self, int pos, int depth) -> void {
        if (res.size() >= N) return;
        if (pos == n) {
            res.push_back(buffer);
            return;
        }

        if ((pattern[pos] == '(' || pattern[pos] == '.') && depth + 1 <= n) {
            if (dp[pos + 1][depth + 1]) {
                buffer.push_back('(');
                self(self, pos + 1, depth + 1);
                buffer.pop_back();
            }
        }

        if (res.size() < N && (pattern[pos] == ')' || pattern[pos] == '.') && depth - 1 >= 0) {
            if (dp[pos + 1][depth - 1]) {
                buffer.push_back(')');
                self(self, pos + 1, depth - 1);
                buffer.pop_back();
            }
        }
    };

    if (dp[0][0]) {
        dfs(dfs, 0, 0);
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    assert(1 <= N && N <= 200);
    vector<string> T(N);
    for (int i = 0; i < N; i++)
    {
        cin >> T[i];
        assert(T[i].size() == N);
    }

    if (N % 2 == 1)
    {
        cout << "-1" << endl;
        return 0;
    }

    map<string, int> cand2idx;
    vector<string> idx2cand;
    vector<vector<int>> candidate;

    for (int i = 0; i < N; i++)
    {
        // vector<int> close(N + 1);
        // for (int j = 1; j <= N; j++)
        // {
        //     close[j] = close[j - 1] + (T[i][j] != '(');
        // }
        // vector<char> buffer(N);
        // vector<string> res;

        // auto f = [&](auto self, int pos, int depth) -> void
        // {
        //     if (res.size() == N)
        //         return;
        //     if (pos == T[i].size())
        //     {
        //         res.push_back(string(buffer.begin(), buffer.end()));
        //         return;
        //     }

        //     if (T[i][pos] == '.' || T[i][pos] == '(')
        //     {
        //         if (depth + 1 <= close[T[i].size()] - close[pos + 1])
        //         {
        //             buffer[pos] = '(';
        //             self(self, pos + 1, depth + 1);
        //         }
        //     }

        //     if ((T[i][pos] == '.' || T[i][pos] == ')') && depth > 0)
        //     {
        //         buffer[pos] = ')';
        //         self(self, pos + 1, depth - 1);
        //     }
        // };

        

        // f(f, 0, 0);

        vector<string> res = GetN(T[i], N);

        if (res.size() == 0)
        {
            cout << "-1" << endl;
            return 0;
        }

        for (int j = 0; j < res.size(); j++)
        {
            if (cand2idx.find(res[j]) == cand2idx.end())
            {
                cand2idx[res[j]] = idx2cand.size();
                idx2cand.push_back(res[j]);
                candidate.push_back({ i });
            }
            else
            {
                candidate[cand2idx[res[j]]].push_back(i);
            }
        }
    }

    if (candidate.size() < N)
    {
        cout << "-1" << endl;
        return 0;
    }

    // C <= N^2
    int C = candidate.size();
    int source = 0;
    int sink = 1;
    int candHead = 2;
    int tHead = candHead + C;

    atcoder::mf_graph<int> g(2 + C + N);
    for (int i = 0; i < C; i++)
    {
        g.add_edge(source, candHead + i, 1);
    }
    for (int i = 0; i < N; i++)
    {
        g.add_edge(tHead + i, sink, 1);
    }

    for (int i = 0; i < C; i++)
    {
        for (int j = 0; j < candidate[i].size(); j++)
        {
            g.add_edge(candHead + i, tHead + candidate[i][j], 1);
        }
    }

    int maxflow = g.flow(source, sink);
    if (maxflow != N)
    {
        cout << "-1" << endl;
        return 0;
    }

    auto edges = g.edges();

    vector<string> S(N);

    for (int i = 0; i < edges.size(); i++)
    {
        if (edges[i].from == source || edges[i].to == sink) continue;

        if (edges[i].flow == 1)
        {
            S[edges[i].to - tHead] = idx2cand[edges[i].from - candHead];
        }
    }

    for (int i = 0; i < N; i++)
    {
        cout << S[i] << endl;
    }
    
    for (int i = 0; i < N; i++)
    {
        cout << S[i] << endl;
    }
}