Submission #62925791

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 以下の近傍を用いる焼き鈍し解法
 * 近傍
 *  ・1点の深さを変更（隣接頂点いずれかの子とみなせる深さ）
 *  ・1点を根にする
 */
#include <bits/stdc++.h>
using namespace std;
//@brief プログラムの実行時間を計測する
struct Timer
{
    chrono::system_clock::time_point start;
    Timer()
    {
        start = chrono::system_clock::now();
    }
    void reset()
    {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

/**
 * 以下の近傍を用いる焼き鈍し解法
 * 近傍
 *  ・1点の深さを変更（隣接頂点いずれかの子とみなせる深さ）
 *  ・1点を根にする
 */
#include <bits/stdc++.h>
using namespace std;

//@brief プログラムの実行時間を計測する
struct Timer
{
    chrono::system_clock::time_point start;

    Timer()
    {
        start = chrono::system_clock::now();
    }

    void reset()
    {
        start = chrono::system_clock::now();
    }

    //@brief プログラムの実行時間を取得する
    //@return プログラムの実行時間(秒)
    double getTime()
    {
        auto now = chrono::system_clock::now();
        return chrono::duration<double>(now - start).count();
    }
};

//@brief startからendまでの範囲でprogressに応じ、最初に急激に減少、その後緩やかに減少した値をとる
//@param start 開始値
//@param end 終了値
//@param progress 進捗度(0~1)
//@return 進捗に合わせた値
double exponential_decrease(double start, double end, double progress)
{
    return pow(start, 1.0 - progress) * pow(end, progress);
}

Timer timer;
class Xorshift
{
public:
    using result_type = uint64_t;

    explicit Xorshift(uint64_t seed) : x_(seed) { assert(seed); }

    // [0, stop)
    uint64_t randrange(uint64_t stop)
    {
        assert(stop > 0);
        next();
        return x_ % stop;
    }

    // [start, stop)
    uint64_t randrange(uint64_t start, uint64_t stop)
    {
        assert(start < stop);
        next();
        return start + x_ % (stop - start);
    }

    // [a, b]
    uint64_t randint(uint64_t a, uint64_t b)
    {
        assert(a <= b);
        return randrange(a, b + 1);
    }

    // [0.0, 1.0]
    double random()
    {
        next();
        return static_cast<double>(x_) * (1.0 / static_cast<double>(UINT64_MAX));
    }

    // [a, b] or [b, a]
    double uniform(double a, double b) { return a + (b - a) * random(); }

    uint64_t next()
    {
        x_ ^= x_ << 13;
        x_ ^= x_ >> 17;
        x_ ^= x_ << 5;
        return x_;
    }

    bool gen_bool(double p)
    {
        return random() < p;
    }

    // Add this operator to use with std::shuffle
    uint64_t operator()()
    {
        return next();
    }

    static constexpr uint64_t min() { return 0; }
    static constexpr uint64_t max() { return UINT64_MAX; }

private:
    uint64_t x_;
};
Xorshift rng(1);
constexpr int N = 1000, H = 10;
int M;
vector<vector<int>> G(N);
int A[N], X[N], Y[N];

void input()
{
    int _;
    cin >> _ >> M >> _;
    for (int i = 0; i < N; i++)
        cin >> A[i];
    for (int i = 0; i < M; i++)
    {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for (int i = 0; i < N; i++)
        cin >> X[i] >> Y[i];
    for (int i = 0; i < N; i++)
    {
        sort(G[i].begin(), G[i].end(), [&](int x, int y)
             { return A[x] < A[y]; });
    }
}

/// @brief 各頂点の高さを元に親を復元して出力
/// @param heigts 頂点iの高さ
void output(vector<int> &heigts)
{
    vector<int> p(N, -1); // 頂点iの親の頂点
    for (int i = 0; i < N; i++)
    {
        if (heigts[i] == 0)
        {
            p[i] = -1;
        }
        else
        {
            for (auto to : G[i])
            {
                if (heigts[to] + 1 == heigts[i])
                {
                    p[i] = to;
                }
            }
        }
    }
    for (int i = 0; i < N; i++)
        cout << p[i] << " \n"[i + 1 == N];
}

struct SimulatedAnnealing
{
    const float start_temp = 32;
    const float end_temp = 4.8;
    const int TEMP_CHANGE_STEP = 4096;

    // 頂点iの隣接点を高さごとに何個あるか数える。
    // e.g. next_height_cnt[i][h]=2なら、頂点iの隣接点のうち、高さhの頂点が2個ある。
    int next_height_cnt[N][H + 1];
    vector<int> heights;
    int score = 0;

    vector<int> best_heights;
    int best_score = 0;

    SimulatedAnnealing(const vector<int> &heights) : heights(heights)
    {
        // 各頂点の隣接点を高さごとに何個あるか数える。
        for (int i = 0; i < N; i++)
            for (int j = 0; j < H + 1; j++)
                next_height_cnt[i][j] = 0;
        for (int i = 0; i < N; i++)
        {
            score += A[i] * (heights[i] + 1);
            for (auto &e : G[i])
            {
                assert(e < heights.size());
                assert(heights[e] < H + 1);
                next_height_cnt[i][heights[e]]++;
            }
        }
    }

    void solve(double time_limit)
    {

        best_heights = heights;
        best_score = score;

        float current_temp = start_temp;
        while (timer.getTime() < time_limit)
        {
            current_temp = exponential_decrease(start_temp, end_temp, timer.getTime() / time_limit);
            for (int _ = 0; _ < TEMP_CHANGE_STEP; _++)
            {
                // 1点の深さを変更
                int cur = rng.randrange(N);
                int new_parent = G[cur][rng.randrange(G[cur].size())];
                int prev_height = heights[cur];
                int new_height = heights[new_parent] + 1;
                if (rng.randrange(10) == 0)
                    new_height = 0;

                if (new_height > H)
                    continue;
                if (new_height == heights[cur])
                    continue;

                int height_diff = new_height - prev_height;
                int score_diff = A[cur] * height_diff;
                if (score_diff < 0 && exp(score_diff / current_temp) < rng.random())
                    continue;

                // 変更しても木が構築可能かチェック
                // 対象頂点に子の頂点がある場合、その子が別の頂点を親にできれば、
                // 子の高さを変えずに済む。
                // よって、対象頂点の子とつながる頂点が他に対象頂点の元の高さと同じ高さの頂点を持つかどうかをチェックする。
                bool can_change = true;
                for (auto &e : G[cur])
                    if (heights[e] == prev_height + 1)
                    {
                        if (next_height_cnt[e][prev_height] == 1)
                        {
                            can_change = false;
                            break;
                        }
                    }
                if (!can_change)
                    continue;

                // 更新
                score += score_diff;
                heights[cur] = new_height;
                for (auto &e : G[cur])
                {
                    next_height_cnt[e][prev_height]--;
                    next_height_cnt[e][new_height]++;
                }

                if (best_score < score)
                {
                    best_score = score;
                    best_heights = heights;
                }
            }
        }
    }
    inline vector<int> getAnswer()
    {
        return best_heights;
    }
};

int main()
{
    ios::sync_with_stdio(false); // cin, coutの同期を切る
    cin.tie(0);                  // cinのバッファリングを切る
    cout.tie(0);                 // coutのバッファリングを切る
    input();
    vector<int> heights(N, 0);
    {
        timer.reset();

        SimulatedAnnealing annealing(heights);
        annealing.solve(1.98);
        cerr << annealing.best_score << endl;
        heights = annealing.getAnswer();
        auto elapsed_time = timer.getTime();
        cerr << "elapsed_time for annealing: " << elapsed_time << endl;
    }

    output(heights);
}

Submission Info

Compile Error

In file included from /usr/include/c++/12/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/12/bits/stdc++.h:33,
                 from Main.cpp:7:
Main.cpp: In constructor ‘SimulatedAnnealing::SimulatedAnnealing(const std::vector<int>&)’:
Main.cpp:190:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  190 |                 assert(e < heights.size());
      |                        ~~^~~~~~~~~~~~~~~~

Judge Result