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

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

目次

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

目次

AHF(AtCoder Heuristic First-step) とは

公式のページも併せてご覧下さい！

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

対象層と大まかな流れ

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

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

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

開催場所

Vol.1 の開催場所は毎度お馴染みメルカリ本社オフィス(六本木ヒルズ森タワー)でした。
私自身メルカリ競プロコンや Build@Mercari で何度もお世話になっているものの、毎回ほんのり迷っています。六本木は迷宮なので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と比べ、コードもコーディングにかけられる時間も長くなる傾向があります。

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

コードを読んで感じたこと

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

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

具体的な学習の流れ

AHFで扱った教材は一般に公開されており、こちらからダウンロードできます。

今回のイベントでは、

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

個人での演習

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

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

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

グループワーク

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

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

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

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

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

ローカル環境でのコーディングに慣れておく

少なくとも今回の教材はzipファイルでの配布となっています。これを手持ちのエディタで編集していく上で、

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

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

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

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

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

グラフアルゴリズムについて勉強しておく

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

特に鉄則本で勉強するのがおすすめです。
さらっとした易しい解説なので、初学者が雰囲気を掴むのにはぴったりだと思います。
運が良ければ大学の図書館などにも置いてあると思うので是非！

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

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

各アルゴリズムについてさらっと予習しておく

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

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

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

まとめ

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

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

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

関連リンク集