結果
| 問題 |
No.5020 Averaging
|
| ユーザー |
 colun
|
| 提出日時 | 2025-04-11 16:32:52 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 805 ms / 1,000 ms |
| コード長 | 19,946 bytes |
| コンパイル時間 | 1,780 ms |
| コンパイル使用メモリ | 135,408 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 38,090,399 |
| 最終ジャッジ日時 | 2025-04-11 16:33:37 |
| 合計ジャッジ時間 | 45,034 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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は必ず含める
- 残りのN-1枚のカードからランダムに19枚を選択（計20枚）
- 一定回数のランダム選択を行い、それぞれの選択に対して焼きなましを適用
- 評価関数：最終的なカード1の表裏の値と0の差の最大値（max(|A'_1|,|B'_1|)）
- デバッグ情報の出力：
- 選択したカード集合の表の合計値と平均値
- 選択したカード集合の裏の合計値と平均値
- 選択したカードの表と裏の値をPython形式のリストで出力
### 操作順序最適化（焼きなまし）
- ランダムサンプリングで選んだカード集合について、カード1と混合する順序を最適化
- 常に50回の操作を行うために選んだカードを循環使用
- 選択されたカードが50個未満の場合は循環させて繰り返し使用
- 各操作では必ずカード1が含まれる
- 焼きなましのパラメータ
- 初期温度：10.0
- 冷却率：0.995
- 実行時間：0.3秒
- 状態表現：カード1と他のカードを混合する順序の配列
- 遷移操作
- 隣接する操作の入れ替え
- ランダムな位置の操作の入れ替え
- 評価関数：最終的なカード1の表裏の値と0の差の最大値
### 最終出力
- 最良の解から操作回数Xと各操作のカード番号ペア(u_i, v_i)を出力
### 実装詳細
- 差分表現を用いたカード値の更新処理
- カード組み合わせ時の平均値計算（小数点以下切り捨て）
- 一定時間内で複数のランダムサンプリングと焼きなましを繰り返し実行
- 複数の試行から最良解を選択
## メモ
- 表と裏の同時最適化が重要
- 正負の符号が異なるカードを組み合わせると0に近づきやすい
- ランダムサンプリングで多様な組み合わせを試し、良い解を見つける
- 最終スコアは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__
#include <iomanip>
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 SELECTED_CARDS = 20; // 選択するカード数
constexpr int MAX_ITERATIONS = 10; // ランダムサンプリングの繰り返し回数
constexpr double SA_TIME_LIMIT = 0.1; // 0.3→0.1に短縮
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_diff; // 目標値からの差分（表）
int64_t back_diff; // 目標値からの差分（裏）
Card() : front_diff(0), back_diff(0) {}
Card(int64_t f, int64_t b) : front_diff(f - TARGET_VALUE), back_diff(b - TARGET_VALUE) {}
// 実際の値を取得
int64_t front() const { return front_diff + TARGET_VALUE; }
int64_t back() const { return back_diff + TARGET_VALUE; }
};
// 焼きなましの状態
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;
// カードの混合操作
void merge_cards(Card& card_a, Card& card_b) {
int64_t new_front_diff = (card_a.front_diff + card_b.front_diff) / 2;
int64_t new_back_diff = (card_a.back_diff + card_b.back_diff) / 2;
card_a.front_diff = new_front_diff;
card_b.front_diff = new_front_diff;
card_a.back_diff = new_back_diff;
card_b.back_diff = new_back_diff;
}
// スコア計算（maxの絶対値）
double calculate_score(int64_t front_diff, int64_t back_diff) {
return max(abs(front_diff), abs(back_diff));
}
// ランダムにカードを選択
vector<int> random_selection() {
static vector<int> selected_cards;
selected_cards.clear();
selected_cards.push_back(0); // カード1は必ず含める
static vector<int> candidates;
if (candidates.empty()) {
// 初回のみ作成
candidates.reserve(N);
for (int i = 1; i < N; ++i) {
candidates.push_back(i);
}
}
shuffle(candidates.begin(), candidates.end(), rng);
// 19枚追加
for (int i = 0; i < SELECTED_CARDS - 1 && i < (int)candidates.size(); ++i) {
selected_cards.push_back(candidates[i]);
}
return selected_cards;
}
// 焼きなましで操作順序を最適化
vector<pair<int, int>> simulated_annealing(const vector<int>& selected_cards) {
TIMER();
// 常に50回の操作を行うためにカードを選択する
static vector<int> operations;
operations.clear();
operations.reserve(MAX_OPERATIONS);
// 固定サイズになるように選択
for (size_t i = 1; i < selected_cards.size() && operations.size() < MAX_OPERATIONS; ++i) {
operations.push_back(selected_cards[i]);
}
// MAX_OPERATIONSに満たない場合は有効なカードを繰り返し追加
while (operations.size() < MAX_OPERATIONS) {
operations.push_back(operations[operations.size() % (selected_cards.size() - 1)]);
}
// 最良の解を保存
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++;
// 遷移操作：順序の入れ替え
static vector<int> new_operations;
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 % 500 == 0) {
temp *= SA_COOLING_RATE;
}
}
// 操作列に変換（常に50回）
static vector<pair<int, int>> result;
result.clear();
result.reserve(MAX_OPERATIONS);
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);
}
// 最良の解を保存
static vector<pair<int, int>> best_operations;
double best_score = 1e18;
// 一時バッファ
static vector<Card> sim_cards;
// 残り時間（約0.8秒）
double start_time = getTime();
double time_limit = 0.75;
// ランダムサンプリングと焼きなましを繰り返す
int iteration = 0;
while (getTime() - start_time < time_limit) {
iteration++;
// ランダムにカードを選択
vector<int> selected_cards = random_selection();
#ifdef __local__
// 選択したカード集合の表裏の合計値と平均値を計算
int64_t front_sum = 0;
int64_t back_sum = 0;
for (size_t j = 0; j < selected_cards.size(); ++j) {
front_sum += cards[selected_cards[j]].front();
back_sum += cards[selected_cards[j]].back();
}
double front_avg = static_cast<double>(front_sum) / selected_cards.size();
double back_avg = static_cast<double>(back_sum) / selected_cards.size();
cerr << "Iteration " << iteration << ": "
<< "Selected cards (" << selected_cards.size() << "): "
<< "Front sum = " << front_sum << ", "
<< "Front avg = " << front_avg << ", "
<< "Back sum = " << back_sum << ", "
<< "Back avg = " << back_avg << endl;
// 選択したカードの表と裏の値のリストをPython形式で表示
cerr << "selected_cards = [" << endl;
for (size_t j = 0; j < selected_cards.size(); ++j) {
int card_idx = selected_cards[j];
cerr << " [" << card_idx + 1 << ", "
<< cards[card_idx].front() << ", "
<< cards[card_idx].back() << "]";
if (j < selected_cards.size() - 1) {
cerr << ",";
}
cerr << endl;
}
cerr << "]" << endl;
#endif
// 焼きなましで操作順序を最適化
vector<pair<int, int>> operations = simulated_annealing(selected_cards);
// 最終スコアを計算
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);
#ifdef __local__
cerr << "Iteration " << iteration << ": Score = " << score
<< " (Front = " << sim_cards[0].front()
<< ", Back = " << sim_cards[0].back() << ")" << endl;
#endif
if (score < best_score) {
best_score = score;
best_operations = operations;
#ifdef __local__
cerr << "New best solution found! Score = " << score << endl;
#endif
}
}
#ifdef __local__
cerr << "Total iterations: " << iteration << endl;
cerr << "Final best score: " << best_score << endl;
// 最終解のシミュレーション
sim_cards = cards;
for (const auto& op : best_operations) {
merge_cards(sim_cards[op.first], sim_cards[op.second]);
}
cerr << "Final card 1: Front = " << sim_cards[0].front() << ", Back = " << sim_cards[0].back() << endl;
cerr << "Diff from target: Front = " << abs(sim_cards[0].front_diff) << ", Back = " << abs(sim_cards[0].back_diff) << endl;
#endif
// 出力
cout << best_operations.size() << endl;
for (const auto& op : best_operations) {
cout << op.first + 1 << " " << op.second + 1 << endl; // 1-indexed
}
return 0;
}