#1159423 (C++23) No.3506 All Distance is Square Number

• 問題: No.3506 All Distance is Square Number
• ユーザー: 왕지후
• 提出日時: 2026-04-18 11:15:15
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,525 ms / 2,000 ms
• コード長: 5,008 bytes
• コンパイル時間: 1,838 ms
• コンパイル使用メモリ: 214,392 KB
• 実行使用メモリ: 14,312 KB
• 最終ジャッジ日時: 2026-04-18 11:15:24
• 合計ジャッジ時間: 8,665 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
other	AC * 29

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <random>

using namespace std;

bool is_sq(int x) {
    int r = round(sqrt(x));
    return r * r == x;
}

int N;
vector<int> x_arr, y_arr;
int C_weight;

// 利用可能な重みのリスト
vector<int> available;

// グラフの構築 (バックトラッキング)
bool build_graph(int idx, vector<int>& avail, mt19937& rng) {
    if (idx > N) return true;

    // 利用可能な重みから2つを選ぶ候補を作成
    vector<pair<int, int>> cands;
    for (size_t i = 0; i < avail.size(); ++i) {
        for (size_t j = 0; j < avail.size(); ++j) {
            if (i == j) continue;
            cands.push_back({avail[i], avail[j]});
        }
    }
    shuffle(cands.begin(), cands.end(), rng);

    for (auto& p : cands) {
        int x = p.first;
        int y = p.second;

        // 頂点 idx に x と y を仮置き
        x_arr[idx] = x;
        y_arr[idx] = y;

        bool ok_node = true;
        
        // 1. 頂点1へのパスが平方数になるか
        bool ok1 = is_sq(x) || is_sq(y + C_weight);
        for (int w = 3; w < idx && !ok1; ++w) if (is_sq(y + y_arr[w] + x_arr[w])) ok1 = true;
        if (!ok1) continue;

        // 2. 頂点2へのパスが平方数になるか
        bool ok2 = is_sq(y) || is_sq(x + C_weight);
        for (int w = 3; w < idx && !ok2; ++w) if (is_sq(x + x_arr[w] + y_arr[w])) ok2 = true;
        if (!ok2) continue;

        // 3. 既存の頂点 j (3 <= j < idx) へのパスが平方数になるか
        for (int j = 3; j < idx; ++j) {
            bool ok_j = is_sq(x + x_arr[j]) || is_sq(y + y_arr[j]) ||
                        is_sq(x + C_weight + y_arr[j]) || is_sq(y + C_weight + x_arr[j]);
            for (int w = 3; w < idx && !ok_j; ++w) {
                if (w == j) continue;
                if (is_sq(x + x_arr[w] + y_arr[w] + y_arr[j])) ok_j = true;
                if (is_sq(y + y_arr[w] + x_arr[w] + x_arr[j])) ok_j = true;
            }
            if (!ok_j) {
                ok_node = false;
                break;
            }
        }

        if (ok_node) {
            vector<int> next_avail;
            for (int v : avail) {
                if (v != x && v != y) next_avail.push_back(v);
            }
            if (build_graph(idx + 1, next_avail, rng)) return true;
        }
    }
    return false;
}

struct Edge {
    int to, weight, id;
};
vector<vector<Edge>> adj;
vector<int> best_path;
vector<int> current_path;
vector<bool> vis;

// 平方数になるパスを見つけるためのDFS
bool dfs_path(int u, int target, int sum) {
    if (u == target) {
        if (is_sq(sum)) {
            best_path = current_path;
            return true;
        }
        return false;
    }
    for (auto& edge : adj[u]) {
        if (!vis[edge.to]) {
            vis[edge.to] = true;
            current_path.push_back(edge.id);
            if (dfs_path(edge.to, target, sum + edge.weight)) return true;
            current_path.pop_back();
            vis[edge.to] = false;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N)) return 0;

    mt19937 rng(1337); // 固定シードを用いて再現性を確保

    x_arr.resize(N + 1);
    y_arr.resize(N + 1);

    while (true) {
        vector<int> nums;
        for (int i = 1; i <= 200; ++i) nums.push_back(i);
        shuffle(nums.begin(), nums.end(), rng);

        // C_weight は平方数であると見つかりやすい
        int c_idx = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (is_sq(nums[i])) {
                c_idx = i;
                break;
            }
        }
        
        C_weight = nums[c_idx];
        nums.erase(nums.begin() + c_idx);

        if (N <= 2 || build_graph(3, nums, rng)) {
            break;
        }
    }

    // グラフの構築と出力
    int M = (N == 2) ? 1 : 2 * N - 3;
    cout << M << "\n";

    adj.assign(N + 1, vector<Edge>());
    int edge_id = 1;

    auto add_edge = [&](int u, int v, int w) {
        cout << u << " " << v << " " << w << "\n";
        adj[u].push_back({v, w, edge_id});
        adj[v].push_back({u, w, edge_id});
        edge_id++;
    };

    add_edge(1, 2, C_weight);
    for (int i = 3; i <= N; ++i) {
        add_edge(1, i, x_arr[i]);
        add_edge(2, i, y_arr[i]);
    }

    // 各ペアについて平方数パスを探す
    vis.assign(N + 1, false);
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            current_path.clear();
            best_path.clear();
            vis.assign(N + 1, false);
            vis[i] = true;
            
            dfs_path(i, j, 0);
            
            cout << best_path.size() << "\n";
            for (size_t k = 0; k < best_path.size(); ++k) {
                cout << best_path[k] << (k + 1 == best_path.size() ? "" : " ");
            }
            cout << "\n";
        }
    }

    return 0;
}