結果
| 問題 |
No.5020 Averaging
|
| ユーザー |
 colun
|
| 提出日時 | 2025-04-11 14:17:09 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 913 ms / 1,000 ms |
| コード長 | 21,595 bytes |
| コンパイル時間 | 2,882 ms |
| コンパイル使用メモリ | 163,724 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 13,364,017 |
| 最終ジャッジ日時 | 2025-04-11 14:18:01 |
| 合計ジャッジ時間 | 51,242 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
/* README.md
# New Heursitic Contest プロジェクト
## Claudeへのお願い
ヒューリスティックコンテストで1位を取るののお手伝いをお願いいたします。
頻繁にClaudeの別の部屋への移動が発生するため、重要な情報については可能な限り直接README.mdの更新をお願いいたします。
なお、TODOに関して増やす際は、頭に☐を置く様にし、また解決したことに関しては☐を☑へと置き換えるだけで、絶対に消さない様にしてください。
対話やコメントは常に日本語でお願いします。そもそもコメントは最低限にして、コメントなしでも分かりやすいコードになっていることが望ましいです。また、編集を行ったこと自体をコメントに残すことは避けてください。コード前後でのdiffを取るため、編集の意図はコメントが無くても正しく伝わっていると仮定して頂いて問題ありません。
指示されない範囲でコードを書いてください。凝ったコードは書かないでください。なるべく簡潔に、無駄なコードゴルフをしなくても短い行数でまとまる様な実装を選んでください。
1位を取るために必要なことは、重要な箇所のみを押さえることです。それらの重要な箇所については、都度指示を出します。重要な箇所をしっかり押さえることが出来るように、指示があった場所以外はシンプルにコードを保つことが、極めて重要になります。
また、一回のやり取りで沢山の修正を加えるのは控えてください。少しずつの修正を何往復もやり取りをくり返しながら修正していくことを好みます。
更に、現在の状況を把握するような指示が出ている際には、単に状況を把握するだけに留めてください。次の目標に取り掛かったりするのは、次の対話の往復時で充分ですし、別の指示が出る可能性もあります。
過去の別問題の仕様やメモは、参考のためです。今回も類似の問題とは限らないため、解法の方針は全く異なるものが望ましい場合があります。参考程度にご利用ください。
## フォルダ構成
- README.md - このファイル
- AHC045.md - 過去問の.md。TODO, 仕様, メモなどの参考にしてください。
- problem.md - 問題文（コンテスト開始時は存在しない）
- Main.cpp - C++のメインファイル（コンテスト開始時は存在しない）
- get_time.hpp, timer.hpp - 時間計測用のC++ヘッダファイル。書き替えずに使う。initTime関数とgetTime関数が定義されている。
- *.hpp - C++のヘッダファイル。なるべく、まとまった単位で分割して書く
- run.py - Main.cppをコンパイルして、inにあるファイルでテスト実行を行い統計結果を出力する
- submit.py - Main.cppからincludeされているファイルをを連結して、1つのC++ソースコードへと変換するPythonプログラム。プログラムを提出するときに使う
- submit.txt - submit.pyによって作成されるファイル（無視する）
- in - 入力ファイル置き場。（無視する）
## TODO
☑ 問題文をHTML形式で貼り付けてもらい、それをMarkDown形式へと変換してproblem.mdを作成する
☑ 仕様について話し合い、ユーザーに仕様が完成したことを納得させる。
☑ 仕様通りに実装を行う。
## 常に存在し完了することがないTODO
- 高速なコードを保つ
- 再帰でもない限りは、メモリの確保と解放を避けるために、ループ最下層でのコンテナはグローバル変数を使うなどする
- 簡潔なコードを保つ
- 明確なユーザーからの指示やREADME.mdへの過去の指示の痕跡のない冗長なコードは、行数が少なくなりシンプルになる様にリファクタリングを都度実施する
## 仕様
### 基本方針
- 全カードの値を「5×10^17からの差分」として扱う（A'_i = A_i - 5×10^17, B'_i = B_i - 5×10^17）
- 目標はカード1の表裏の値(A'_1, B'_1)を0に近づけること
- カード1を必ず含み、2段階のアプローチで解く：
1. ビームサーチで使用するカードの集合を選定
2. 焼きなましで選んだカードの操作順序を最適化
### 入力処理
- N=45枚のカードの表裏の値(A_i, B_i)を読み込む
- 全ての値を差分表現(A'_i, B'_i)に変換する
### カード選択（ビームサーチ）
- カード1は必ず含める
- ビームサーチのパラメータ
- ビーム幅：100
- 最大深さ：15（使用カード数）
- 状態表現：選択したカードの集合と各カードの現在値
- 遷移：新たなカードを追加する
- 重複除去：
- ゾブリストハッシュを使用
- 各カードIDに64ビットのハッシュ種を割り当て
- 選択済みカード集合のハッシュは各カードハッシュ種のXOR
- 同じハッシュ値の状態は探索から除外
- 評価関数：
- 途中評価：カード1の表裏の値の絶対値の和（|A'_1|+|B'_1|）
- 最終評価：シミュレーション後のカード1の表裏の値と0の差の最大値（max(|A'_1|,|B'_1|)）
- ビーム上位K個の解を焼きなまし初期状態として使用
### 操作順序最適化（焼きなまし）
- ビームサーチで選んだカード集合について、カード1と混合する順序を最適化
- 焼きなましのパラメータ
- 初期温度：10.0
- 冷却率：0.995
- 実行時間：0.8秒
- 状態表現：カード1と他のカードを混合する順序の配列
- 遷移操作
- 隣接する操作の入れ替え
- ランダムな位置の操作の入れ替え
- 評価関数：最終的なカード1の表裏の値と0の差の最大値
### 最終出力
- 最良の解から操作回数Xと各操作のカード番号ペア(u_i, v_i)を出力
### 実装詳細
- 差分表現を用いたカード値の更新処理
- カード組み合わせ時の平均値計算（小数点以下切り捨て）
- ビームサーチと焼きなましの効率的実装
- 複数のビーム候補から異なる初期解で焼きなまし並列実行
## メモ
- 表と裏の同時最適化が重要
- 正負の符号が異なるカードを組み合わせると0に近づきやすい
- ビームサーチでは「カード1と相性の良いカード群」を特定することを目指す
- 最終スコアはmax(V1, V2)で決まるため、表裏両方を均等に近づける必要がある
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <random>
#include <chrono>
#include <unordered_set>
#include <cassert>
#include <cstdint>
#include <queue>
#include <functional>
#include <sys/time.h>
inline double getNativeTime() {
timeval tv;
gettimeofday(&tv, 0);
return tv.tv_sec + tv.tv_usec * 1e-6;
}
inline void getCpuClock(unsigned long long & t) {
__asm__ __volatile__ ("rdtsc" : "=a"(*(unsigned int*)&t), "=d"(((unsigned int*)&t)[1]));
}
inline unsigned long long getCpuClock() {
unsigned long long t;
getCpuClock(t);
return t;
}
unsigned long long getTime$initCpuClock;
unsigned long long getTime$reserveUpdateCpuClock;
double getTime$initNativeTime;
double getTime$secPerClock;
double getTime$doneTime;
inline void initTime() {
getTime$initNativeTime = getNativeTime();
getCpuClock(getTime$initCpuClock);
getTime$secPerClock = 0.00000000025;
getTime$reserveUpdateCpuClock = 10000000;
getTime$doneTime = 0;
}
struct getTime$init_class {
inline getTime$init_class() {
initTime();
}
};
getTime$init_class getTime$init_obj;
inline double getTime() {
unsigned long long now;
getCpuClock(now);
now -= getTime$initCpuClock;
if(getTime$reserveUpdateCpuClock < now) {
double nowTime = getNativeTime() - getTime$initNativeTime;
getTime$secPerClock = nowTime / now;
getTime$reserveUpdateCpuClock = now + (unsigned long long)(0.05 * now / nowTime);
}
return getTime$doneTime = std::fmax(getTime$doneTime, getTime$secPerClock * now);
}
#ifdef __local__
class Timer;
Timer * g_timer = NULL;
class Timer {
private:
double start_time;
double children_elapsed;
std::string name;
int line;
bool reported;
Timer * parent;
public:
Timer(const char * section_name, int line) : name(section_name), line(line), reported(false), children_elapsed(0.0) {
start_time = getTime();
parent = g_timer;
g_timer = this;
}
void report() {
if (!reported) {
assert(g_timer==this);
g_timer = parent;
double end_time = getTime();
double elapsed = end_time - start_time;
if(parent) parent->children_elapsed += elapsed;
std::cerr << "TIME_" << name << "@" << line << ": " << std::fixed << std::setprecision(6) << (elapsed - children_elapsed) << " seconds" << std::endl;
reported = true;
}
}
~Timer() {
report();
}
};
#define TIMER_CAT(a, b) a##b
#define TIMER_CAT2(a, b) TIMER_CAT(a, b)
#define TIMER() Timer TIMER_CAT2(timer, __LINE__)(__func__, __LINE__)
#else
#define TIMER()
#endif
using namespace std;
// 定数
constexpr int64_t TARGET_VALUE = 500000000000000000LL;
constexpr int MAX_OPERATIONS = 50;
constexpr int BEAM_WIDTH = 50; // 100→50に削減
constexpr int MAX_DEPTH = 10; // 15→10に削減
constexpr double SA_TIME_LIMIT = 0.3; // 0.8→0.3に削減
constexpr double SA_INIT_TEMP = 10.0;
constexpr double SA_COOLING_RATE = 0.995;
// 乱数生成器
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// カードの構造体
struct Card {
int64_t front; // 表の値
int64_t back; // 裏の値
int64_t front_diff; // 目標値からの差分（表）
int64_t back_diff; // 目標値からの差分（裏）
Card() : front(0), back(0), front_diff(0), back_diff(0) {}
Card(int64_t f, int64_t b) : front(f), back(b) {
front_diff = front - TARGET_VALUE;
back_diff = back - TARGET_VALUE;
}
};
// ビームサーチの状態
struct BeamState {
vector<int> selected_cards;
vector<bool> is_selected;
int64_t card1_front_diff;
int64_t card1_back_diff;
uint64_t zobrist_hash;
double score;
BeamState() : card1_front_diff(0), card1_back_diff(0), zobrist_hash(0), score(0) {}
BeamState(int n) : is_selected(n, false), card1_front_diff(0), card1_back_diff(0), zobrist_hash(0), score(0) {}
bool operator<(const BeamState& other) const {
return score > other.score; // 小さいスコアが優先
}
};
// 焼きなましの状態
struct SAState {
vector<int> operations;
double score;
SAState() : score(0) {}
SAState(const vector<int>& ops) : operations(ops), score(0) {}
bool operator<(const SAState& other) const {
return score > other.score; // 小さいスコアが優先
}
};
// グローバル変数
int N;
vector<Card> cards;
vector<uint64_t> zobrist_seeds;
// ゾブリストハッシュの初期化
void init_zobrist() {
zobrist_seeds.resize(N);
for (int i = 0; i < N; ++i) {
zobrist_seeds[i] = rng();
}
}
// カードの混合操作
void merge_cards(Card& card_a, Card& card_b) {
int64_t new_front = (card_a.front + card_b.front) / 2;
int64_t new_back = (card_a.back + card_b.back) / 2;
card_a.front = new_front;
card_b.front = new_front;
card_a.back = new_back;
card_b.back = new_back;
card_a.front_diff = card_a.front - TARGET_VALUE;
card_b.front_diff = card_b.front - TARGET_VALUE;
card_a.back_diff = card_a.back - TARGET_VALUE;
card_b.back_diff = card_b.back - TARGET_VALUE;
}
// スコア計算（maxの絶対値）
double calculate_score(int64_t front_diff, int64_t back_diff) {
return max(abs(front_diff), abs(back_diff));
}
// ビームサーチで選択したカードのシミュレーション
/*
void simulate_beam_state(const vector<int>& selected_cards, vector<Card>& sim_cards) {
sim_cards = cards;
// カード1は必ず含まれる
for (size_t i = 1; i < selected_cards.size(); ++i) {
Card& card1 = sim_cards[0];
Card& card2 = sim_cards[selected_cards[i]];
merge_cards(card1, card2);
}
}
*/
// ビームサーチでカードを選択
vector<vector<int>> beam_search() {
TIMER();
// 結果格納用
vector<vector<int>> best_selections;
// 初期状態（カード1を含む）
vector<BeamState> current_beam;
BeamState initial_state(N);
initial_state.selected_cards.push_back(0); // カード1を追加
initial_state.is_selected[0] = true;
initial_state.card1_front_diff = cards[0].front_diff;
initial_state.card1_back_diff = cards[0].back_diff;
initial_state.zobrist_hash = zobrist_seeds[0];
initial_state.score = calculate_score(initial_state.card1_front_diff, initial_state.card1_back_diff);
current_beam.push_back(initial_state);
// 重複チェック用ハッシュセット
unordered_set<uint64_t> hash_set;
hash_set.insert(initial_state.zobrist_hash);
// 一時バッファを再利用
static vector<Card> sim_cards;
// ビーム探索
for (int depth = 1; depth < MAX_DEPTH; ++depth) {
vector<BeamState> next_beam;
next_beam.reserve(BEAM_WIDTH * (N-depth)); // 予め最大サイズを確保
for (const BeamState& state : current_beam) {
// 各カードについて追加を試みる
for (int card_idx = 1; card_idx < N; ++card_idx) {
if (state.is_selected[card_idx]) continue;
// 新しい状態を作成
BeamState new_state = state;
new_state.selected_cards.push_back(card_idx);
new_state.is_selected[card_idx] = true;
new_state.zobrist_hash ^= zobrist_seeds[card_idx];
// 重複チェック
if (hash_set.count(new_state.zobrist_hash) > 0) continue;
// カードの組み合わせをシミュレーション
sim_cards = cards;
// カード1は必ず含まれる
for (size_t i = 1; i < new_state.selected_cards.size(); ++i) {
Card& card1 = sim_cards[0];
Card& card2 = sim_cards[new_state.selected_cards[i]];
merge_cards(card1, card2);
}
// 途中評価（絶対値の和）
new_state.card1_front_diff = sim_cards[0].front_diff;
new_state.card1_back_diff = sim_cards[0].back_diff;
new_state.score = abs(new_state.card1_front_diff) + abs(new_state.card1_back_diff);
next_beam.push_back(new_state);
hash_set.insert(new_state.zobrist_hash);
}
}
// 次のビームを選択
if (next_beam.empty()) break;
// ビーム幅制限（部分ソートで効率化）
if (next_beam.size() > BEAM_WIDTH) {
partial_sort(next_beam.begin(), next_beam.begin() + BEAM_WIDTH, next_beam.end());
next_beam.resize(BEAM_WIDTH);
} else {
sort(next_beam.begin(), next_beam.end());
}
current_beam = move(next_beam); // moveで効率化
}
// 最終評価でソート
vector<pair<double, int>> final_scores;
final_scores.reserve(current_beam.size());
for (int i = 0; i < (int)current_beam.size(); ++i) {
sim_cards = cards;
// シミュレーション
for (size_t j = 1; j < current_beam[i].selected_cards.size(); ++j) {
Card& card1 = sim_cards[0];
Card& card2 = sim_cards[current_beam[i].selected_cards[j]];
merge_cards(card1, card2);
}
double score = calculate_score(sim_cards[0].front_diff, sim_cards[0].back_diff);
final_scores.emplace_back(score, i);
}
sort(final_scores.begin(), final_scores.end());
// 上位K個の結果を返す（最大3つに削減）
int K = min(3, (int)current_beam.size());
best_selections.reserve(K);
for (int i = 0; i < K; ++i) {
best_selections.push_back(current_beam[final_scores[i].second].selected_cards);
}
return best_selections;
}
// 焼きなましで操作順序を最適化
vector<pair<int, int>> simulated_annealing(const vector<int>& selected_cards) {
TIMER();
// カード1と他のカードの組み合わせ順を最適化
vector<int> operations;
for (size_t i = 1; i < selected_cards.size(); ++i) {
operations.push_back(selected_cards[i]);
}
// 最良の解を保存
SAState best_state(operations);
// 現在の解
SAState current_state = best_state;
// 一時バッファを再利用
static vector<Card> sim_cards;
sim_cards = cards;
// 評価関数
auto evaluate = [&](const vector<int>& ops) -> double {
// 一時バッファを再利用して再確保を避ける
sim_cards = cards;
for (int card_idx : ops) {
merge_cards(sim_cards[0], sim_cards[card_idx]);
}
return calculate_score(sim_cards[0].front_diff, sim_cards[0].back_diff);
};
// 初期評価
current_state.score = evaluate(current_state.operations);
best_state.score = current_state.score;
// 焼きなまし
double temp = SA_INIT_TEMP;
double start_time = getTime();
int iterations = 0;
while (getTime() - start_time < SA_TIME_LIMIT) {
iterations++;
// 遷移操作：順序の入れ替え
vector<int> new_operations = current_state.operations;
if (new_operations.size() >= 2) {
if (rng() % 2 == 0 || new_operations.size() == 2) {
// 隣接要素の入れ替え
int pos = rng() % (new_operations.size() - 1);
swap(new_operations[pos], new_operations[pos + 1]);
} else {
// ランダム位置の入れ替え
int pos1 = rng() % new_operations.size();
int pos2 = rng() % new_operations.size();
while (pos1 == pos2) {
pos2 = rng() % new_operations.size();
}
swap(new_operations[pos1], new_operations[pos2]);
}
}
// 評価
double new_score = evaluate(new_operations);
// 受理判定
bool accept = false;
if (new_score <= current_state.score) {
accept = true;
} else {
double prob = exp((current_state.score - new_score) / temp);
accept = (static_cast<double>(rng()) / rng.max() < prob);
}
// 状態更新
if (accept) {
current_state.operations = new_operations;
current_state.score = new_score;
// 最良解の更新
if (new_score < best_state.score) {
best_state.operations = new_operations;
best_state.score = new_score;
}
}
// 温度更新（頻度を下げる）
if (iterations % 200 == 0) {
temp *= SA_COOLING_RATE;
}
}
// 操作列に変換
vector<pair<int, int>> result;
for (int card_idx : best_state.operations) {
result.emplace_back(0, card_idx); // カード1と他のカードを組み合わせる
}
return result;
}
// メイン関数
int main() {
TIMER();
// タイマー初期化
initTime();
// 入力
cin >> N;
cards.resize(N);
for (int i = 0; i < N; ++i) {
int64_t front, back;
cin >> front >> back;
cards[i] = Card(front, back);
}
// ゾブリストハッシュの初期化
init_zobrist();
// ビームサーチでカードを選択
vector<vector<int>> best_selections = beam_search();
// 最良の解を求める
vector<pair<int, int>> best_operations;
double best_score = 1e18;
// 焼きなましの共通バッファ
static vector<Card> sim_cards;
for (const auto& selection : best_selections) {
vector<pair<int, int>> operations = simulated_annealing(selection);
// 最終スコアを計算
sim_cards = cards;
for (const auto& op : operations) {
merge_cards(sim_cards[op.first], sim_cards[op.second]);
}
double score = calculate_score(sim_cards[0].front_diff, sim_cards[0].back_diff);
if (score < best_score) {
best_score = score;
best_operations = operations;
}
}
// 出力
cout << best_operations.size() << endl;
for (const auto& op : best_operations) {
cout << op.first + 1 << " " << op.second + 1 << endl; // 1-indexed
}
return 0;
}