AtCoder Heuristic First-step Vol.1 - 変数・関数一覧と疑似コード
貪欲法の変数一覧
| 変数名 | 説明 |
|---|
| order_count | 注文の総数（固定値 1000） |
| pickup_count | 高橋くんが処理する注文の数（固定値 50） |
| office | AtCoderオフィスの座標 (400, 400) スタート地点、かつゴール地点 |
| restaurants | レストランの座標リスト |
| destinations | 目的地（配達先）の座標リスト |
| orders | 選択した注文のリスト |
| route | 訪問するルートのリスト |
| visited_restaurant | 訪問済みのレストランを記録する |
| current_position | 現在地 |
| total_dist | 総移動距離 |
貪欲法の関数一覧
| 関数名 | 説明 |
|---|
| int Point::dist(const Point& p) | 2つの点のマンハッタン距離を計算する |
| static Input Input::read() | 入力データを読み取る |
| void Output::print() | 解を出力する |
| Output solve(const Input& input) | 問題を解く |
貪欲法の疑似コード
関数 solve(input: Input) -> Output:
変数 orders ← 空のリスト
変数 route ← 空のリスト
変数 visited_restaurant ← 長さ input.order_count の false 配列
route に input.office を追加
変数 current_position ← input.office
変数 total_dist ← 0
ループ (50回): 最も近いレストランを訪問
ループ (50回): 最も近い配達先を訪問
route に input.office を追加
total_dist 更新
戻り値 Output(orders, route)
貪欲法の出力例
50 709 217 838 931 774 366 278 474 538 515 458 970 96 269 744 360 490 107 804 836 995 171 497 408 166 312 813 58 708 915 610 850 715 657 693 418 333 419 688 263 355 656 743 924 325 234 290 449 951 755
102 400 400 407 397 385 394 379 410 381 412 386 434 408 436 441 440 439 463 430 457 416 477 426 488 399 493 372 493 360 493 345 486 335 501 335 512 305 509 298 495 287 516 288 529 276 528 278 539 306 536 310 529 321 539 322 564 335 560 333 555 337 566 323 590 322 589 324 605 355 600 367 602 378 596 385 584 385 566 395 571 407 578 409 579 371 579 367 530 389 525 424 527 422 535 436 529 434 526 451 514 461 521 480 592 604 522 584 472 565 430 556 427 552 316 487 284 450 286 422 198 372 61 359 27 286 69 275 121 270 135 289 137 206 136 157 131 36 62 2 39 0 251 63 355 106 336 109 429 232 482 242 528 235 670 248 682 239 759 136 742 125 668 68 652 7 688 33 799 292 315 263 254 494 369 683 406 757 407 762 353 700 328 677 254 648 120 619 106 578 50 570 34 778 148 778 151 708 532 791 626 797 651 400 400
貪欲法の標準エラー出力
0番目のレストラン: p_708 = (407, 397)
1番目のレストラン: p_216 = (385, 394)
2番目のレストラン: p_837 = (379, 410)
3番目のレストラン: p_930 = (381, 412)
4番目のレストラン: p_773 = (386, 434)
5番目のレストラン: p_365 = (408, 436)
6番目のレストラン: p_277 = (441, 440)
7番目のレストラン: p_473 = (439, 463)
8番目のレストラン: p_537 = (430, 457)
9番目のレストラン: p_514 = (416, 477)
10番目のレストラン: p_457 = (426, 488)
11番目のレストラン: p_969 = (399, 493)
12番目のレストラン: p_95 = (372, 493)
13番目のレストラン: p_268 = (360, 493)
14番目のレストラン: p_743 = (345, 486)
15番目のレストラン: p_359 = (335, 501)
16番目のレストラン: p_489 = (335, 512)
17番目のレストラン: p_106 = (305, 509)
18番目のレストラン: p_803 = (298, 495)
19番目のレストラン: p_835 = (287, 516)
20番目のレストラン: p_994 = (288, 529)
21番目のレストラン: p_170 = (276, 528)
22番目のレストラン: p_496 = (278, 539)
23番目のレストラン: p_407 = (306, 536)
24番目のレストラン: p_165 = (310, 529)
25番目のレストラン: p_311 = (321, 539)
26番目のレストラン: p_812 = (322, 564)
27番目のレストラン: p_57 = (335, 560)
28番目のレストラン: p_707 = (333, 555)
29番目のレストラン: p_914 = (337, 566)
30番目のレストラン: p_609 = (323, 590)
31番目のレストラン: p_849 = (322, 589)
32番目のレストラン: p_714 = (324, 605)
33番目のレストラン: p_656 = (355, 600)
34番目のレストラン: p_692 = (367, 602)
35番目のレストラン: p_417 = (378, 596)
36番目のレストラン: p_332 = (385, 584)
37番目のレストラン: p_418 = (385, 566)
38番目のレストラン: p_687 = (395, 571)
39番目のレストラン: p_262 = (407, 578)
40番目のレストラン: p_354 = (409, 579)
41番目のレストラン: p_655 = (371, 579)
42番目のレストラン: p_742 = (367, 530)
43番目のレストラン: p_923 = (389, 525)
44番目のレストラン: p_324 = (424, 527)
45番目のレストラン: p_233 = (422, 535)
46番目のレストラン: p_289 = (436, 529)
47番目のレストラン: p_448 = (434, 526)
48番目のレストラン: p_950 = (451, 514)
49番目のレストラン: p_754 = (461, 521)
0番目の配達先: q_268 = (480, 592)
1番目の配達先: q_754 = (604, 522)
2番目の配達先: q_687 = (584, 472)
3番目の配達先: q_773 = (565, 430)
4番目の配達先: q_262 = (556, 427)
5番目の配達先: q_849 = (552, 316)
6番目の配達先: q_969 = (487, 284)
7番目の配達先: q_692 = (450, 286)
8番目の配達先: q_609 = (422, 198)
9番目の配達先: q_354 = (372, 61)
10番目の配達先: q_994 = (359, 27)
11番目の配達先: q_714 = (286, 69)
12番目の配達先: q_332 = (275, 121)
13番目の配達先: q_106 = (270, 135)
14番目の配達先: q_277 = (289, 137)
15番目の配達先: q_914 = (206, 136)
16番目の配達先: q_923 = (157, 131)
17番目の配達先: q_707 = (36, 62)
18番目の配達先: q_95 = (2, 39)
19番目の配達先: q_170 = (0, 251)
20番目の配達先: q_407 = (63, 355)
21番目の配達先: q_656 = (106, 336)
22番目の配達先: q_57 = (109, 429)
23番目の配達先: q_289 = (232, 482)
24番目の配達先: q_418 = (242, 528)
25番目の配達先: q_514 = (235, 670)
26番目の配達先: q_473 = (248, 682)
27番目の配達先: q_233 = (239, 759)
28番目の配達先: q_365 = (136, 742)
29番目の配達先: q_950 = (125, 668)
30番目の配達先: q_803 = (68, 652)
31番目の配達先: q_457 = (7, 688)
32番目の配達先: q_708 = (33, 799)
33番目の配達先: q_165 = (292, 315)
34番目の配達先: q_417 = (263, 254)
35番目の配達先: q_837 = (494, 369)
36番目の配達先: q_216 = (683, 406)
37番目の配達先: q_835 = (757, 407)
38番目の配達先: q_448 = (762, 353)
39番目の配達先: q_742 = (700, 328)
40番目の配達先: q_537 = (677, 254)
41番目の配達先: q_743 = (648, 120)
42番目の配達先: q_311 = (619, 106)
43番目の配達先: q_489 = (578, 50)
44番目の配達先: q_655 = (570, 34)
45番目の配達先: q_812 = (778, 148)
46番目の配達先: q_359 = (778, 151)
47番目の配達先: q_930 = (708, 532)
48番目の配達先: q_324 = (791, 626)
49番目の配達先: q_496 = (797, 651)
total distance: 7918
追加された変数一覧（山登り法）
| 変数名 | 説明 |
|---|
| candidates | オフィスから距離400以下の注文の候補リスト（注文のインデックス） |
| destinations | 【※入力のdestinationsとは別】選択した注文に対応する配達先のインデックスリスト（solve_greedy内でordersをコピー） |
| current_dist | solve_hill_climbing内で現在の経路の総移動距離 |
| rand | 乱数生成器（std::mt19937、固定シード42） |
| start_time | 山登り法の開始時刻 |
| time_limit | 山登り法の制限時間（1900ミリ秒） |
| iteration | 山登り法の試行回数のカウンタ |
| i | ランダムに選ばれる、訪問先（配達先）のルート内インデックス（オフィス・レストラン部分を除く） |
| j | ランダムに選ばれる、訪問先（配達先）のルート内インデックス |
| point_to_move | i番目の訪問先を移動する際の対象ポイント（Point型） |
| new_dist | 操作後に再計算された経路の総移動距離 |
山登り法による経路改善の疑似コード
関数 solve_hill_climbing(input: Input, output_greedy: Output) -> Output: orders ← output_greedy.orders route ← output_greedy.route current_dist ← get_distance(route)
php-template
コピーする
rand ← 乱数生成器(シード=42)
start_time ← 現在時刻
time_limit ← 1900
iteration ← 0
while (現在時刻 - start_time < time_limit) do:
i ← rand() % pickup_count + pickup_count + 1
j ← rand() % pickup_count + pickup_count + 1
point_to_move ← route[i]
route.remove(i)
route.insert(j, point_to_move)
new_dist ← get_distance(route)
if new_dist ≤ current_dist then:
if new_dist < current_dist then:
標準エラー出力に "iteration: " + iteration + ", total distance: " + new_dist
current_dist ← new_dist
else:
route.remove(j)
route.insert(i, point_to_move)
iteration ← iteration + 1
標準エラー出力に "--- Result ---"
標準エラー出力に "iteration: " + iteration + ", total distance: " + current_dist
return Output(orders, route)
追加された変数一覧（焼きなまし法）
| 変数名 | 説明 |
|---|
| orders | solve_simulated_annealing内で初期解としてコピーされた、選択した注文のリスト |
| route | solve_simulated_annealing内で初期解としてコピーされた配達ルート |
| current_dist | 初期解の経路の総移動距離（get_distance(route)で計算） |
| rand | 乱数生成器（std::mt19937、固定シード42） |
| zero_one_dist | 0.0以上1.0未満の乱数を生成する分布（std::uniform_real_distribution） |
| start_time | 焼きなまし法の開始時刻（std::chrono::system_clock::now()で取得） |
| time_limit | 焼きなまし法の制限時間（1900ミリ秒） |
| start_temperature | 焼きなまし法の開始温度（2e2） |
| end_temperature | 焼きなまし法の終了温度（1e0） |
| current_temperature | 現在の温度（温度更新に利用） |
| iteration | 焼きなまし法の試行回数カウンタ |
| i | ランダムに選ばれる、訪問先（配達先）のルート内インデックス（オフィス・レストラン部分を除く） |
| j | ランダムに選ばれる、訪問先（配達先）のルート内インデックス |
| point_to_move | i番目の訪問先を移動する際の対象ポイント（Point型） |
| new_dist | 操作後に再計算された経路の総移動距離 |
| progress | 経過時間の割合（温度更新に利用、0.0～1.0） |
焼きなまし法による経路改善の疑似コード
関数 solve_simulated_annealing(input: Input, output_greedy: Output) -> Output: orders ← output_greedy.orders のコピー route ← output_greedy.route のコピー current_dist ← get_distance(route)
php-template
コピーする
rand ← 乱数生成器(シード=42)
zero_one_dist ← 乱数分布(0.0, 1.0)
start_time ← 現在時刻
time_limit ← 1900
start_temperature ← 200.0
end_temperature ← 1.0
current_temperature ← start_temperature
iteration ← 0
while (現在時刻 - start_time time_limit) do:
i ← rand() % pickup_count + pickup_count + 1
j ← rand() % pickup_count + pickup_count + 1
point_to_move ← route[i]
route.remove(i)
route.insert(j, point_to_move)
new_dist ← get_distance(route)
if new_dist ≤ current_dist or (zero_one_dist(rand) < exp((current_dist - new_dist) / current_temperature)) then:
current_dist ← new_dist
else:
route.remove(j)
route.insert(i, point_to_move)
iteration ← iteration + 1
if (iteration mod 100000 = 0) then:
標準エラー出力に "iteration: " + iteration + ", total distance: " + current_dist
progress ← (現在時刻 - start_time) / time_limit
current_temperature ← (start_temperature^(1.0 - progress)) * (end_temperature^(progress))
標準エラー出力に "--- Result ---"
標準エラー出力に "iteration: " + iteration + ", total distance: " + current_dist
return Output(orders, route)