AHC061

Imported from ymduu/AHC061 (AGENTS.md). Install upstream with npx skills add ymduu/AHC061. Copyright stays with the author.

このリポジトリについて

• このリポジトリは競技プログラミングのヒューリスティックな問題を解くためのものである。
• 問題はtask.htmlに記載されている。

タスク実行時の注意

• タスク実行中に気付いたこと、さらなる改善の可能性などがあれば next_Action.txt に追記すること。
• タスク等の不明点についての質問がある場合もこのファイルに追記して伝えること。ユーザーからの解答もこのファイルを通して与えられる。
• Materials に資料が添付されているが、こちらから指示するまで参照しないこと。

テスト方法

入力ファイルは下記のような名前で0000～0099まで与えられることが多い ./tools/in/0001.txt

下記の例のように実行して、テストケース0000～0014の15件の合計スコアをベンチマークとせよ。改善せよというタスクの場合はこのスコアをKPIとする。スコアが大小どちらがよいかは問題を読んで判断すること。

./a.out < $input_file > $output_file 2> $err_file

入出力は下記の形式で行う

• 入力ファイル ./tools/in/0000.txt
• 出力ファイル ./tools/out/out_0000.txt
• エラー出力ファイル ./tools/err/err_0000.txt

テストをbashで自動化したものがあるのでこれを使ってテストすること。 ./run_all_par_sh.sh

タスク完了時に、テスト結果の15ケースのスコアの合計をSummaryに明記すること。

コーディング規約・実装のヒント

• 指示の無い限り言語はC++20で実装する
• TL、焼きなましの開始温度、最終温度などのモデルパラメータはグローバル変数として、定義はコードの先頭部分に置く事。
• なるべく差分更新でスコアを計算できるようなデータの持ち方を考える
• 関数名は PascalCase にせよ。
• クラスのメンバ変数は private なものは m_PascalCase、 public なものは camelCase とせよ。
• 構造体のメンバ変数は camelCase とせよ。
• ポインタ変数は接頭辞に p をつけよ。これは上記のコーディング規約と複合する。例えば、 private メンバのポインタ変数なら、 m_pHogehoge といった具合である。
• ただし、 入力値を保持する構造体のみは例外として、問題文中の変数名をそのまま使用せよ。変数名が大文字 N ならそのまま使用せよ。
• git の差分を管理するために、意味のない空白の増減やコメントの編集は最小限とせよ。
• 次のテンプレートに沿って実装せよ。

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#define _CRT_SECURE_NO_WARNINGS


#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>      // sqrt, floor 用
#include <cstdlib>    // rand, srand
#include <ctime>      // time
#include <chrono>     // 時間計測用
#include <optional>
using namespace std;

// AHC テンプレート

// 入力値 const 参照で引きまわすべし
struct InputData {};
// 出力値
struct OutputData {};

// 解を計算
void Solve(const InputData* input, OutputData& output) {
    // TODO: 実装
}

// 解を出力
void Output(const OutputData& output) {
    // TODO: 実装
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    InputData input{};
	OutputData output{};

    // TODO: 入力値を input に詰める

    Solve(input, output);
    Output(output);

    return 0;
}

出力形式

標準出力

標準出力への形式はtask.htmlに記載の出力の形式を遵守すること

エラー出力

次の項目がある場合は個の順にエラー出力へ出力すること

• 最終ベストスコア
• モデルパラメータ（パラメータチューニングのため）
• 焼きなましのループ回数
• 時間経過ごとのベストスコア(0.1secごと)

焼きなましの実装方法

• 状態のコピーをするよりも、遷移で状態を変更してしまって、受理されなかったら元に戻すようにするとコピーコストがかからない
• 時間計測は毎回行わない
• 乱数を返す関数は焼きなましループの外で定義しておく

焼きなましの方針のヒント

• 遷移には逆遷移を含めた方がよい
• 一部を大きく破壊して貪欲に再構築する遷移が有効なことがある
• 一定時間スコア改善がない場合は初期解からスタートしなおす(kick)が有効なことがある
• 1点だけの変更ではスコアに直接影響しない、複数の条件が集まって始めてスコアが上がるような設定になっている場合は複数の条件をまとめて導入する遷移が有効なことがある

ビームサーチの実装方法

TBD

評価関数の設計

• 得点Pが大きいものを特に重視したい場合、P >> P^x (x>1) のような変換が有効なことがある

高速化TIPS:

• BFS: 探索済リストの初期化を毎回行わず、各BFS開始前にbfscntを適度にインクリメントしてvisitedまたは距離0としてあつかう
• 乱数生成は std::mt19937 をグローバルに保持し、毎回初期化しない
• スコア計算や評価値は差分更新を徹底して O(1) で求められる形を目指す
• 探索で使う配列は使い回し、キャッシュの局所性を意識する