TUNA Camp 2026 京都Stage ヒューリスティックアルゴリズム入門

2026/3/27 (金) にTUNA Camp 2026 京都Stageで発表させていただいたスライドです。

イベントサイト：https://tunacamp.connpass.com/event/383741/
関連ファイル：https://drive.google.com/drive/folders/1uYYvnBIjsq_bo9SNlIqw6ob8CcqBt6OY?usp=sharing
コンテストサイト：https://judge.tuna.camp/contests/TUNA2026-kyoto-day2-lecture/overview

Transcript

1. ヒューリスティックアルゴリズム入門 ～コンテストもあるよ！～ TUNA Camp 2026 京都Stage 特別講演 株式会社ALGO ARTIS 松尾 充
2. 松尾 充 株式会社ALGO ARTIS まつお あたる （6位） 2010 アルゴリズム ヒューリスティック 3205 @terry_u16 terry_u16 1992年 福岡県生まれ 九州大学に入学して機械工学を勉強 九州大学大学院の修士課程に進学 2010年 2014年 株式会社IHIに入社し戦闘機用ジェットエンジンを開発 うっかり競技プログラミングにハマってしまう 株式会社ALGO ARTISに入社しアルゴリズムを仕事に 2016年 2020年 2022年
3. CM
4. 提供 ご覧のスポンサーの提供でお送りします 明日3/28 (土) の懇親会でブース出展しますので是非お越しください！
5. CM終わり
6. 講演にあたって
7. 講演にあたって どのようなコンテンツを提供すべきか？
8. 講演にあたって ヒューリスティック入門向け講座をやる → 中級者以上が暇になる そんなの知ってるよ……
9. 講演にあたって 普通にヒューリスティックコンテストをやる → 初心者が何もできない 何も分からない……
10. 講演にあたって 会社の話とか社会の話とかをする → 2時間半もたせられるわけがない つまらん…… つまらん……
11. 講演にあたって 初心者向け講座をやりながら 中級者以上には難しい問題を勝手に解いてもらえば 両方ともハッピーなのでは？
12. 講演にあたって 欠点：準備の作業量がシンプルに 倍 になる マジでやめた方が良いです……
13. 講演にあたって 初心者・中上級者問わず どちらも楽しめるようにしたつもりなので よろしくお願いします！
14. 本日の流れ 問題概要解説 各アルゴリズム解説 コンテスト （2h） A問題チュートリアル (時間が余れば) B問題にチャレンジ 解説
15. 問題概要解説
16. ストーリー 発明家のTERRYくんは、電子デバイスに対してチューニングを行って性能を向 上させることのできる装置「TUNER amp 2026」を開発した。 この装置は汎用性が考慮されており、アダプタを付け替えることでどんな電子 デバイスのチューニングも行うことができる。 アダプタの付け替えには、付け替え前後のアダプタのペアに対応した時間が かかり、使うアダプタの順番を工夫することで作業時間を短縮することができ る。 噂を聞きつけた人々から多数のオーダーが届いているため、できるだけ早く全 てのオーダーが完了するような計画を立ててほしい。
17. 問題文要約 • オーダーが 𝑁 個、アダプタが 𝑀 + 1 個ある。 • 最初と最後は装置に特殊なアダプタ 𝑀 を付けた状態でなければならない。 • オーダー 𝑖 はアダプタ集合 𝑆𝑖 のいずれかの要素で遂行できる。 • アダプタ 𝑖 から 𝑗 への取り替えには 𝑡𝑖,𝑗 秒かかる。 • 短時間で全てのオーダーをちょうど1回ずつ遂行する手順を求めよ。 装置 アダプタ オーダー
18. A, B問題の違い A問題 (Easy) とB問題 （Ｈａｒｄ) は制約が異なる A問題はオーダーとアダプタが1対1対応、B問題は1対5対応 A問題 (Easy) オーダーに対しアダプタが一意に定まる B問題 (Hard) アダプタを5種類から自由に選べる
19. その他ルール • コンテスト時間は17:45～19:45の2時間を予定 • テストケース数は1問あたり50ケース • 配点はA問題≪B問題 • CE以外の理由で同一人物が同じ問題に複数回提出する場合は5分空ける （ペナルティはないですができるだけご協力お願いします） • ビジュアライザ・ローカルツール提供あり • 解法の大量自動生成を除き生成AIの使用OK (AHCと同じルール) • 個人参加・チーム参加どちらでもOK • ゆるふわな感じでやります
20. メタヒューリスティクスとは
21. メタヒューリスティクス（ヒューリスティックアルゴリズム）とは メタヒューリスティクスとは、組合せ最適化問題向けのアルゴリズムのうち 最適解は保証されないが幅広い問題に適用できるものをいう 特に厳密解を得るのにとても長い時間のかかる難しい問題に対して有効
22. 巡回セールスマン問題 難しい問題の例として、巡回セールスマン問題を取り上げる これは最小コストで全ての都市を回る経路を探す最適化問題 都市 1 都市 2 都市 3 都市 4 順列全探索 計算量 𝑂 𝑁! → 𝑁 = 11 前後が限界 DP 計算量 𝑂 𝑁22𝑁 → 𝑁 = 19 前後が限界 現実 𝑁 = 100 とかで普通に解きたくなる
23. 巡回セールスマン問題を近似的に解く 一般的な厳密解法では一生かかっても終わらない計算が 実用的な時間で解けるようになって嬉しい！ 巡回セールスマン問題をいろんな近似解法で解く（その6: さまざまな近傍）, take314 https://qiita.com/take314/items/69b93481403feb857d6e 焼きなまし法を使うと 1379都市の巡回セールスマン問題でも 4秒ほどでかなり良い解が得られる※ ※この実行例では、最適解に対しておよそ+1．6%の解が得られた
24. メタヒューリスティクスの長所と短所 メタヒューリスティクスは長所と短所をもつが 使いどころを間違えなければとても強力なアルゴリズムとなる 特定の問題に限定されず 幅広い問題に適用できる 問題専用に作られた アルゴリズムより 性能は落ちる 解くのが難しい問題を 実用的な速度で解ける 解の精度が 保証されておらず どのくらいよい解か不明 長所 短所 専用アルゴリズムが 存在しない問題に有効 精度の保証が不要で 難しい問題を解くときに 有効 使いどころ
25. 各アルゴリズム解説
26. ビームサーチ 解の候補を1つではなく複数個保持して 解を作り上げていく貪欲法 山登り法 ある解を少し変更して改善したら採用し よりよい解に近付けていく方法 メタヒューリスティクスの一覧 メタヒューリスティクスにはいろいろな種類があるが 今回はよく使われるものに絞って紹介 貪欲法 その場その場で最もよい選択肢を選び 解を作り上げていく方法 焼きなまし法 改善しない場合も一定確率で採用し 局所解にハマりにくくした山登り法 発展 発展
27. 貪欲法・ビームサーチ まずは貪欲法とビームサーチ ビームサーチは貪欲法の発展型なので、まずは貪欲法から説明 ビームサーチ 解の候補を1つではなく複数個保持して 解を作り上げていく貪欲法 山登り法 ある解を少し変更して改善したら採用し よりよい解に近付けていく方法 貪欲法 その場その場で最もよい選択肢を選び 解を作り上げていく方法 焼きなまし法 改善しない場合も一定確率で採用し 局所解にハマりにくくした山登り法 発展 発展
28. 貪欲法 貪欲法とは、（後先考えずに）その場その場で最も良さそうな選択肢を選び 解を一から作り上げていく方法 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 複数の選択肢から…… 一番良さそうなものを選択！
29. 貪欲法の適用例 巡回セールスマン問題に貪欲法を適用してみる 「未訪問の都市の中で最も近い都市に移動する」という貪欲を行う 1 2 3 5 4 6 都市1からスタート 1 2 3 5 4 6 最寄りの都市6へ 1 2 3 5 4 6 最寄りの都市2へ 1 2 3 5 4 6 最寄りの都市3へ 1 2 3 5 4 6 最寄りの都市5へ 1 2 3 5 4 6 最寄りの都市4へ 1 2 3 5 4 6 都市1でゴール!
30. 貪欲法の実装例 N = 4 cost = [[0, 5, 3, 8], [5, 0, 4, 6], [3, 4, 0, 9], [8, 6, 9, 0]] total_cost = 0 current_city = 0 visited = [True, False, False, False] order = [0] # 都市0以外のN-1都市を訪問するまでループ for _ in range(N - 1): # 最も近い次の都市を全探索 best_cost = 1000000000 best_city = -1 for next_city in range(N): if visited[next_city]: continue # コストが最小の場合は更新 next_cost = total_cost + cost[current_city][next_city] if next_cost < best_cost: best_cost = next_cost best_city = next_city # 次の都市に移動し、状態を更新する visited[best_city] = True order.append(best_city) total_cost = best_cost current_city = best_city # 最後に都市0に戻ってくる total_cost += cost[current_city][0] order.append(0) print(f"total_cost: {total_cost}") print(f"order: {order}") 入力の作成 合計コスト・現在位置・訪問済みフラグ・訪問順を初期化 都市0以外を全て訪問するまでループ まだ訪問していない都市を全探索し、 最もコストが小さい都市を次の都市として選ぶ 次の都市に移動する 合計コスト・現在位置・訪問済みフラグ・訪問順を更新 最後に都市0に戻る 合計コスト・訪問順を出力して終了
31. 貪欲法の長所と短所 実装が簡単で動作が高速なため、初心者から上級者までオススメ 実装が簡単 まずお試しで組んでみることがやりやすく、 より高度な手法を使う前の足がかりになる 長所 短所 動作が高速 今回のケースだと𝑂 𝑁2 となり、とても高速 他の手法と組み合わせて使うこともやりやすい 「損して得取れ」が難しい 基本的に後先考えずに動くので、 後ろの方にしわ寄せが行きやすい 評価関数のチューニングが難しい 選び方の基準となる評価関数によって 性能が変わり、そのチューニングが難しい 1 2 3 5 4 6 ※各状態の「良さ」を決める関数のことを「評価関数」という
32. ビームサーチ ビームサーチとは貪欲法の発展形 解の候補を複数個保持して解を作り上げていく方法 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 複数の選択肢から…… 良さそうなものを複数選択！
33. ビームサーチの適用例 こちらも巡回セールスマン問題に適用 貪欲法をベースに「総コストの小さい3つを保持する」という方針にしてみる 都市1からスタート 1 2 3 4 0分 候補3つとも保持 1 2 3 4 4分 1 2 3 4 6分 1 2 3 4 10分 1 2 3 4 9分 1 2 3 4 10分 1 2 3 4 10分 1 2 3 4 11分 ⋮ 1 2 3 4 13分 1 2 3 4 16分 1 2 3 4 14分 1 2 3 4 20分 1 2 3 4 20分 1 2 3 4 23分 上位3つまで保持 候補3つとも保持 解の完成！
34. 貪欲法とビームサーチの比較 貪欲法では「その時点で一番良いもの」だけを考えていたが ビームサーチでは「その時点で良い順にK番目まで」を考える点が異なる 1 2 3 4 0分 1 2 3 4 4分 1 2 3 4 6分 1 2 3 4 10分 1 2 3 4 9分 1 2 3 4 10分 1 2 3 4 10分 1 2 3 4 13分 1 2 3 4 16分 1 2 3 4 14分 1 2 3 4 20分 1 2 3 4 20分 1 2 3 4 23分 1 2 3 4 0分 1 2 3 4 4分 1 2 3 4 9分 1 2 3 4 13分 1 2 3 4 23分 1個 K個 貪 欲 法 ビ ー ム サ ー チ
35. ビームサーチの実装例 長くなるので省略！ごめんなさい！
36. 山登り法・焼きなまし法 次に山登り法と焼きなまし法 焼きなまし法は山登り法の発展型なので、まずは山登り法から説明 ビームサーチ 解の候補を1つではなく複数個保持して 解を作り上げていく貪欲法 山登り法 ある解を少し変更して改善したら採用し よりよい解に近付けていく方法 貪欲法 その場その場で最もよい選択肢を選び 解を作り上げていく方法 焼きなまし法 改善しない場合も一定確率で採用し 局所解にハマりにくくした山登り法 発展 発展
37. 山登り法 山登り法（局所探索法） とは、ある解を少し変更してみて改善したら採用し よりよい解に少しずつ近付けていく方法 1 2 3 4 1 2 3 4 微妙な解を…… 少し変更して改善！
38. 山登り法という名前について 解を少しずつ改善していく動きが山を登っていくイメージに似ているため 山登り法と呼ばれることが多い 初期解 下がることは しない 上がる方向なら 進んでいく 良い解が 得られた！ スコア
39. 山登り法の適用例 巡回セールスマン問題に山登り法を適用してみる 巡回セールスマン問題では「ランダムな区間の訪問順を反転させる」※という2-optと呼ばれる変更が 有効なので、今回はその手法を試す 1 3 2 4 52分 5 6 1 3 2 4 58分 5 6 1 3 2 4 43分 5 6 ※「2辺をランダムに選び、辺をつなぎ替える」と説明されることが多いが、やっていることは同じ [3, 4]を 反転 [3, 5]を 反転 [3, 5, 6]を 反転 1 3 2 4 65分 5 6 1 3 2 4 74分 5 6 1 3 2 4 68分 5 6 [5, 3]を 反転 [5, 1, 2]を 反転 1 3 2 4 61分 5 6 [2, 4]を 反転
40. 山登り法の実装例 # 制限時間の定義 TIME_LIMIT = 1.9 # 初期解 (state) を作る # ランダムな解にしても、貪欲法で解を作ってもよい state = generate_initial_state() start_time = get_time() # 時間いっぱいループ while get_time() - start_time < TIME_LIMIT: # 解を少し変化させる # 1箇所の値を変化させたり、2つの値を交換したり new_state = change_state(state) # スコアを計算する old_score = calculate_score(state) new_score = calculate_score(state) # スコアが悪化しなければ採用 if new_score >= old_score: state = new_state # 解を出力する print(state) 制限時間の定義 初期解を作成 ランダムな解を作っても、貪欲法などで解を作ってもよい 解の出力 制限時間になるまでループ 解を少し変化させる 古い解のスコアと新しい解のスコアを計算する スコアが悪化していなければ採用
41. 山登り法の長所と短所 貪欲法以上に強力な手法なので、適用できる問題にはかなり強い 全体を見て判断できる 途中段階ではなく最終状態で評価できるので 「損して得取れ」という動きがとてもやりやすい 長所 短所 性能が高い 比較的実装がシンプルでありながら、 貪欲法よりも良い解を出しやすい 適用できる問題の幅が少し狭い テトリスのように「少し変えただけで最終状態が 大きく変わってしまう」ような問題は苦手 局所解にハマりやすい それ以上改善ができない局所解になりやすい （詳しくは次のページ）
42. 局所解 山登り法では、「どちらに行ってもスコアが下がってしまう」という 嘘の最適解（局所解）にハマってしまうことがある 初期解 頂上まで 来たつもりが…… より良い解に たどり着けない！ スコア
43. 焼きなまし法 「局所解にハマりやすい」という欠点を解消したのが焼きなまし法 ある確率でスコアが悪化する変更を許すことで局所解からの脱出を図る 初期解 悪化する変更も たまに許す スコア より良い解に 到達できた！
44. 温度パラメータ 焼きなまし法で重要な役割を果たすのが温度パラメータ 温度によってスコアが悪化する変更を採用する確率が変化する 温度が高いとき スコアが悪化する変更を採用しやすく 幅広い解を探し回る （ランダムに近い動き） 温度が低いとき スコアが悪化する変更を採用しにくく 確実に良い解に近付いていく （山登り法に近い動き）
45. 温度スケジューリング 焼きなまし法では、序盤は温度を高くしだんだんと温度を下げていく 序盤は幅広い解を探索し、終盤は確実に良い解に近付く 高温 低温 大きな解の悪化も許し 幅広い解を探し回る 少しずつ温度を下げて 探索する範囲を狭める 山登りのような動きになり 確実に良い解に近付く
46. 焼きなまし法の実装例 詳細は割愛するが、山登り法から解の採用判断だけ変更すればOK # 制限時間の定義 TIME_LIMIT = 1.9 # 初期解 (state) を作る # ランダムな解にしても、貪欲法で解を作ってもよい state = generate_initial_state() start_time = get_time() # 時間いっぱいループ while get_time() - start_time < TIME_LIMIT: # 解を少し変化させる # 1箇所の値を変化させたり、2つの値を交換したり new_state = change_state(state) # スコアを計算する old_score = calculate_score(state) new_score = calculate_score(state) # スコアが悪化しなければ採用 if new_score >= old_score: state = new_state # 解を出力する print(state) ↑違いはここだけ！ # 各種パラメータ定義 TIME_LIMIT = 1.9 START_TEMP = 10000 END_TEMP = 100 # 初期解 (state) を作る # ランダムな解にしても、貪欲法で解を作ってもよい state = generate_initial_state() start_time = get_time() # 時間いっぱいループ while get_time() - start_time < TIME_LIMIT: # 解を少し変化させる # 1箇所の値を変化させたり、2つの値を交換したり new_state = change_state(state) # スコアを計算する old_score = calculate_score(state) new_score = calculate_score(state) # 温度 (temperature) と遷移確率 (probability) を計算 time = (get_time() - start_time) / TIME_LIMIT temperature = pow(START_TEMP, 1 - time) * pow(END_TEMP, time) probatility = exp((new_score - old_score) / temperature) # スコアが悪化しなければ無条件で採用 # 悪くなっていても確率的に採用 if new_score >= old_score or random() < probatility: state = new_state # 解を出力する print(state) 山登り法 焼きなまし法 温度 温度パラメータ𝑇は、 開始温度を𝑇0 、終了温度を𝑇1 、 経過時間を𝑡 0 ≤ 𝑡 ≤ 1 として、 𝑇 𝑡 = 𝑇0 1−𝑡 × 𝑇1 𝑡 としている 採用確率 採用確率𝑝は、スコア変化量をΔ𝑆、 温度を𝑇として、 𝑝 Δ𝑆, 𝑇 = ቊ 1 Δ𝑆 ≥ 0 𝑒 Τ Δ𝑆 𝑇 Δ𝑆 < 0 とする（最大化問題の場合）
47. 焼きなまし法の長所と短所 焼きなましの欠点の一つを解消した手法なので、適用できればかなり強い 全体を見て判断できる 途中段階ではなく最終状態で評価できるので 「損して得取れ」という動きがとてもやりやすい 長所 短所 性能が高い 比較的実装がシンプルでありながら、 貪欲法よりも良い解を出しやすい 適用できる問題の幅が少し狭い テトリスのように「少し変えただけで最終状態が 大きく変わってしまう」ような問題は苦手
48. 問題内容の整理
49. 問題文を読む 改めて問題文を読む https://judge.tuna.camp/contests/TUNA2026-kyoto-day2-lecture/problems/tunar-amp-2026-easy-6linux/statement
50. A問題要約 • オーダーが 𝑁 個、アダプタが 𝑀 + 1 個あり、 𝑁 = 𝑀 である。 • 最初と最後は装置に特殊なアダプタ 𝑀 を付けた状態でなければならない。 • オーダー 𝑖 はアダプタ 𝑖 を用いて遂行できる。 • アダプタ 𝑖 から 𝑗 への取り替えには 𝑡𝑖,𝑗 秒かかる。 • 短時間で全てのオーダーをちょうど1回ずつ遂行する手順を求めよ。 装置 アダプタ オーダー
51. 問題内容の整理 A問題ではオーダーとアダプタが1対1で対応するため 全てのアダプタが1回ずつ出現する順列を求めればよい 𝑸 は無視してよく、良い感じの順列 𝑷 を求めればよい
52. 巡回セールスマン問題への帰着 全ての状態を1回ずつ訪れてから元の状態に戻ってきたいと捉えると 実は巡回セールスマン問題そのものとみなして解くことができる - 15秒 10秒 30秒 15秒 - 25秒 15秒 10秒 25秒 - 5秒 30秒 15秒 5秒 - 10秒 15秒 5秒 15秒 30秒 25秒 取り替え後 取 り 替 え 前
53. 巡回セールスマン問題への帰着 結局以下のの巡回セールスマン問題と等価とみなせる よって今まで説明してきた貪欲法・山登り法・焼きなまし法が使える • 都市が 201 個ある。 • 都市 200 を出発して、 0, ⋯ , 199 をちょうど一回ずつ回り、都市 200 に戻る。 • 都市 𝑖 から 𝑗 への移動には 𝑡𝑖,𝑗 秒かかる。 • できるだけ短時間で全ての都市を回る順列を求めよ。
54. 実装
55. 進め方 ABCと違って一気に実装する必要はないので、少しずつ進めましょう 早く終わったという人は先に進めてしまって構いません 入 力 受 け 取 り と 自 明 解 作 成 貪 欲 法 作 成 ス コ ア 計 算 関 数 作 成 山 登 り 法 作 成 焼 き な ま し 法 作 成 焼 き な ま し 法 高 速 化
56. サンプルコード Google Driveから各ステップのサンプルコードがダウンロードできます 実装の参考にしてみてください https://drive.google.com/drive/folders/1uYYvnBIjsq_bo9SNlIqw6ob8CcqBt6OY?usp=sharing この中にC++/Pythonの サンプルコードがあります
57. ビジュアライザを用いたデバッグ 実行結果をビジュアライザに貼り付けるとバグの確認がしやすいです バグがある場合 エラーメッセージが出る 入力はこれ ここに出力を貼る 入力ケース変更 アニメーション開始 https://tuna-camp-2026-kyoto-8ee6a7.vercel.app/
58. 助け合って解いていきましょう 競プロ初心者からアルゴ解きまくっている方まで、色々な方がいらっしゃいます 周りで困ってそうな方がいたら是非助けてあげてください！
59. 1. 入力受け取りと自明解作成 まずは問題文を読み、入力を受け取り、ACを取りましょう 出力する解は何でも良いので、とりあえず 200, 0, 1, ⋯ , 200 を出力しましょう 200 0 0 1 1 ... 199 199 200 入力形式 出力形式 出力例 𝑀 + 1 × 𝑀 + 1 行列 𝑆 は使わない 読み飛ばしてもOK
60. 出力例 コードが書けたらビジュアライザの入力を使って実行してみましょう 上手く行けばこんな感じの動きになるはずです Final Scoreが出れば AC判定
61. 2. 貪欲法作成 先程の説明と同じような貪欲法を考えます アダプタ 𝑥 から、未使用かつ 𝑡𝑥,𝑦 が最小となる 𝑦 を選んで変更します 1 2 3 5 4 6 都市1からスタート 1 2 3 5 4 6 最寄りの都市6へ 1 2 3 5 4 6 最寄りの都市2へ 1 2 3 5 4 6 最寄りの都市3へ 1 2 3 5 4 6 最寄りの都市5へ 1 2 3 5 4 6 最寄りの都市4へ 1 2 3 5 4 6 都市1でゴール!
62. やりたいことの整理 ABCの問題文っぽく言うとこんな感じです • 整数 𝑀 と、 𝑀 + 1 × 𝑀 + 1 行列 𝑡 が与えられる。 • はじめ、数列 𝑃 を 𝑃 = 𝑀 、 集合 𝑋 を 𝑋 = 0, 1, ⋯ , 𝑀 − 1 で初期化する。 • 𝑖 = 0, ⋯ , 𝑀 − 1 について、以下を繰り返す。 • 𝑡𝑃𝑖,𝑥 が最小であるような 𝑥 を選び、 𝑃 の末尾に追加する。 • その後、 𝑋 から 𝑥 を取り除く。 • 最後に、 𝑃 の末尾に 𝑀 を追加する。 • 全ての操作が完了したときの 𝑃 を求めよ。
63. 出力例 コードが書けたらビジュアライザの入力を使って実行してみましょう かなり大きくスコアが改善するはずです 6135点 → 17462点
64. 3. スコア関数の作成 山登り法を行うためには自分でスコア計算をする必要があります スコア計算関数を作りましょう 初期解 下がることは しない 上がる方向なら 進んでいく 良い解が 得られた！ スコア スコアが計算できないと どちらが上か分からない
65. やりたいことの整理 ABCの問題文っぽく言うとこんな感じです • 整数 𝑀, 𝐶 、 𝑀 + 1 × 𝑀 + 1 行列 𝑡 と、長さ 𝑀 の数列 𝑃 が与えられる。 • スコア関数 𝑓 を以下で定義する。 • 𝑓 𝑀, 𝑡, 𝐶, 𝑃 = max 𝐶 − σ𝑖=0 𝑀 𝑡𝑃𝑖,𝑃𝑖+1 , 1 • その値を求めよ。
66. 標準エラー出力への書き出し ジャッジに読まれたくないが表示させたい情報は 標準エラー出力に書き出すとデバッグがやりやすくなります #include <iostream> #include <vector> using namespace std; int main() { vector<int> P = greedy(M, t); int score = calc_score(M, t, C, P); cerr << "score = " << score << endl; } import sys P = greedy(M, t); score = calc_score(M, t, C, P); print(f"score = {score}", file=sys.stderr) 標準エラー出力（C++） 標準エラー出力（Python）
67. 出力例 コードが書けたらビジュアライザの入力を使って実行してみましょう ビジュアライザと標準エラー出力のスコアが一致していればOKです スコアが合っていればOK
68. 4. 山登り法の作成 スコア計算関数ができたので、山登り法を書く準備が整いました 2-opt（ランダムな区間 𝑳, 𝑹 を反転する） を試してみましょう 𝐿 𝑅 反転
69. やりたいことの整理 ABCの問題文っぽく言うとこんな感じです • 整数 𝑀, 𝐶 、 𝑀 + 1 × 𝑀 + 1 行列 𝑡 と、長さ 𝑀 の数列 𝑃 が与えられる。 • スコア関数 𝑓 を 𝑓 𝑀, 𝑡, 𝐶, 𝑃 = max 𝐶 − σ𝑖=0 𝑀 𝑡𝑃𝑖,𝑃𝑖+1 , 1 と定義する。 • 以下のクエリに実行時間が許す限り処理せよ。 • ランダムな区間 𝐿, 𝑅 1 ≤ 𝐿 < 𝑅 ≤ 𝑀 + 1 が与えられる。 • 𝑃 の区間 𝐿, 𝑅 を反転させたものを 𝑃′ とする。 • 𝑓 𝑀, 𝑡, 𝐶, 𝑃′ > 𝑓 𝑀, 𝑡, 𝐶, 𝑃 であれば、 𝑃 を 𝑃′ で置き換える。
70. 実行時間の計測と乱数の生成 実行時間計測および乱数（ランダムな数）生成を行う必要があります 詳細はサンプルコードを参考にしてください #include <chrono> #include <random> using namespace std; using namespace chrono; int main() { // 乱数生成 mt19937<int> rng(998244353); uniform_int_distribution<int> dist(1, M + 1); int l = dist(rng); int r = dist(rng); // 時刻計測 auto start = high_resolution_clock::now(); auto now = high_resolution_clock::now(); auto elapsed_ns = duration_cast<nanoseconds>(now – start).count(); double elapsed = elapsed_ns / 1e9; } import random import time # 乱数生成 random.seed(998244353); l = random.randint(1, M + 1); r = random.randint(1, M + 1); # 時刻計測 start = time.perf_counter() now = time.perf_counter() elapsed_time = now - start C++ Python
71. 出力例 コードが書けたらビジュアライザの入力を使って実行してみましょう 終盤に弱かった貪欲法の弱点が改善されていると思います
72. 5. 焼きなまし法の作成 山登り法はそのまま焼きなまし法に拡張できます 採用・不採用判定を少し書き換えましょう # 制限時間の定義 TIME_LIMIT = 1.9 # 初期解 (state) を作る # ランダムな解にしても、貪欲法で解を作ってもよい state = generate_initial_state() start_time = get_time() # 時間いっぱいループ while get_time() - start_time < TIME_LIMIT: # 解を少し変化させる # 1箇所の値を変化させたり、2つの値を交換したり new_state = change_state(state) # スコアを計算する old_score = calculate_score(state) new_score = calculate_score(state) # スコアが悪化しなければ採用 if new_score >= old_score: state = new_state # 解を出力する print(state) ↑違いはここだけ！ 山登り法 # 各種パラメータ定義 TIME_LIMIT = 1.9 START_TEMP = 10000 END_TEMP = 100 # 初期解 (state) を作る # ランダムな解にしても、貪欲法で解を作ってもよい state = generate_initial_state() start_time = get_time() # 時間いっぱいループ while get_time() - start_time < TIME_LIMIT: # 解を少し変化させる # 1箇所の値を変化させたり、2つの値を交換したり new_state = change_state(state) # スコアを計算する old_score = calculate_score(state) new_score = calculate_score(state) # 温度 (temperature) と遷移確率 (probability) を計算 time = (get_time() - start_time) / TIME_LIMIT temperature = pow(START_TEMP, 1 - time) * pow(END_TEMP, time) probatility = exp((new_score - old_score) / temperature) # スコアが悪化しなければ無条件で採用 # 悪くなっていても確率的に採用 if new_score >= old_score or random() < probatility: state = new_state # 解を出力する print(state) 焼きなまし法 温度 温度パラメータ𝑇は、 開始温度を𝑇0 、終了温度を𝑇1 、 経過時間を𝑡 0 ≤ 𝑡 ≤ 1 として、 𝑇 𝑡 = 𝑇0 1−𝑡 × 𝑇1 𝑡 としている 採用確率 採用確率𝑝は、スコア変化量をΔ𝑆、 温度を𝑇として、 𝑝 Δ𝑆, 𝑇 = ቊ 1 Δ𝑆 ≥ 0 𝑒 Τ Δ𝑆 𝑇 Δ𝑆 < 0 とする（最大化問題の場合）
73. やりたいことの整理 ABCの問題文っぽく言うとこんな感じです • 整数 𝑀, 𝐶 、 𝑀 + 1 × 𝑀 + 1 行列 𝑡 と、長さ 𝑀 の数列 𝑃 が与えられる。 • スコア関数 𝑓 を 𝑓 𝑀, 𝑡, 𝐶, 𝑃 = max 𝐶 − σ𝑖=0 𝑀 𝑡𝑃𝑖,𝑃𝑖+1 , 1 と定義する。 • 以下のクエリに実行時間が許す限り処理せよ。 • ランダムな区間 𝐿, 𝑅 1 ≤ 𝐿 < 𝑅 ≤ 𝑀 + 1 が与えられる。 • 𝑃 の区間 𝐿, 𝑅 を反転させたものを 𝑃′ とする。 • 温度 𝑇 𝜏 を、経過時間を 0 ≤ 𝜏 ≤ 1 として 𝑇0 1−𝜏 × 𝑇1 𝜏 とする。 • スコア差分 Δ = 𝑓 𝑀, 𝑡, 𝐶, 𝑃′ − 𝑓 𝑀, 𝑡, 𝐶, 𝑃 とおき、以下の処理を行う。 • Δ ≥ 0 であれば、 𝑃 を 𝑃′ で置き換える。 • Δ < 0 であれば、 0 以上 1 未満の一様乱数 𝑟 を生成し、 𝑟 < 𝑒 Δ 𝑇 𝜏 であれば、 𝑃 を 𝑃′ で置き換える。 ※ 𝑇0 , 𝑇1 の値は試行錯誤して決めますが、今回はまずは 𝑇0 = 10, 𝑇1 = 0.1 くらいにしておきましょう。
74. ベスト解の保持 焼きなましはスコアが下がることもあるので、ベスト解を保持しておくとよい • (前略) • ベスト解 𝑃𝑏𝑒𝑠𝑡 を 𝑃 で初期化する。 • 以下のクエリに実行時間が許す限り処理せよ。 • (中略) • 温度 𝑇 𝜏 を、経過時間を 0 ≤ 𝜏 ≤ 1 として 𝑇0 1−𝜏 × 𝑇1 𝜏 とする。 • スコア差分 Δ = 𝑓 𝑀, 𝑡, 𝐶, 𝑃′ − 𝑓 𝑀, 𝑡, 𝐶, 𝑃 とおき、以下の処理を行う。 • Δ ≥ 0 であれば、 𝑃 を 𝑃′ で置き換える。 • Δ < 0 であれば、 0 以上 1 未満の一様乱数 𝑟 を生成し、 𝑟 < 𝑒 Δ 𝑇 𝜏 であれば、 𝑃 を 𝑃′ で置き換える。 • 𝑓 𝑀, 𝑡, 𝐶, 𝑃′ > 𝑓 𝑀, 𝑡, 𝐶, 𝑃𝑏𝑒𝑠𝑡 であれば、 𝑃𝑏𝑒𝑠𝑡 を 𝑃 で置き換える。
75. 実数乱数の生成 実数乱数の生成を行う必要があります 詳細はサンプルコードを参考にしてください #include <random> using namespace std; int main() { // [0, 1) の乱数生成 mt19937<int> rng(998244353); uniform_real_distribution<double> dist(0, 1); int r = dist(rng); } import random # [0, 1) の乱数生成 random.seed(998244353); r = random.raondom(); C++ Python
76. 出力例 局所解から抜け出せるようになり、スコアが伸びました （Pythonの場合は速度が足りなくて逆にスコアが落ちることもあるかも）
77. 6. 焼きなまし法の高速化 焼きなまし法は試行錯誤の回数が増えるほど性能が上がります スコア計算の計算量を 𝑶 𝑴 から 𝑶 𝟏 にできるのでやってみましょう ここかな……？ こっちの方が良い！ 回数が少ない 回数が多い
78. 6. 焼きなまし法の高速化 ある区間 𝐿, 𝑅 を反転させたとき コストが変化するのは2箇所だけなので高速に差分計算ができる 反転 ※ 𝑡𝑖,𝑗 = 𝑡𝑗,𝑖 であるので、区間内部のコストは変わらない スコア差分 Δ = + − −
79. 出力例 たくさん試行錯誤できるようになり、さらにスコアが伸びました ループ回数をカウントして出力すると高速化の程度が測定できるのでオススメ
80. さらに理解を深めるには 焼きなましの差分計算までで既に高度なレベルですが、 さらに理解を深めるために色々試してみましょう • 温度パラメータ 𝑇0 , 𝑇1 を少し変化させてみる • 乱数の初期値を変えて、スコアのばらつきを見てみる • 時刻計測と温度のアップデートを100回に1回とかにしてみる （時刻計測は結構重い処理のため、頻度を減らすことで高速化を図る） • 初期解を貪欲法ではなくランダムにしてみる • 焼きなましを何回もやって、一番良かったものを出力してみる （乱数の初期値を変えないと同じ結果になることがあるので注意） • 焼きなまし中に一定時間ごとにスコアを出力させてスコア推移を見てみる • 2-opt以外の操作を試してみる
81. B問題に挑戦！ 飽きたらB問題に挑戦してみましょう！ 難易度がグッと上がるので、まずは貪欲法から試してみるのがオススメ B問題 (Hard) アダプタを5種類から自由に選べる アダプタとオーダーの ペアを全探索し 最もコストが小さいものを選ぶ
82. B問題のビジュアライザ 貪欲法が書けたらビジュアライザを再生してみましょう 何か気付くことがあるかも？
83. B問題解法例
84. 貪欲法 まずは貪欲法をやってみる 最もコストの小さいアダプタ・オーダーのペアを選び続ける B問題 (Hard) アダプタを5種類から自由に選べる アダプタとオーダーの ペアを全探索し 最もコストが小さいものを選ぶ スコア 960... くらい
85. オーダー順を巡回セールスマン問題+DPで解く こなすオーダー順を決め打つと、最小コストはDPで求められる オーダー順の焼きなましを行って、DPすることでそのときのスコアを求める スコア 965... くらい 𝑑𝑝 𝑖 0 , 𝑑𝑝 𝑖 1 , ⋯ , 𝑑𝑝 𝑖 4 𝑑𝑝 𝑖 + 1 0 , 𝑑𝑝 𝑖 + 1 1 , ⋯ , 𝑑𝑝 𝑖 + 1 4 𝑑𝑝 𝑖 + 2 0 , 𝑑𝑝 𝑖 + 2 1 , ⋯ , 𝑑𝑝 𝑖 + 2 4 類題: AHC028 Lucky Words
86. 考察2点 𝑡𝑖,𝑖 = 0 なので同じアダプタを連続して使うのが良さそう（最適とは限らない） 三角不等式が成り立たないので、小さすぎる近傍だとスコアが悪化しやすい b a c 三角不等式: 𝑡𝑎,𝑏 + 𝑡𝑏,𝑐 ≥ 𝑡𝑎,𝑐 頂点bを挿入・削除したとき、スコアの値が大きく悪化しがち
87. アダプタ順を巡回セールスマン問題+破壊再構築で解く オーダー順ではなく、全部のオーダーを被覆するアダプタ順を焼きなます 近傍は2-optと、アダプタの破壊再構築 スコア 972... くらい 破壊再構築近傍 • ランダムなアダプタをいくつか削除する • これによりいくつか遂行不能なオーダーが発生する • 全てのオーダーを被覆するまで、対応オーダーの多いアダプタを 貪欲に追加する • 2-opt山登り等を改善しなく なるまで行い局所解を得る
88. もっと学びたい人向け情報
89. オススメの本 ゲームで学ぶ探索アルゴリズム実践入門 青木栄太 著／技術評論社 メタヒューリスティクスをはじめとする幅広い探索アルゴリズムがぎゅっと詰まった一冊！ 丁寧な実装例付きで、各手法の基礎から一歩進んだテクニックまで学べます。 初心者から上級者まで、メタヒューリスティクスをじっくり学びたい人にオススメです！ https://book.mynavi.jp/ec/products/detail/id=131288 https://gihyo.jp/book/2023/978-4-297-13360-3 競技プログラミングの鉄則 アルゴリズム力と思考力を高める77の技術 米田優峻 著／マイナビ出版 メタヒューリスティクス関連の章は1章だけですが、とても分かりやすくまとまっています！ AtCoder上での自動採点システムも提供されているので、定着度の確認もバッチリです。 アルゴリズムもメタヒューリスティクスも勉強してみたい初～中級者の方にオススメです！
90. オススメの問題 AHCのうち、長期コンテストは複雑な問題が出されることが多いので、 まずは短期コンテスト（４時間程度）で学んでみるのがオススメです Introduction to Heuristics Contest 問題がシンプルな上、いろいろな解法で解くことができる良問です。 wataさんの解説pdfがとても丁寧です。 私もこれでメタヒューリスティクスに入門しました。 AtCoder Heuristics Contest 020 手前味噌ですが、私がwriterを務めた問題です。 基本問題から一歩進んだ貪欲法や焼きなましの練習にどうぞ。 解説放送で、いろいろな解き方をステップを踏みつつ紹介しています。
91. オススメのイベント AtCoderさんがAHC入門者向けのイベントを開催してくださっています ご都合が合えば是非ご参加ください！ AtCoder Heuristic First-step 豪華解説陣のもと、オンサイトでヒューリスティックコンテストの基本を学ぶことができます。 参加者同士の交流の場も設けられているのでぜひご参加ください！
92. ご参加頂き ありがとうございました！