注意
こちらは個人による記述であり、公式の情報ではありません。古い情報や誤った情報が含まれる恐れがあります。
こちらはイベント自体に興味がある方向けの記事です。
AHFで学んだコツなどはまた別途まとめるつもりなので、そちらも併せてご覧ください。(後でここに貼ります)
スマホ版だと自動で目次が出てこないようなので、こちらに置いておきます。
PC版の方は右下にある目次の方が使いやすいのでぜひ。
AHF(AtCoder Heuristic First-step)とは、Atcoder社が主催するヒューリスティックコンテストの初心者向けチュートリアルイベントです。
自分は灰色のひよっこなのですが、置いていかれることなく楽しむことができました。
解説が非常に丁寧なので、最低限グラフに関する知識があればどなたでも参加できるんじゃないかなと思います。前提知識として身につけておくべきことに関しては後述します。
また実際に問題を解く期間が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の問題と違い、Heuristicの目指すところは 「クリティカルな解答」ではなく「最適解」 になります。またHeuristicはAlgorithmと比べ、コードもコーディングにかけられる時間も長くなる傾向があります。
こういった違いからか、今回の体験を通していくらかの特徴を感じました。
長くなってしまったので以下に折りたたみ式で記述します。
この他にもきっとたくさんあると思いますが、ひとまず思いつくのはこんな感じです。
これについては具体的な実装例なども付け加えてまた別途メモを残します。
AHFで扱った教材は一般に公開されており、こちらからダウンロードできます。
今回のイベントでは、
の順に個人で演習を行い、それ以降の最適化がグループワークとなっていました。
それぞれのアルゴリズムについて実習用コードとお手本のコードが用意されているので、自分で実装した後手元の解答と照らし合わせて丸つけできる仕組みになっています。（リンク先はC++のお手本コードです）
各アルゴリズムを学ぶ上で関係のない部分は既に埋められており、実習は該当箇所の穴埋め形式となっていました。サクサク進んでやりやすかったです。
ヒントや解説もコード内に書き込んであるため、ドキュメントとコードを往復する必要もありません。コンパクトに講義の内容を手に持っておけるのが、復習する時にかなりありがたかったです。
グループワークの進め方については各チームに委ねられていました。
私のチームでは、Google Docsでメモを共同編集しながらアイデアを練っていきました。
またコンテストページからはチームメイトの提出を見ることができます。これを使って、仲間の提出からコードを拾って、部分的に書き足して提出するということを繰り返していました。
取り組みやすかったのでおすすめです。
(「うちのチームはこうやったよ」とかあればコメントで教えていただけると嬉しいです！)
イベント前にしておくべきことは、主に以下の3つかなと思います。他にも思いつくことがあれば教えてください。
少なくとも今回の教材はzipファイルでの配布となっています。これを手持ちのエディタで編集していく上で、
などできると良いかなと思います。
最後の「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に適したコードの書き方など、根本的な部分を身につけておくのが良いように思います。
これについては、武道でまず型を習うのと同様に、初めは自己流ではなく先輩方の綺麗なコードを使って練習するのが望ましいです。
そういった意味でも、上級者のノウハウを直接学べる今回のイベントはとても有益なものでした。何より楽しかった！是非私のようなひよっこにこそ参加していただきたいです。
Be the first to comment
