AHC043( https://atcoder.jp/contests/ahc043/tasks/ahc043_a )に参加したので、解法や工夫した点を語っていきます
問題
50×50の区画の土地があって、そこに駅と線路を建設しようという問題です。
50~1600人の人がいて、各人の家（赤）と職場（青）が与えられ、家と職場の間が線路で繋がっている場合はその距離（マンハッタン距離）だけ収入が与えられます。逆に、駅や線路の建設にはコストがかかります。
ターン数が決められているので、最終的な所持金を高くすることが目的となります
細かい条件は色々ありますが、ざっくり以下の点が特徴的です
- 駅の建設コストは線路に比べてかなり高い
- 家や職場から距離2以下に駅があれば利用可能
- 駅や線路を建設する以外にも、何もしないターンを作ることもできる
- 線路については形状まで決める必要がある
出典：https://atcoder.jp/contests/ahc043/tasks/ahc043_a
ざっくり解法
最終的な解法はざっくり以下の2段階です
- 駅の位置と順序をビームサーチで決定
- 幅優先探索で実際に駅を建設
最終的なコードはこちらになります
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <optional>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <utility>
// 型や定数の定義
using namespace std;
using Pos = pair<int, int>;
const int EMPTY = -1;
const int DO_NOTHING = -1;
const int STATION = 0;
const int RAIL_HORIZONTAL = 1;
const int RAIL_VERTICAL = 2;
const int RAIL_LEFT_DOWN = 3;
const int RAIL_LEFT_UP = 4;
const int RAIL_RIGHT_UP = 5;
const int RAIL_RIGHT_DOWN = 6;
const int COST_STATION = 5000;
const int COST_RAIL = 100;
const int PLAN_MAX_DEPTH = 200;
const int PLAN_MAX_CANDIDATES_EACH_DEPTH = 30;
const int PLAN_MAX_CANDIDATES_EACH_ROUTE = 1; // 1の場合のみ最適化されて高速
const int PLAN_MAX_CANDIDATES_DEPTH1 = 300;
const int TOTAL_DECREASE_ALLOWANCE = 10000;
const double PLAN_TIME_LIMIT = 12.8;
// DIRECTION4, NEAR_DIRECTIONS の定義
vector<Pos> DIRECTION4 = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<Pos> NEAR_DIRECTIONS = {{0, 2}, {0, -2}, {2, 0}, {-2, 0}, {1, 1}, {1, -1}, {-1, 1},
{-1, -1}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {0, 0}};
// 計算量削減のため、駅の位置の候補は離れた場所のみ
vector<Pos> STATION_BUILDABLE_DIRECTIONS = {{-2, 0}, {2, 0}, {0, -2}, {0, 2}, {0, 0}};
// 環境変数 "ATCODER" の確認
bool IS_ATCODER = ([]() {
const char* s = std::getenv("ATCODER");
if (s == nullptr) {
return false;
}
try {
return std::stoi(s) != 0;
} catch (...) {
return false;
}
})();
// デバッグ出力（ATCODER環境でなければ出力）
template <typename... Args>
void debug(Args... args) {
// if (!IS_ATCODER) {
std::cerr << "debug: ";
((std::cerr << args), ...);
std::cerr << std::endl;
// }
}
// ATCODER環境でのみ出力
void print_if_atcoder(const std::string& msg) {
if (IS_ATCODER) {
std::cout << msg << std::endl;
}
}
// pair 用のハッシュ関数（unordered_map 用）
struct pair_hash {
template <class T1, class T2>
std::size_t operator()(const pair<T1, T2>& p) const {
auto h1 = hash<T1>{}(p.first);
auto h2 = hash<T2>{}(p.second);
return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2));
}
};
// DIRECTION_TUPLE_MAP_RAIL の定義（キー： (方向, 次の方向) のペア）
using DirPair = pair<Pos, Pos>;
map<DirPair, int> DIRECTION_TUPLE_MAP_RAIL;
void initRailMap() {
DIRECTION_TUPLE_MAP_RAIL[{{0, 1}, {0, 1}}] = RAIL_HORIZONTAL;
DIRECTION_TUPLE_MAP_RAIL[{{0, 1}, {1, 0}}] = RAIL_LEFT_DOWN;
DIRECTION_TUPLE_MAP_RAIL[{{0, 1}, {-1, 0}}] = RAIL_LEFT_UP;
DIRECTION_TUPLE_MAP_RAIL[{{1, 0}, {0, 1}}] = RAIL_RIGHT_UP;
DIRECTION_TUPLE_MAP_RAIL[{{1, 0}, {1, 0}}] = RAIL_VERTICAL;
DIRECTION_TUPLE_MAP_RAIL[{{1, 0}, {0, -1}}] = RAIL_LEFT_UP;
DIRECTION_TUPLE_MAP_RAIL[{{0, -1}, {1, 0}}] = RAIL_RIGHT_DOWN;
DIRECTION_TUPLE_MAP_RAIL[{{0, -1}, {0, -1}}] = RAIL_HORIZONTAL;
DIRECTION_TUPLE_MAP_RAIL[{{0, -1}, {-1, 0}}] = RAIL_RIGHT_UP;
DIRECTION_TUPLE_MAP_RAIL[{{-1, 0}, {0, -1}}] = RAIL_LEFT_DOWN;
DIRECTION_TUPLE_MAP_RAIL[{{-1, 0}, {-1, 0}}] = RAIL_VERTICAL;
DIRECTION_TUPLE_MAP_RAIL[{{-1, 0}, {0, 1}}] = RAIL_RIGHT_DOWN;
}
// 現在時刻（秒）を返す関数
double get_current_time() {
using namespace std::chrono;
auto now = high_resolution_clock::now();
duration<double> sec = now.time_since_epoch();
return sec.count();
}
// Manhattan 距離
int distance_pos(const Pos& a, const Pos& b) {
return abs(a.first - b.first) + abs(a.second - b.second);
}
// Union-Find クラス
class UnionFind {
public:
int n;
vector<int> parents;
UnionFind(int n) : n(n), parents(n * n, -1) {
}
int find_root(int idx) {
if (parents[idx] < 0) {
return idx;
}
return parents[idx] = find_root(parents[idx]);
}
bool is_same(const Pos& p, const Pos& q) {
int p_idx = p.first * n + p.second;
int q_idx = q.first * n + q.second;
return find_root(p_idx) == find_root(q_idx);
}
void unite(const Pos& p, const Pos& q) {
int p_idx = p.first * n + p.second;
int q_idx = q.first * n + q.second;
int p_root = find_root(p_idx);
int q_root = find_root(q_idx);
if (p_root != q_root) {
int p_size = -parents[p_root];
int q_size = -parents[q_root];
if (p_size > q_size) {
swap(p_root, q_root);
}
parents[q_root] += parents[p_root];
parents[p_root] = q_root;
}
}
};
// Action クラス
class Action {
public:
int type;
Pos pos;
Action(int type, Pos pos) : type(type), pos(pos) {
}
string toString() const {
if (type == DO_NOTHING) {
return "-1";
} else {
return to_string(type) + " " + to_string(pos.first) + " " + to_string(pos.second);
}
}
};
// Result クラス
class Result {
public:
vector<Action> actions;
int score;
Result(const vector<Action>& actions, int score) : actions(actions), score(score) {
}
string toString() const {
string s;
for (size_t i = 0; i < actions.size(); i++) {
s += actions[i].toString();
if (i + 1 < actions.size()) {
s += "\n";
}
}
return s;
}
};
// Field クラス
class Field {
public:
int N;
vector<vector<int>> rail;
UnionFind uf;
Field(int N) : N(N), rail(N, vector<int>(N, EMPTY)), uf(N) {
}
void build(int type, int r, int c) {
if (rail[r][c] == type || rail[r][c] == STATION) {
return;
}
if (rail[r][c] != EMPTY && type != STATION) {
throw runtime_error("invalid build: " + to_string(type) + " " + to_string(r) + " " + to_string(c));
}
rail[r][c] = type;
// 上
if (type == STATION || type == RAIL_VERTICAL || type == RAIL_LEFT_UP || type == RAIL_RIGHT_UP) {
if (r > 0 && (rail[r - 1][c] == STATION || rail[r - 1][c] == RAIL_VERTICAL || rail[r - 1][c] == RAIL_LEFT_DOWN ||
rail[r - 1][c] == RAIL_RIGHT_DOWN)) {
uf.unite({r, c}, {r - 1, c});
}
}
// 下
if (type == STATION || type == RAIL_VERTICAL || type == RAIL_LEFT_DOWN || type == RAIL_RIGHT_DOWN) {
if (r < N - 1 && (rail[r + 1][c] == STATION || rail[r + 1][c] == RAIL_VERTICAL ||
rail[r + 1][c] == RAIL_LEFT_UP || rail[r + 1][c] == RAIL_RIGHT_UP)) {
uf.unite({r, c}, {r + 1, c});
}
}
// 左
if (type == STATION || type == RAIL_HORIZONTAL || type == RAIL_LEFT_DOWN || type == RAIL_LEFT_UP) {
if (c > 0 && (rail[r][c - 1] == STATION || rail[r][c - 1] == RAIL_HORIZONTAL ||
rail[r][c - 1] == RAIL_RIGHT_DOWN || rail[r][c - 1] == RAIL_RIGHT_UP)) {
uf.unite({r, c}, {r, c - 1});
}
}
// 右
if (type == STATION || type == RAIL_HORIZONTAL || type == RAIL_RIGHT_DOWN || type == RAIL_RIGHT_UP) {
if (c < N - 1 && (rail[r][c + 1] == STATION || rail[r][c + 1] == RAIL_HORIZONTAL ||
rail[r][c + 1] == RAIL_LEFT_DOWN || rail[r][c + 1] == RAIL_LEFT_UP)) {
uf.unite({r, c}, {r, c + 1});
}
}
}
bool is_connected(const Pos& s, const Pos& t) {
vector<Pos> stations0 = collect_stations(s);
vector<Pos> stations1 = collect_stations(t);
for (const auto& station0 : stations0) {
for (const auto& station1 : stations1) {
if (uf.is_same(station0, station1)) {
return true;
}
}
}
return false;
}
vector<Pos> collect_stations(const Pos& pos) {
vector<Pos> stations;
for (int dr = -2; dr <= 2; dr++) {
for (int dc = -2; dc <= 2; dc++) {
if (abs(dr) + abs(dc) > 2) {
continue;
}
int r = pos.first + dr, c = pos.second + dc;
if (r >= 0 && r < N && c >= 0 && c < N && rail[r][c] == STATION) {
stations.push_back({r, c});
}
}
}
return stations;
}
};
// StationUtils クラス
class StationUtils {
public:
static Pos modify_station_pos(const Pos& station, int N) {
int r = station.first, c = station.second;
if (r == 0) {
r = 1;
}
if (r == N - 1) {
r = N - 2;
}
if (c == 0) {
c = 1;
}
if (c == N - 1) {
c = N - 2;
}
return Pos(r, c);
}
static optional<vector<Pos>> search_connect_station(const Pos& station, Field& field, int n) {
// rail のディープコピー
vector<vector<int>> rail = field.rail;
queue<tuple<int, int, vector<Pos>>> q;
q.push({station.first, station.second, vector<Pos>{station}});
while (!q.empty()) {
auto [r, c, history] = q.front();
q.pop();
vector<Pos> directions = DIRECTION4;
if (history.size() % 2 == 0) {
reverse(directions.begin(), directions.end());
}
for (auto [dr, dc] : directions) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
if (rail[nr][nc] == STATION) {
auto new_history = history;
new_history.push_back({nr, nc});
return new_history;
}
if (rail[nr][nc] == EMPTY) {
rail[nr][nc] = RAIL_HORIZONTAL; // 適当なレール
auto new_history = history;
new_history.push_back({nr, nc});
q.push({nr, nc, new_history});
}
}
}
}
return nullopt;
}
};
// Solver クラス
class Solver {
public:
int N, M, K, T;
vector<Pos> home, workplace;
Field field;
int money;
vector<Action> actions;
int income;
vector<tuple<int, int>> expected_total_time = {};
Solver(int N, int M, int K, int T, const vector<Pos>& home, const vector<Pos>& workplace)
: N(N), M(M), K(K), T(T), home(home), workplace(workplace), field(N), money(K), income(0) {
}
int calc_income() {
int inc = 0;
for (int i = 0; i < M; i++) {
if (field.is_connected(home[i], workplace[i])) {
inc += distance_pos(home[i], workplace[i]);
}
}
// debug("income=", inc);
return inc;
}
void build_rail(int type, int r, int c) {
if ((int)actions.size() >= T) {
return;
}
while (money < COST_RAIL) {
// debug("can't build rail: ", type, " ", r, " ", c, " money=",
// money);
build_nothing();
if ((int)actions.size() >= T) {
return;
}
}
field.build(type, r, c);
money -= COST_RAIL;
actions.push_back(Action(type, {r, c}));
money += income;
}
void build_station(int r, int c) {
if ((int)actions.size() >= T) {
return;
}
while (money < COST_STATION) {
// debug("can't build station: ", r, " ", c, " money=", money);
build_nothing();
if ((int)actions.size() >= T) {
return;
}
}
// debug("build station: ", r, " ", c);
field.build(STATION, r, c);
money -= COST_STATION;
actions.push_back(Action(STATION, {r, c}));
income = calc_income();
money += income;
expected_total_time.push_back({money + income * (T - (int)actions.size()), (int)actions.size()});
}
void build_nothing() {
actions.push_back(Action(DO_NOTHING, {0, 0}));
money += income;
}
Result execute(const vector<Pos>& stations) {
unordered_set<Pos, pair_hash> built_stations;
for (auto station : stations) {
if (built_stations.empty()) {
build_station(station.first, station.second);
built_stations.insert(station);
continue;
}
if (field.rail[station.first][station.second] != EMPTY) {
build_station(station.first, station.second);
built_stations.insert(station);
continue;
}
auto historyOpt = StationUtils::search_connect_station(station, field, N);
if (!historyOpt.has_value()) {
debug("can't connect station: ", station.first, " ", station.second);
continue;
}
auto history = historyOpt.value();
// 各3点ごとの組でレールを敷設
for (size_t i = 0; i + 2 < history.size(); i++) {
Pos pos_prev = history[i];
Pos pos_now = history[i + 1];
Pos pos_next = history[i + 2];
Pos direction = {pos_now.first - pos_prev.first, pos_now.second - pos_prev.second};
Pos direction_next = {pos_next.first - pos_now.first, pos_next.second - pos_now.second};
DirPair key = {direction, direction_next};
int rail_type = DIRECTION_TUPLE_MAP_RAIL[key];
build_rail(rail_type, pos_now.first, pos_now.second);
}
build_station(station.first, station.second);
built_stations.insert(station);
}
// 想定スコアが最大となる時点で打ち切る（planには建設が速くなりがちなため必要以上に長くなることがある）
int expected_income;
int time_for_max_expected_income;
if (expected_total_time.empty()) {
expected_income = 0;
time_for_max_expected_income = 0;
} else {
tuple<int, int> max_expected_income = *max_element(expected_total_time.begin(), expected_total_time.end());
expected_income = get<0>(max_expected_income);
time_for_max_expected_income = get<1>(max_expected_income);
}
vector<Action> actions_trim(actions.begin(), actions.begin() + time_for_max_expected_income);
actions_trim.insert(actions_trim.end(), T - time_for_max_expected_income, Action(DO_NOTHING, {0, 0}));
return Result(actions_trim, expected_income);
}
};
// Planner クラス
class Planner {
public:
int N, M, K, T;
vector<Pos> home, workplace;
unordered_map<Pos, vector<int>, pair_hash> pos_map_list_near_idx_home;
unordered_map<Pos, vector<int>, pair_hash> pos_map_list_near_idx_workplace;
// Planner 内で用いる Route 構造体
struct Route {
int total;
int last_connect;
int final_gain;
vector<Pos> stations;
};
Planner(int N, int M, int K, int T, const vector<Pos>& home, const vector<Pos>& workplace)
: N(N), M(M), K(K), T(T), home(home), workplace(workplace) {
for (int i = 0; i < M; i++) {
for (auto& dir : NEAR_DIRECTIONS) {
int r = home[i].first + dir.first, c = home[i].second + dir.second;
pos_map_list_near_idx_home[{r, c}].push_back(i);
r = workplace[i].first + dir.first;
c = workplace[i].second + dir.second;
pos_map_list_near_idx_workplace[{r, c}].push_back(i);
}
}
}
// 想定スコア計算（直線的に繋ぐという前提を置いているので、高めに出る）
tuple<int, int> _calc_score(
int prev_total, int prev_last_connect, int prev_gain, int cost, int new_gain, int min_turn
) {
if (prev_gain == 0) {
return {
prev_total - cost + (T - prev_last_connect - min_turn + 1) * new_gain, prev_last_connect + min_turn
}; // 初期接続時は必ず残金が存在する
}
int zannkinn_last_connect =
prev_total - (T - prev_last_connect + 1) * prev_gain + prev_gain; // 繋がった時点でgainがもらえる
int next_connect =
max((cost - zannkinn_last_connect - 1) / prev_gain + 1 + 1,
min_turn); // 切り上げと、建設->集金の流れなので+1
// 繋がったターンからgainが得られるので+1
return {
prev_total - cost + (T - prev_last_connect - next_connect + 1) * (new_gain - prev_gain),
prev_last_connect + next_connect
};
}
// 次のルート候補を計算
vector<Route> _calc_next_route(const vector<Route>& prev_route_choices, int max_total) {
vector<Route> route_choices;
for (const Route& route : prev_route_choices) {
// 既存の駅の近くにhome/workspaceがあるidxの人を集める
unordered_set<int> set_near_idx_home;
unordered_set<int> set_near_idx_workplace;
for (const Pos& station : route.stations) {
if (pos_map_list_near_idx_home.count(station)) {
set_near_idx_home.insert(
pos_map_list_near_idx_home[station].begin(), pos_map_list_near_idx_home[station].end()
);
}
if (pos_map_list_near_idx_workplace.count(station)) {
set_near_idx_workplace.insert(
pos_map_list_near_idx_workplace[station].begin(), pos_map_list_near_idx_workplace[station].end()
);
}
}
// 既存の駅の近くにhome/workspaceの片方のみがある人（未追加の人）のidxを集める
unordered_set<int> set_home_near_idx;
for (int idx : set_near_idx_home) {
if (!set_near_idx_workplace.count(idx)) {
set_home_near_idx.insert(idx);
}
}
unordered_set<int> set_workspace_near_idx;
for (int idx : set_near_idx_workplace) {
if (!set_near_idx_home.count(idx)) {
set_workspace_near_idx.insert(idx);
}
}
vector<Route> route_choices_i;
for (int idx : set_home_near_idx) {
Pos best_new_station = {-1, -1};
int best_near_idx_count = 0;
for (auto& dir : STATION_BUILDABLE_DIRECTIONS) {
Pos new_station = Pos(workplace[idx].first + dir.first, workplace[idx].second + dir.second);
// 端の駅は避ける
if (new_station.first <= 0 || new_station.first >= N - 1 || new_station.second <= 0 ||
new_station.second >= N - 1) {
continue;
}
// 新駅の近くにhome/workspaceがあるidxの人で未追加の人
unordered_set<int> set_near_idx_from_new_station;
for (int idx2 : pos_map_list_near_idx_home[new_station]) {
if (set_home_near_idx.count(idx2) == 0) {
set_near_idx_from_new_station.insert(idx2);
}
}
for (int idx2 : pos_map_list_near_idx_workplace[new_station]) {
if (set_workspace_near_idx.count(idx2) == 0) {
set_near_idx_from_new_station.insert(idx2);
}
}
if ((int)set_near_idx_from_new_station.size() >= best_near_idx_count) {
best_new_station = new_station;
best_near_idx_count = set_near_idx_from_new_station.size();
}
}
auto new_route = _add_new_station(best_new_station, route, set_home_near_idx, set_workspace_near_idx);
if (new_route.total > max_total - TOTAL_DECREASE_ALLOWANCE) {
route_choices_i.push_back(new_route);
}
}
for (int idx : set_workspace_near_idx) {
Pos best_new_station = {-1, -1};
int best_near_idx_count = 0;
for (auto& dir : STATION_BUILDABLE_DIRECTIONS) {
Pos new_station = Pos(home[idx].first + dir.first, home[idx].second + dir.second);
// 端の駅は避ける
if (new_station.first <= 0 || new_station.first >= N - 1 || new_station.second <= 0 ||
new_station.second >= N - 1) {
continue;
}
// 新駅の近くにhome/workspaceがあるidxの人で未追加の人
unordered_set<int> set_near_idx_from_new_station;
for (int idx2 : pos_map_list_near_idx_home[new_station]) {
if (set_home_near_idx.count(idx2) == 0) {
set_near_idx_from_new_station.insert(idx2);
}
}
for (int idx2 : pos_map_list_near_idx_workplace[new_station]) {
if (set_workspace_near_idx.count(idx2) == 0) {
set_near_idx_from_new_station.insert(idx2);
}
}
if ((int)set_near_idx_from_new_station.size() >= best_near_idx_count) {
best_new_station = new_station;
best_near_idx_count = set_near_idx_from_new_station.size();
}
}
auto new_route = _add_new_station(best_new_station, route, set_home_near_idx, set_workspace_near_idx);
if (new_route.total > max_total - TOTAL_DECREASE_ALLOWANCE) {
route_choices_i.push_back(new_route);
}
}
int sort_length = min((int)route_choices_i.size(), PLAN_MAX_CANDIDATES_EACH_ROUTE);
partial_sort(
route_choices_i.begin(), route_choices_i.begin() + sort_length, route_choices_i.end(),
[](const Route& a, const Route& b) { return a.total > b.total; }
);
route_choices.insert(route_choices.end(), route_choices_i.begin(), route_choices_i.begin() + sort_length);
}
int sort_length = min((int)route_choices.size(), PLAN_MAX_CANDIDATES_EACH_DEPTH);
partial_sort(
route_choices.begin(), route_choices.begin() + sort_length, route_choices.end(),
[](const Route& a, const Route& b) { return a.total > b.total; }
);
vector<Route> router_choices_slice(route_choices.begin(), route_choices.begin() + sort_length);
return router_choices_slice;
}
Route _add_new_station(
const Pos& new_station, const Route& route, const unordered_set<int>& set_home_near_idx,
const unordered_set<int>& set_workspace_near_idx
) {
int dist = INT_MAX;
for (auto& s : route.stations) {
dist = min(dist, distance_pos(new_station, s));
}
// 駅の付近にhome/workspaceがあるidxの人でworkplace/homeが既存の駅に近い人は追加
unordered_set<int> set_near_idx_from_new_station;
for (int idx2 : pos_map_list_near_idx_home[new_station]) {
if (set_home_near_idx.count(idx2) == 0 && set_workspace_near_idx.count(idx2)) {
set_near_idx_from_new_station.insert(idx2);
}
}
for (int idx2 : pos_map_list_near_idx_workplace[new_station]) {
if (set_workspace_near_idx.count(idx2) == 0 && set_home_near_idx.count(idx2)) {
set_near_idx_from_new_station.insert(idx2);
}
}
int new_gain = route.final_gain;
for (int idx2 : set_near_idx_from_new_station) {
new_gain += distance_pos(home[idx2], workplace[idx2]);
}
auto [new_total, new_last_connect] = _calc_score(
route.total, route.last_connect, route.final_gain, COST_STATION + COST_RAIL * (dist - 1), new_gain, dist
);
Route new_route = route;
new_route.total = new_total;
new_route.last_connect = new_last_connect;
new_route.final_gain = new_gain;
new_route.stations.push_back(new_station);
return new_route;
}
// 駅配置計画
vector<Pos> plan(double timeout) {
int max_distance = (K - COST_STATION * 2) / COST_RAIL;
vector<pair<int, int>> list_distance_person_idx;
for (int i = 0; i < M; i++) {
list_distance_person_idx.push_back({distance_pos(home[i], workplace[i]), i});
}
sort(list_distance_person_idx.begin(), list_distance_person_idx.end());
int max_valid_index = list_distance_person_idx.size() - 1;
for (size_t i = 0; i < list_distance_person_idx.size(); i++) {
if (list_distance_person_idx[i].first >= max_distance) {
max_valid_index = i - 1;
break;
}
}
if (max_valid_index < 0) {
max_valid_index = 0;
}
int max_total = K;
vector<Route> route_stack;
route_stack.push_back(Route{K, 0, 0, {}});
vector<Route> route_choices_i;
int start_index = max(0, max_valid_index - PLAN_MAX_CANDIDATES_DEPTH1);
for (int i = start_index; i <= max_valid_index && i < (int)list_distance_person_idx.size(); i++) {
int idx = list_distance_person_idx[i].second;
Pos best_station_home = {-1, -1};
Pos best_new_workspace = {-1, -1};
int best_near_idx_count = 0;
for (auto& dir1 : NEAR_DIRECTIONS) {
Pos station_home = {home[idx].first + dir1.first, home[idx].second + dir1.second};
// 端の駅は避ける
if (station_home.first <= 0 || station_home.first >= N - 1 || station_home.second <= 0 ||
station_home.second >= N - 1) {
continue;
}
for (auto& dir2 : NEAR_DIRECTIONS) {
Pos station_workplace = {workplace[idx].first + dir2.first, workplace[idx].second + dir2.second};
if (distance_pos(station_home, station_workplace) > max_distance) {
continue;
}
// 端の駅は避ける
if (station_workplace.first <= 0 || station_workplace.first >= N - 1 || station_workplace.second <= 0 ||
station_workplace.second >= N - 1) {
continue;
}
// 新駅の近くにhome/workspaceがあるidxの人で未追加の人
unordered_set<int> set_near_idx_from_new_station;
for (int idx2 : pos_map_list_near_idx_home[station_home]) {
set_near_idx_from_new_station.insert(idx2);
}
for (int idx2 : pos_map_list_near_idx_workplace[station_home]) {
set_near_idx_from_new_station.insert(idx2);
}
for (int idx2 : pos_map_list_near_idx_home[station_workplace]) {
set_near_idx_from_new_station.insert(idx2);
}
for (int idx2 : pos_map_list_near_idx_workplace[station_workplace]) {
set_near_idx_from_new_station.insert(idx2);
}
if ((int)set_near_idx_from_new_station.size() >= best_near_idx_count) {
best_station_home = station_home;
best_new_workspace = station_workplace;
best_near_idx_count = set_near_idx_from_new_station.size();
}
}
}
Route route_prev = {K - COST_STATION, 1, 0, {best_station_home}};
unordered_set<int> set_near_idx_home;
for (int idx : pos_map_list_near_idx_home[best_station_home]) {
set_near_idx_home.insert(idx);
}
unordered_set<int> set_near_idx_workplace;
for (int idx : pos_map_list_near_idx_workplace[best_station_home]) {
set_near_idx_workplace.insert(idx);
}
unordered_set<int> set_home_near_idx;
for (int idx : set_near_idx_home) {
if (set_near_idx_workplace.count(idx) == 0) {
set_home_near_idx.insert(idx);
}
}
unordered_set<int> set_workspace_near_idx;
for (int idx : set_near_idx_workplace) {
if (set_near_idx_home.count(idx) == 0) {
set_workspace_near_idx.insert(idx);
}
}
auto new_route = _add_new_station(best_new_workspace, route_prev, set_home_near_idx, set_workspace_near_idx);
if (new_route.total > max_total - TOTAL_DECREASE_ALLOWANCE) {
route_choices_i.push_back(new_route);
}
}
int sort_length = min((int)route_choices_i.size(), PLAN_MAX_CANDIDATES_EACH_DEPTH);
partial_sort(
route_choices_i.begin(), route_choices_i.begin() + sort_length, route_choices_i.end(),
[](const Route& a, const Route& b) { return a.total > b.total; }
);
vector<Route> route_choices(route_choices_i.begin(), route_choices_i.begin() + sort_length);
route_stack.insert(route_stack.end(), route_choices.begin(), route_choices.end());
for (int depth = 1; depth < PLAN_MAX_DEPTH; depth++) {
double current_time = get_current_time();
if (current_time > timeout) {
debug("finish by time: depth=", depth);
break;
}
route_choices = _calc_next_route(route_choices, max_total);
if (route_choices.empty()) {
debug("finish by no route: depth=", depth);
break;
}
max_total = max(max_total, route_choices[0].total);
route_stack.insert(route_stack.end(), route_choices.begin(), route_choices.end());
}
auto best_route = *max_element(route_stack.begin(), route_stack.end(), [](const Route& a, const Route& b) {
return a.total < b.total;
});
debug(
"best of route=", best_route.total, ", ", best_route.last_connect, ", ", best_route.final_gain, ", ",
best_route.stations.size()
);
return best_route.stations;
}
};
//////////////////////
// main 関数
//////////////////////
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
initRailMap();
int N, M, K, T;
cin >> N >> M >> K >> T;
vector<Pos> home, workplace;
for (int i = 0; i < M; i++) {
int r0, c0, r1, c1;
cin >> r0 >> c0 >> r1 >> c1;
home.push_back({r0, c0});
workplace.push_back({r1, c1});
}
Planner planner(N, M, K, T, home, workplace);
double start_time = get_current_time();
double timeout = start_time + PLAN_TIME_LIMIT;
vector<Pos> stations = planner.plan(timeout);
Solver solver(N, M, K, T, home, workplace);
Result result = solver.execute(stations);
print_if_atcoder(result.toString());
ofstream fout("output.txt");
fout << result.toString();
fout.close();
debug("score=", result.score, ", time=", get_current_time() - start_time);
return 0;
}
スコア推移
何回かブレイクスルーがあったものの、最終的には打ち手がなくなりスコアが伸び悩む形となりました
（※これは自分の提出履歴から見れる絶対的な得点です。順位表の相対的な得点とは異なります）
最終的には、暫定テスト24.50G、システムテスト974Gで307位でした。
上位は約50Gなので、半分ぐらいのスコアしか取れていないことになります。
サンプルプログラム（スコア不明）
AtCoder側から提供されたサンプルプログラムでは、初期資金で家と職場をつなげる人を一人選び、その人の家と職場を繋いで、あとは待機する実装になっていました
初回提出（スコア2M）
改善点
- 一人繋いだら終わりではなく、総ターン数の半分までは繋げるようにする
- 繋ぐ人は、初期資金で繋げる人のうち、家と職場の距離が遠い人から順番に繋ぐ（駅の建設コストが高いのでできるだけ少ない駅数で高い収入を得られるようにした）
所感
AHC初参加ということもあり、全てが手探りだったので、大きく変更するよりは少しずつ小さな改善を試していたフェーズです。
このとき、アイデアだけ出してコードは生成AIに丸投げして生成させることも試してみましたが、全然うまくいかないといった印象で、実装も自分メインでやるようにしていました
計画フェーズと建設フェーズに分ける（スコア6M）
改善点
- ざっくり、計画フェーズと建設フェーズの2段階で処理するように変更しました
- 計画フェーズでは接続数を5に絞って全探索して、想定収入が一番多い計画を採用します
- 建設フェーズでは、既存の線路をまたぐルートが取れないので、幅優先探索で接続可能なルートを探します
- どうやっても接続できないルートがある場合は、想定収入が次に多い計画を採用します
- なお、効いたかは不明ですが、幅優先探索の探索時は、右,左,上,下の探索順序を偶奇で入れ替えています（できる限り直線的に繋ぐ方が後で邪魔にならないと考えたため）
所感
複数人繋ごうとすると、既存の線路とバッティングするので、そこの解決に苦労しました。ちなみに、幅優先探索を思いついたのは布団の中です。このせいで寝れなくなりました
接続数を増やす（スコア8M）
改善点
- 接続数を16に増やしました
- 制限時間内に収まるようにtimeoutを追加しました
所感
スコアがあまり上がらず、接続数（＝探索する深さ）を増やすことによる改善は限界があることを理解したので、今後は根本的なロジックの改善に着手することになります
既存の駅付近の人のみ探索対象にする（スコア30M）
改善点
- 駅の建設コストが高いので、家と職場の片方は既存の駅を利用できる人のみ対象にすることで、探索範囲を狭めました
- これにより、全線路が一つに繋がるので、諸々の処理がかなり簡略化されました
- ビームサーチにして計算量を減らし、より深く探索する(50)ようにしました。
- このタイミングで、駅の位置がちょうど家か職場と同じ位置でなくても良いことに気づいたので、駅の位置の探索もするようにしています
所感
ここら辺で、そもそも最適化の手法に何があるのかをChatGPTに聞きながら整理しました。その結果、ビームサーチが使えそうということに気づいて、ビームサーチを早速使ってみています
また、深さを深くするとスコアが飛躍的に伸びることに気づいたので、制約を追加して探索する対象を限定するように方針を変えています
最適化の手法の整理
リファクタリングとパラメーター調整（スコア43M）
改善点
- 探索する深さをより深くしました(100)
- リファクタリングしました（ので、diffが見づらく、漏れがあるかもです）
所感
探索する深さを深くすることでスコアが伸びそうだったので、C++に移植することを決意します。移植前にプログラムをリファクタリングしておきました
C++に移植（スコア58M）
改善点
- C++に移植しました
- 探索する深さをより深くしました(200)
所感
移植自体は生成AIにやらせました。いくつか手直ししましたが、概ね動くコードが生成されました。最近のAIはすごい
C++初めて触るので、自分用のチートシートも作ったり、linterを試してみたりしました
計画時の各ステップのスコアをより正確にする（スコア119M）
改善点
- 計画時のスコア計算の精緻化
- かなり適当な計算をしていたので、ちゃんと数式を考え直しました
- ある人の接続時に、ついでに家と職場がつながる人がいる場合にスコア計算に反映させるようにする
- 元々は次のステップで計算するようにしていました
- その他収入計算などの細かいロジックを見直し
所感
プランニングのロジックを全体的に見直して、雑な部分を修正していった感じです。箇条書き2個目の改善はビームサーチで上位数件のみ利用するので、スコアへの反映が1ターン遅れることはかなり影響が大きかった部分かと思います
ただし、この処理は繋がる人がいるかどうかを各分岐で計算する必要があり、かなり時間が掛かるようになった印象です
微調整（スコア133M）
改善点
- スコアが最大となる時点で打ち切り
- 既存の線路との兼ね合いで回り道をする必要があるなど、どうしても計画時点とは誤差が出るので実際に建設していって、スコアが最大になる時点までのアクションのみ採用するようにしました
- 駅の建設位置は、探索せず、未接続の人が多い位置に配置する
- 計算量削減のためです。影響が長期的にしか観測できない可能性が高い部分なので、ロジカルに決めた方が良いのではと考えて実装しました
所感
改善策が思いつかず細かい改善を行なっていました。週末は少し忙しかったこともあり、ここでフィニッシュです。
その他できたらよかったこと
- スコアが低くなる初期配置の傾向をみる
- 機械学習系の海法
- 筆者の本業が機械学習系なので、使ってみたいと思いましたが、そもそも教師データとなる最適解を求めることが無理そうだったので断念しました、、、強化学習系ならワンチャンありそうですが、強化学習は実装が大変で学習も安定しなさそうなので諦めました
まとめ
めちゃくちゃ楽しかったし、勉強になったので参加してよかった！！！