AHF001に参加してきたよ

:::note warn
**注意**
こちらは個人による記述であり、公式の情報ではありません。古い情報や誤った情報が含まれる恐れがあります。
:::

:::note info
こちらはイベント自体に興味がある方向けの記事です。
AHFで学んだコツなどはまた別途まとめるつもりなので、そちらも併せてご覧ください。(後でここに貼ります)
:::

# 目次
スマホ版だと自動で目次が出てこないようなので、こちらに置いておきます。
PC版の方は右下にある目次の方が使いやすいのでぜひ。

<details>

<summary>目次</summary>

- [AHF(AtCoder Heuristic First-step) とは](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#ahfatcoder-heuristic-first-step-%E3%81%A8%E3%81%AF)
　- [対象層と大まかな流れ](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E5%AF%BE%E8%B1%A1%E5%B1%A4%E3%81%A8%E5%A4%A7%E3%81%BE%E3%81%8B%E3%81%AA%E6%B5%81%E3%82%8C)
　- [開催場所](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E9%96%8B%E5%82%AC%E5%A0%B4%E6%89%80)
　- [初日のスケジュール](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E5%88%9D%E6%97%A5%E3%81%AE%E3%82%B9%E3%82%B1%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AB)
- [感想](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E6%84%9F%E6%83%B3)
- [Algorithmとの違い](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#algorithm-%E3%81%A8%E3%81%AE%E9%81%95%E3%81%84)
- [具体的な学習の流れ](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E5%85%B7%E4%BD%93%E7%9A%84%E3%81%AA%E5%AD%A6%E7%BF%92%E3%81%AE%E6%B5%81%E3%82%8C)
　- [個人での演習](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E5%80%8B%E4%BA%BA%E3%81%A7%E3%81%AE%E6%BC%94%E7%BF%92)
　- [グループワーク](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E3%82%B0%E3%83%AB%E3%83%BC%E3%83%97%E3%83%AF%E3%83%BC%E3%82%AF)
- [事前準備とおすすめの勉強法](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E4%BA%8B%E5%89%8D%E6%BA%96%E5%82%99%E3%81%A8%E3%81%8A%E3%81%99%E3%81%99%E3%82%81%E3%81%AE%E5%8B%89%E5%BC%B7%E6%B3%95)
　- [ローカル環境でのコーディングに慣れておく](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E7%92%B0%E5%A2%83%E3%81%A7%E3%81%AE%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%81%AB%E6%85%A3%E3%82%8C%E3%81%A6%E3%81%8A%E3%81%8F)
　- [グラフアルゴリズムについて勉強しておく](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E3%82%B0%E3%83%A9%E3%83%95%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E5%8B%89%E5%BC%B7%E3%81%97%E3%81%A6%E3%81%8A%E3%81%8F)
　- [各アルゴリズムについてさらっと予習しておく](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E5%90%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E3%81%95%E3%82%89%E3%81%A3%E3%81%A8%E4%BA%88%E7%BF%92%E3%81%97%E3%81%A6%E3%81%8A%E3%81%8F)
- [まとめ](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E3%81%BE%E3%81%A8%E3%82%81)
- [関連リンク集](https://qiita.com/ponzu_domo/private/75a2192d82895044c0e5#%E9%96%A2%E9%80%A3%E3%83%AA%E3%83%B3%E3%82%AF%E9%9B%86)

</details>

# AHF(AtCoder Heuristic First-step) とは

:::note info
[公式のページ](https://atcoder.jp/contests/ahf1) も併せてご覧下さい！
:::

AHF(AtCoder Heuristic First-step)とは、**Atcoder社が主催するヒューリスティックコンテストの初心者向けチュートリアルイベント**です。

### 対象層と大まかな流れ

- **AHCに興味はあるが、まだ慣れていない/よく分かっていない人向け**
- **アルゴリズムのRatingが茶色以上の人**、または**BFS、DFS、ダイクストラ法を実装できる人**、または**これらのアルゴリズムについて自学可能な人**が対象
　- 茶色未満でも参加は可能です
- **初日にオリエンテーションと講義があり、その後1週間ほどチームで実際の問題に取り組む**
- **参加者の使用言語に合わせて教材が作成されるので安心**
　- 今年はC++, C#, Python, Rust, Ruby, Java, Nimの7種類でした

自分は灰色のひよっこなのですが、置いていかれることなく楽しむことができました。
解説が非常に丁寧なので、**最低限グラフに関する知識があればどなたでも参加できる**んじゃないかなと思います。前提知識として身につけておくべきことに関しては後述します。

**また実際に問題を解く期間が1週間ほどあるので、イベント当日だけではなくイベント後の予定も開けておくと安心です。**

### 開催場所

Vol.1 の開催場所は毎度お馴染み**メルカリ本社オフィス(六本木ヒルズ森タワー)でした**。
私自身 [メルカリ競プロコン](https://www.youtube.com/watch?v=hUqkqx9ppI8&ab_channel=MercariGears) や [Build@Mercari](https://qiita.com/ponzu_domo/items/2add037a4ea2ca1d399d) で何度もお世話になっているものの、毎回ほんのり迷っています。**六本木は迷宮なので30分ほど前に到着しておくと安心です**。

**特に大江戸線ユーザーの方は、Google Mapの案内に従うとどう見てもオフィスビルじゃない商業施設に案内されます**。かなり不安になりますが、そこを通り抜けるとオフィスビルがありますのでご安心ください。

### 初日のスケジュール

　12:30 ~ 13:00　受付
　13:00 ~ 13:05　スタッフ紹介
　13:05 ~ 13:15　アイスブレイク　
　13:15 ~ 13:30　**問題理解と貪欲法**
　13:30 ~ 14:15　実習
　14:15 ~ 14:20　休憩
　14:20 ~ 14:40　**山登り法**
　14:40 ~ 15:10　実習
　15:10 ~ 15:20　**焼きなまし法**
　15:20 ~ 15:40　実習
　15:40 ~ 15:50　**解法選択について**
　15:50 ~ 16:30　懇親会 (任意参加)

# 感想

### 解説が実践的でよい
AHFでは具体的な解法だけでなく、**問題の読み方や解法の選び方までしっかり教えてもらえます。上手い人の頭の中を覗き見しているような感覚で楽しかったです！**
また見本のコードがとても綺麗で、**コードの書き方などの点でも非常に勉強になりました**。こちらについては書きたいことがたくさんあるので後ほど別の記事にまとめようと思います。

### グループワークが楽しかった
練習用のコンテストはチーム(4人ほど)での参加となります。
初日は最初に10分ほどアイスブレイクがあったのですが、ここでは**チームで取り組める簡単なゲームが用意されており、チームメイトとの絆を深めることができました**。
アディショナルな部分まで非常によく準備されたイベントであるのを感じます。運営の方々には頭が上がりません...。

### アルゴとの違いに驚いた
コードの書き方、考え方、デバッグの方法などが今まで自分の使ってきたものと大きく異なりショックを受けました。
詳しくは後述しますが、**AlgorithmからHeuristicに入る人は、絶対に自己流でやるより上手い人を参考にした方がよい** と思います。そういった意味でも、今回のイベントへの参加は意義のあるものであったと感じます。

# Algorithm との違い

Algorithmの問題と違い、Heuristicの目指すところは **「クリティカルな解答」ではなく「最適解」** になります。またHeuristicはAlgorithmと比べ、**コードもコーディングにかけられる時間も長くなる**傾向があります。

こういった違いからか、今回の体験を通していくらかの特徴を感じました。
長くなってしまったので以下に折りたたみ式で記述します。

<details>
<summary> コードを読んで感じたこと </summary>

- **手間よりも可読性が重視されている**
　- 変数や構造体のネーミングが丁寧
　- Doxygenを用いて各構造体や関数に説明がつけられている
- **丁寧な情報の整理が必要**
　- 変数一覧や疑似コードをまとめた補助資料がある
　- データや関数がカテゴリ別に構造体としてまとめられている
- **実行時間制限ギリギリまで最適解を探す姿勢**
　- chrono::system_clock::now()で開始時刻を記録
　- ループ一回ごとに現在時刻を取得し制限時間ギリギリまで粘る
- **デバッグのために進行状況を可視化**
　- cerrを用いて標準エラー出力に現在の状況を出力
- **何にどのくらい重きを置くか見極めが必要**
　- 焼きなましの温度は問題のスケールに応じて決定する
　- 複数の条件について複数回焼きなましを行う場合などは、感度(問題への寄与度)の高い条件を優先的に最適化する
- **コードにランダム性を持たせている**
　- GRASP法や焼きなまし法など、解に多様性を持たせることでより広い範囲を見渡すことができる
</details>

この他にもきっとたくさんあると思いますが、ひとまず思いつくのはこんな感じです。
これについては具体的な実装例なども付け加えてまた別途メモを残します。


# 具体的な学習の流れ
:::note info
AHFで扱った教材は一般に公開されており、[こちら](https://atcoder.jp/contests/ahf1-S2wpmcNX)からダウンロードできます。
:::

今回のイベントでは、
1. [貪欲法](https://github.com/ponzudomo/AHF001/blob/main/01_nearest_neighbor_answer.cpp)
1. [山登り法](https://github.com/ponzudomo/AHF001/blob/main/02_hill_climbing_answer.cpp)
1. [焼きなまし法](https://github.com/ponzudomo/AHF001/blob/main/03_simulated_annealing_answer.cpp)

の順に個人で演習を行い、それ以降の最適化がグループワークとなっていました。

### 個人での演習
それぞれのアルゴリズムについて実習用コードとお手本のコードが用意されているので、自分で実装した後手元の解答と照らし合わせて丸つけできる仕組みになっています。（リンク先はC++のお手本コードです）

各アルゴリズムを学ぶ上で関係のない部分は既に埋められており、実習は**該当箇所の穴埋め形式**となっていました。**サクサク進んでやりやすかったです**。

ヒントや解説もコード内に書き込んであるため、ドキュメントとコードを往復する必要もありません。**コンパクトに講義の内容を手に持っておけるのが、復習する時にかなりありがたかった**です。

### グループワーク
グループワークの進め方については各チームに委ねられていました。
私のチームでは、**Google Docsでメモを共同編集**しながらアイデアを練っていきました。
またコンテストページからはチームメイトの提出を見ることができます。これを使って、**仲間の提出からコードを拾って、部分的に書き足して提出する**ということを繰り返していました。
取り組みやすかったのでおすすめです。

**(「うちのチームはこうやったよ」とかあればコメントで教えていただけると嬉しいです！)**

# 事前準備とおすすめの勉強法


イベント前にしておくべきことは、主に以下の3つかなと思います。他にも思いつくことがあれば教えてください。

- **ローカル環境でのコーディングに慣れておく**
- **グラフアルゴリズムについて勉強しておく**
- **各アルゴリズムについてさらっと予習しておく**

### ローカル環境でのコーディングに慣れておく
少なくとも今回の教材はzipファイルでの配布となっています。これを手持ちのエディタで編集していく上で、

- 環境構築しておく(C++のコンパイラやVSCodeの拡張など)
- エディタの基本操作に慣れておく
- [ACL](https://atcoder.jp/posts/517)や[boost](https://www.boost.org/)などのお役立ちライブラリを入れ、includeできるようパスを通しておく

などできると良いかなと思います。

最後の「ACLやboostなどの外部ライブラリをincludeできるようにパスを通しておく」について、初心者にはキツい作業に感じるので参考までに自分がVSCodeのsetting.jsonに書き足したものを載せておきます。

<details>

```jsonc:setting.json
// すべてのウィンドウでBoostとAtCoder Libraryを有効化する
"C_Cpp.default.includePath": [
    "${workspaceFolder}/**", // 現在の作業フォルダ以下を全て対象に
    "/opt/homebrew/opt/boost", // 自分のPC内でのBoostの場所を書く
    "~/zprog/zinclude",      // ACLの場所を書く
    "~/zprog/zinclude/ac-library-master"
],
// ライブラリをビルド付きで使う場合、ここらへんを書かなきゃいけないらしい
"C_Cpp.default.compilerPath": "/usr/bin/g++", // 使用するg++の場所
"C_Cpp.default.cppStandard": "c++17", // C++のバージョン
"C_Cpp.default.intelliSenseMode": "macos-gcc-arm64", // Apple Silicon環境に合わせた補完設定
"C_Cpp.files.exclude": { // 必要ないファイルを非表示にする設定 関係ないけどついでに書いとくといいかも
    "**/.vscode": true, 
    "**/.vs": true
}
```

ChatGPTに自分の環境と上記のコードを送って、「私の環境向けに書き直してください」って投げればいい感じにカスタマイズしてくれると思います。ひとまずはこれで凌ぎましょう。

ここら辺はまだ自分も理解できていません。詳しくはコメントを参考に調べてほしいです。ごめんなさい。

</details>


### グラフアルゴリズムについて勉強しておく
普通に「グラフアルゴリズム」で検索すると何やら難しい単語で書かれた難しい記事しか出てこないので、まずは競プロ用の本や記事で勉強するのがよいと思います。

**特に[鉄則本](https://www.amazon.co.jp/%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E9%89%84%E5%89%87-%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E5%8A%9B%E3%81%A8%E6%80%9D%E8%80%83%E5%8A%9B%E3%82%92%E9%AB%98%E3%82%81%E3%82%8B77%E3%81%AE%E6%8A%80%E8%A1%93-Compass-Books%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E7%B1%B3%E7%94%B0/dp/483997750X)で勉強するのがおすすめです。**
さらっとした易しい解説なので、初学者が雰囲気を掴むのにはぴったりだと思います。
運が良ければ大学の図書館などにも置いてあると思うので是非！

**また [けんちょんさんの記事](https://qiita.com/drken/items/4a7869c5e304883f539b) も大変読みやすかったです。**
こちらは鉄則本よりも詳細な解説がされています。ボリュームはあるものの、図が豊富なので初学者でもスルスル読める非常に良い記事です。**鉄則本を既に読んでいる方も目を通しておくことをおすすめします。**

（他におすすめなどあればコメントで教えていただけると助かります）

### 各アルゴリズムについてさらっと予習しておく
時間の都合上どうしてもイベントはさらーっと終わってしまうので、事前に軽く予習をしておくと話が入りやすいです。

**実はHeuristicの基本的なアルゴリズムに関しても鉄則本に記載があります**。こちらで勉強するのがおすすめです。

**似たような問題(巡回セールスマン問題)についてより詳しく勉強する場合は、まず [take314さんの記事](https://qiita.com/take314/items/dc2e6cf6d97889923c8b) を読むとよいです。**
巡回セールスマン問題に関する様々なアルゴリズムが名前とともにまとまっているため、どんなアルゴリズムがあるのか把握し、そこから必要に応じて検索などができるようになります。
解説自体も図が豊富で非常に分かりやすいです。とてもお世話になりました。


# まとめ
**非常に完成度の高いイベントでした。自信を持っておすすめします！**

HeuristicはAlgorithmとはまた雰囲気が変わってきます。
独学だとアルゴリズムの勉強に目がいきがちですが、初学者は**まず解法選択やHeuristicに適したコードの書き方など、根本的な部分を身につけておくのが良い**ように思います。
これについては、武道でまず型を習うのと同様に、初めは自己流ではなく**先輩方の綺麗なコードを使って練習するのが望ましい**です。

そういった意味でも、**上級者のノウハウを直接学べる今回のイベントはとても有益なものでした**。何より楽しかった！是非私のようなひよっこにこそ参加していただきたいです。



# 関連リンク集
- [AHF Vol.1のイベントページ](https://atcoder.jp/contests/ahf1)
- [教材や講義資料](https://atcoder.jp/contests/ahf1-S2wpmcNX)
- [問題](https://atcoder.jp/contests/ahf1-S2wpmcNX/tasks/ahc006_a)