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

• 問題: No.3506 All Distance is Square Number
• ユーザー: gojoxd
• 提出日時: 2026-04-18 15:14:00
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 8,107 bytes
• コンパイル時間: 1,801 ms
• コンパイル使用メモリ: 233,332 KB
• 実行使用メモリ: 7,972 KB
• 最終ジャッジ日時: 2026-04-18 15:14:23
• 合計ジャッジ時間: 21,996 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_1

ファイルパターン	結果
other	AC * 26 WA * 3

ソースコード

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

using namespace std;

// 最大800程度までの平方数を事前計算
bool is_sq[200005];

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    for (int i = 1; i * i < 200005; ++i) {
        is_sq[i * i] = true;
    }

    int N;
    if (!(cin >> N)) return 0;
    
    // ベースケース
    if (N == 2) {
        cout << 1 << "\n";
        cout << 1 << " " << 2 << " " << 1 << "\n";
        cout << 1 << " " << 1 << "\n";
        return 0;
    }

    int M = 2 * N - 3;
    vector<int> vals(200);
    iota(vals.begin(), vals.end(), 1); // 1から200の重みを利用可能
    
    mt19937 rng(1337);
    shuffle(vals.begin(), vals.end(), rng);
    
    int W = vals[0];
    vector<int> X(N + 1), Y(N + 1), S(N + 1);
    for (int i = 3; i <= N; ++i) {
        X[i] = vals[2 * i - 5];
        Y[i] = vals[2 * i - 4];
        S[i] = X[i] + Y[i];
    }
    
    // 平方数の経路を持たないペアの数（スコア）を計算する関数
    auto get_score = [&]() {
        int bad = 0;
        
        // 1と2の間のパス
        if (!is_sq[W]) {
            bool ok = false;
            for (int k = 3; k <= N; ++k) {
                if (is_sq[S[k]]) { ok = true; break; }
            }
            if (!ok) bad++;
        }
        
        // 1とvの間のパス
        for (int v = 3; v <= N; ++v) {
            if (is_sq[X[v]] || is_sq[W + Y[v]]) continue;
            bool ok = false;
            for (int k = 3; k <= N; ++k) {
                if (k == v) continue;
                if (is_sq[S[k] + Y[v]]) { ok = true; break; }
            }
            if (!ok) bad++;
        }
        
        // 2とvの間のパス
        for (int v = 3; v <= N; ++v) {
            if (is_sq[Y[v]] || is_sq[W + X[v]]) continue;
            bool ok = false;
            for (int k = 3; k <= N; ++k) {
                if (k == v) continue;
                if (is_sq[S[k] + X[v]]) { ok = true; break; }
            }
            if (!ok) bad++;
        }
        
        // 葉uと葉vの間のパス
        for (int u = 3; u <= N; ++u) {
            int Xu = X[u], Yu = Y[u];
            for (int v = u + 1; v <= N; ++v) {
                if (is_sq[Xu + X[v]] || is_sq[Yu + Y[v]] || 
                    is_sq[Xu + W + Y[v]] || is_sq[Yu + W + X[v]]) continue;
                
                bool ok = false;
                for (int k = 3; k <= N; ++k) {
                    if (k == u || k == v) continue;
                    if (is_sq[Xu + S[k] + Y[v]] || is_sq[Yu + S[k] + X[v]]) { 
                        ok = true; break; 
                    }
                }
                if (!ok) bad++;
            }
        }
        return bad;
    };
    
    int current_score = get_score();
    int best_score = current_score;
    vector<int> best_vals = vals;
    
    auto start_time = chrono::steady_clock::now();
    int iters = 0;
    
    // 焼きなまし法のパラメータ
    double start_temp = 5.0;
    double end_temp = 0.01;
    double time_limit = 1.85; 
    
    // 焼きなまし法 (Simulated Annealing)
    while (best_score > 0) {
        iters++;
        
        int type = rng() % 2;
        int idx1 = rng() % M;
        int idx2 = (type == 0) ? (rng() % M) : (M + (rng() % (200 - M)));
        
        if (idx1 == idx2) continue;
        
        swap(vals[idx1], vals[idx2]);
        
        W = vals[0];
        for (int i = 3; i <= N; ++i) {
            X[i] = vals[2 * i - 5];
            Y[i] = vals[2 * i - 4];
            S[i] = X[i] + Y[i];
        }
        
        int new_score = get_score();
        bool accept = false;
        
        if (new_score <= current_score) {
            accept = true;
        } else {
            auto now = chrono::steady_clock::now();
            double elapsed = chrono::duration<double>(now - start_time).count();
            if (elapsed > time_limit) break;
            
            // 悪化を許容する確率を計算
            double temp = start_temp * pow(end_temp / start_temp, elapsed / time_limit);
            double prob = exp((current_score - new_score) / temp);
            if (uniform_real_distribution<double>(0.0, 1.0)(rng) < prob) {
                accept = true;
            }
        }
        
        if (accept) {
            current_score = new_score;
            if (current_score < best_score) {
                best_score = current_score;
                best_vals = vals;
            }
        } else {
            // 元に戻す (Rollback)
            swap(vals[idx1], vals[idx2]);
            W = vals[0];
            for (int i = 3; i <= N; ++i) {
                X[i] = vals[2 * i - 5];
                Y[i] = vals[2 * i - 4];
                S[i] = X[i] + Y[i];
            }
        }
    }

    // --- タイムアップ後に最も良かった状態を確実に復元 ---
    vals = best_vals;
    W = vals[0];
    for (int i = 3; i <= N; ++i) {
        X[i] = vals[2 * i - 5];
        Y[i] = vals[2 * i - 4];
        S[i] = X[i] + Y[i];
    }

    // --- グラフ形状と辺の重みの出力 ---
    cout << M << "\n";
    cout << "1 2 " << W << "\n";
    for (int i = 3; i <= N; ++i) {
        cout << "1 " << i << " " << X[i] << "\n";
        cout << "2 " << i << " " << Y[i] << "\n";
    }
    
    // パス出力用ヘルパーラムダ
    auto print_path = [&](const vector<int>& p) {
        cout << p.size();
        for (int e : p) cout << " " << e;
        cout << "\n";
    };

    // --- パスの復元 ---
    for (int u = 1; u <= N; ++u) {
        for (int v = u + 1; v <= N; ++v) {
            
            if (u == 1 && v == 2) {
                if (is_sq[W]) { print_path({1}); continue; }
                bool found = false;
                for (int k = 3; k <= N; ++k) {
                    if (is_sq[S[k]]) { print_path({2*k-4, 2*k-3}); found = true; break; }
                }
                if (!found) print_path({1}); 
                continue;
            }
            
            if (u == 1) {
                if (is_sq[X[v]]) { print_path({2*v-4}); continue; }
                if (is_sq[W + Y[v]]) { print_path({1, 2*v-3}); continue; }
                bool found = false;
                for (int k = 3; k <= N; ++k) {
                    if (k == v) continue;
                    if (is_sq[S[k] + Y[v]]) { print_path({2*k-4, 2*k-3, 2*v-3}); found = true; break; }
                }
                if (!found) print_path({2*v-4});
                continue;
            }
            
            if (u == 2) {
                if (is_sq[Y[v]]) { print_path({2*v-3}); continue; }
                if (is_sq[W + X[v]]) { print_path({1, 2*v-4}); continue; }
                bool found = false;
                for (int k = 3; k <= N; ++k) {
                    if (k == v) continue;
                    if (is_sq[S[k] + X[v]]) { print_path({2*k-3, 2*k-4, 2*v-4}); found = true; break; }
                }
                if (!found) print_path({2*v-3});
                continue;
            }
            
            // 葉同士 (u >= 3 && v >= 3)
            if (is_sq[X[u] + X[v]]) { print_path({2*u-4, 2*v-4}); continue; }
            if (is_sq[Y[u] + Y[v]]) { print_path({2*u-3, 2*v-3}); continue; }
            if (is_sq[X[u] + W + Y[v]]) { print_path({2*u-4, 1, 2*v-3}); continue; }
            if (is_sq[Y[u] + W + X[v]]) { print_path({2*u-3, 1, 2*v-4}); continue; }
            bool found = false;
            for (int k = 3; k <= N; ++k) {
                if (k == u || k == v) continue;
                if (is_sq[X[u] + S[k] + Y[v]]) {
                    print_path({2*u-4, 2*k-4, 2*k-3, 2*v-3});
                    found = true; break;
                }
                if (is_sq[Y[u] + S[k] + X[v]]) {
                    print_path({2*u-3, 2*k-3, 2*k-4, 2*v-4});
                    found = true; break;
                }
            }
            if (!found) print_path({2*u-4, 2*v-4});
        }
    }
    
    return 0;
}