Atcoder Beginner Contestで有名なアルゴリズムとデータ構造に触れる。

こんにちは、イナズマです。
AtCoderの問題を解いている時に、使うアルゴリズム、データ構造は覚えているけどいまいち実装法を思い出せない…そんなことがあると思います。少なくとも私は結構あります。今回はそんなことが起こってもすぐに自分のコードを見直せるように、有名なアルゴリズム、データ構造を扱う問題をメモしておこうと思います。
※配列等の超基本的なデータ構造は、ほとんどの問題で扱われると思うので省略します。
もしかしたら私のこのブログを参考に解く問題を決める方がいらっしゃるかもしれませんが、まずはこちらの問題を解くといいと思います。 qiita.com

以下の問題は私の独断で選んでいます。良い問題に出会い次第、少しずつ追加していこうと思います。 解説等は、僕よりもAtCoderにあげられているPDF・プレゼンテーションや、AtCoder Live - YouTubeのアーカイブを見たほうがわかりやすいと思うので割愛させていただきます。

追記

「良い問題」の選んでいるブログ、いつも楽しく見てるけど、みんな「良い」の基準がバラバラなので、「どういうものを良いとするか」みたいな基準は最初に書いた方がいいとおもう。

— chokudai(高橋 直大) (@chokudai) 2018年4月2日

「確かに」と思ったので記事を一部編集しました。

AtCoder Beginner Contest

A問題

現状とくにないです。

B問題

現状とくにないです。

C問題

• C - 幅優先探索
  幅優先探索を実装する問題です。
• C - AtColor
  いもす法と呼ばれるアルゴリズムを用います。https://imoz.jp/algorithms/imos_method.html
  いもす法でこの問題を解くとなるほど〜ってなると思います。知ってないとなかなか思いつかないのではないでしょうか。
• C - 壁抜け
  ダイクストラ法(ベルマンフォード法などでも可)と二分探索を用います。難しいです。私はまだこの問題を解けてません。
• C - 2D Plane 2N Points
  pairとmapの使い方がわかります。解き方にもよるんでしょうが、pairを持ったmapのsortなど、なかなか体験できないことができました。 解法がなかなか思いつかないと思うので、どうしてもという時はAtCoder Regular Contest 092/ Beginner Contest 091 解説放送 - YouTubeを観るとわかりやすいと思います。(このリンクからいけばC問題の解説から始まると思います。)
• C - Cat Snuke and a Voyage
  ユニオンファインドやるだけ。
• C - Splitting Pile
  累積和をやるだけ。

D問題

• D - Grid Repainting
  幅優先探索を使いました。
• D - Equals
  ユニオンファインド木を使います。

おまけ

• A - 深さ優先探索
  Beginner Contestではありませんが、上述した幅優先探索と対をなす深さ優先探索というアルゴリズムを実装する問題です。