ロアちゃんかわいい

競プロっぽい話がなされる駄文の掃きだめ

2022年振り返り

一年振り返りをします

仕事してました😡おわり😡

なんや😡😡😡

仕事

web系の会社に入りました。
真面目にwebのことを勉強したりプログラムを書いたりします。
微妙に規模が大きいベンチャーなので色んな種類の仕事があって楽しいです。
php、js、react、sql、その他色々を若干書けるぐらいになりました。

採用の仕事を頼まれて、逆求人イベントに出向いて学生とお喋りしたりとかもありました。
会社名は公開していないんですが、映像扱うwebシステムに興味があったらお声がけ頂ければ会社の話をするぐらいは出来ると思います。(競プロerの水準で見るとお給料そんなに高くないですが……)

競プロの知識が役に立つことはぶっちゃけなかったですが、一度だけ役に立ちそうなところまで行き、熱い展開でした。
ある不具合の原因になっているプログラムを参照しているファイルを全て列挙する必要があって上司が迷っていたので、「プロジェクトに入っているファイルに深さ優先探索を行って、参照関係を全部辿れば大丈夫です。そういうスクリプトを書きましょうか」と言ったらドン引きされて却下されました。かなしい
(軽度な不具合だったので、結局一部の重要なファイルのみ修正を行って事なきを得ました)

仕事以外

「仕事でやっていると仕事以外でプログラムを書こうという気にならない」という話をTwitterでよく見かけます。
誰がそんな迷信信じるかよ、と思っていたら全く書く気が起きません こまった
AtCoderやる気力も起きず、かと言って何もしないのもあれなので、脆弱性攻撃の勉強とかしていました。C言語にちょっとだけ詳しくなりました。
ネットワークのお勉強もちょっとだけやっていました。マスタリングTCP/IP入門編を読んでいましたが、分かりやすくてよかったです。

夢月ロア

かわいい はやくもどってきて😢

来年

  • 応用情報辺り取っておきたい
  • CTFやってみたい
  • Kaggleやってみたい
  • 競プロもやりたい
  • 数学勉強したい

まとめ

おふとんきもちいい すやすや よいおとしを

典型90問をRustでやっていく その1

おはようございます。

今回はタイトル通り典型90問をやっていきます。
この記事には

  • 前書き
  • 各問題の考察・感想などと、Rustで詰まった部分
  • その他雑談

が含まれます。苦手な方はご注意ください。

前書き

大学で途中から競プロやる余裕がなくなってしまって歯がゆい思いをしていましたが、社会人になったらかえって時間ができたので、復帰がてら解いていきます。
折角なので流行りのRustを覚えつつやっていこうと思います。
「典型90問を解いてみた」系の記事は沢山あるので、今回は「Rustを始めてみたいな~」と思ってる人に多少役立つ内容を目指せればと思います。
と言っても文法とかは自分で調べていただくのがよいと思います。「素人はここで躓きました!」みたいなメモとしてご利用ください。
Rustよくわからんまま書いてるので間違いがあったらごめんなさい。

典型90問 なに

E8さん(https://twitter.com/e869120)という高校生時代からレッドコーダーの凄い人が企画・作題された90問の問題集です。
競技プログラミングで出てくる典型的な要素を詰めた教育コンテンツで、僕ぐらいの層(AtCoder灰~青)にちょうど良いっぽいです。

ご本人が詳しく解説されてるので、こちらをご覧ください。

qiita.com

E8さんは昨年末に本を出されているので、こちらも是非。

Rust なに

Rustはプログラミング言語のひとつです。
特徴として

  • 生成コードの実行速度がC/C++レベルで速い
  • 安全性の高いコードが書きやすい
  • 利用可能な範囲が広い(組み込みからwebまで様々)
  • モダンな文法や機能(これよくわからないまま言ってます みんな言ってるので多分あってます) 

などがあります。
競プロにおける難点としては次が思い当たるので敬遠してました。

  • 慣れるまで書きづらい
  • 入力を受け取るのが面倒
  • コンパイル時に可能な限りエラーを検知するため、いくつか面倒な制約がある
  • エラー処理が面倒
  • ぶっちゃけC++で書く方が楽そう

proconioという素敵なライブラリが用意されたので、入力受け取りが面倒な問題が解決されました。
という訳で今回はその他の難点をこちらでどうにか対処出来ればと考えています。

競技プログラミング なに

この記事見に来てて知らないなんてこと流石にないでござるよ~(笑)

おまえ だれ

ぼく こるぼー(@zero_kpr)
きじにしてき れんらく くれ

夢月ロア だれ

かわいい だいすき
はよもどってきて

環境構築

ではやっていきます。
と言ってもここ長くする気はないので、こんな感じのツールがあって便利だよ~という話だけします。

コンパイラ・ビルドツールなど

rustupというツールに各種ソフトが含まれています。インストールはこちら(https://www.rust-lang.org/ja/tools/install
rustupにはCargoというソフトが入っています。

エディタ

vscodeを使います。ここは別に他のエディタでもあまり変わらないと思います。
拡張機能でrust-analyzerを入れましょう。
rust-analyzerはrustのリンターやコード補完、フォーマッターなどの機能を含む拡張機能です。
余談ですがLSP(Language Server Protocol)というのがあるらしく、そのおかげでrust-analyzerを他のエディタでも使えるみたいです。

後述しますが、なんかrust-analyzerが対応しているバージョンの問題でCargo.tomlファイルのeditionを2018にする必要があります。
そうしないとrust-analyzerがプロジェクトの読み込みに失敗します。
cargo newコマンドで新しいプロジェクトを作るとき、デフォルトだとeditionは2021に設定されているので、cargo.tomlファイルを開いて修正しましょう。2021を2018に書き換えるだけです。
もしくはcargo newを行う時に--editionで指定できるみたいなので、そちらでも良いと思います。

cargo atcoder

プロジェクトの作成や、書いたコードの提出を一括でやってくれます。超便利。
テストケース通らなかったら提出しないという親切設計なので安心です。

詳細はこちら(https://github.com/tanakh/cargo-atcoder)に全部載ってます。

2022年5月14日現在でちょっとした注意点があります。
cargo-atcoderでは内部でcargo newコマンドを呼び出すため、生成されたプロジェクトではeditionが2021になっています。
こちらはバージョン指定とか出来ないので、生成後に直さないとrust-analyzerがプロジェクトを読み込まず、補完などが効きません。

あと、cargo-atcoderのreadmeに書いてあるconfig.tomlの設定は絶対にやる方が良いです。
これをやらないとビルドに毎回時間を取られる上に、無駄な実行ファイルが大量に生成されて容量を食います。

cargo atcoderと、後述するproconioのinputマクロ(の元になったアイデア)はtanakhさんによって用意されたものです。
Twitterのbioに「今すぐフォローすべき競技プログラミング界のスーパーエンジニア」とあるので是非フォローしましょう。
tanakhさんのおかげでRustを始めたと言っても過言ではありません。𝐵𝐼𝐺 𝐿𝑂𝑉𝐸...

夢月ロア

問題が解けなくなったり、変なバグ踏んでイライラした時とかにおすすめです。
ぱっぱやを聴け。
Electronic Dance Roa?【Launchpad】 - YouTube

proconioについて

proconioはrustの競技プログラミング向けのIOライブラリで、inputマクロが主に使われます。
コードの上の方にuse proconio::input;を書いとけばatcoderでも使えます。

rustはそのまま使うと入力がすごく面倒で、予め入力用の関数を用意しておいたりすることになります。面倒!
そこでinputマクロが役立ちます。

input! {
  n: usize,
  a: [i32; N],
}

こんな感じで書くと数値や配列やらをいい感じに受け取ってくれます。超便利!

proconioはstatiolakeさんが、tanakhさんのinputマクロをベースに用意してくださったようです。
元々対応してなかったinteractiveな入力形式にも対応していたり、型推論がちゃんと働いたりとすごいです。
statiolakeさんがいなかったらRustを始めていなかった可能性が高いです。𝐵𝐼𝐺 𝐿𝑂𝑉𝐸...


さて、だいぶ長くなりましたが問題を解いていきます。

001 001 - Yokan Party(★4)

提出したコードは
https://atcoder.jp/contests/typical90/submissions/31498336
です。

これはいつものフッフッフッwですね。
ある値で成立したらそれより大きい値でもずっと成立、みたいなのは二分探索が使えます。

ところで、僕は基本的に二分探索の方法はめぐる式二分探索(https://qiita.com/drken/items/97e37dd6143e33a64c8c)を使うことにしています。わかりやすいのでおすすめです。

Rustでは、変数宣言はこんな感じ↓

let (mut ok, mut ng): (i64, i64) = (0, l);

で構造化束縛みたいなのが出来るようです。便利。

前処理のところは面倒なのでVecのinsertを使いました。この辺はC++にもありますね。

二分探索のところ、C++みたいにtemplateでabs関数をいい感じにしてくれないかと思ったんですが、Rustはそういうのはダメっぽいです。
かわりにi32型にabsがメソッドとして用意されているらしく、

(ok-ng).abs()

で行けました。これならC++とほとんど変わらない文字数で書けますね。
FFの方に教えてもらいました、ありがとうございます。

002 002 - Encyclopedia of Parentheses(★3)

括弧列の問題、苦手。括弧列見ただけで反射的に悲鳴を上げました。

提出コードはこれです。
https://atcoder.jp/contests/typical90/submissions/31505604

定義通りに文字列を作っていき、最終的にVec→HashSet→Vecと変換することで各要素が一つずつになるようにしています。
割と力技で解いてしまったんですが、これは解説のようにbit全探索で解けますね。そちらもこの後に出しました。
この問題は無理な解法で粘ったのもあって結構嵌りました。

Rustでは文字列の結合がString型 + &str型の形式にならないといけないようです。面倒ですね。
次の記事がわかりやすかったです。
Rustの文字列結合はどうしてString+&strなのか - Qiita

あとはイテレータ周りがいまいちわかっていません。

into_iter().collect()

みたいなやつとか。

Rustのfor文はイテレータ専用らしく、vをイテレータに変換し、各要素を見ていくようです。
for x in &vみたいに参照にしておけば借用になってムーブされません。
こちらが詳しくてわかりやすいです。
iter()とinto_iter()の違いとちょっとした落とし穴 - Qiita

こいつfor文みたいな顔をしやがって、裏で生意気なことしてやがるな。

内部でinto_iterを呼んでいるが、into_iterは配列には実装されていない。だからRustではfor文で配列を使えないわけですね。
この辺りはAPG4bを読み終えたばかりだったりすると難しそうです。

for x in &v を回している間はv自体に変更を加えられないので、上のコードでは回りくどいやり方をしています。
この辺りはc++の方が簡単な気がしますが、一方でc++で雑に同じようなことをやるとバグの原因になりがちなので、こちらの方が良いのかもしれません。
もしくはもっといい書き方があるかも?

003 003 - Longest Circular Road(★4)

提出コードは↓です。
https://atcoder.jp/contests/typical90/submissions/31509639

木の直径ですね。二回dfsをします。

Rustではグローバル変数を使うのが色々面倒なので、C++Pythonでやってたみたいに関数からグローバル変数にアクセスするような書き方が出来ません。
もちろん安全性のためですが、一々参照を関数で渡す必要があって、競プロではちょっと面倒です。

とはいえRustにはC++より便利な部分があって、それはタプル型がPython並みに使いやすいことです。
おかげで上のコードのように、dfsの戻り値が綺麗に書けます。

for next_v in &graph[now]になっているところは、先述の借用の文ですね。
この場合next_vも参照になるので、後で参照外しをしています。
for文みたいな顔をして裏で何をしているのかわからないので、ちゃんと何をしてるのかドキュメントで調べる必要があります。いや他の言語でも調べろや。
実際はfor文は3種類しかない(T, &T, mut &T, std::iter - Rust)らしいので、一回理解してしまえばそんなに辛くなさそうです。

004 004 - Cross Sum(★2)

提出したコード↓
https://atcoder.jp/contests/typical90/submissions/31510508

みんな大好き累積和ですね。ここは特に嵌りませんでした。

おわりに

一旦ここで切り上げます。
別の記事に分けるか追記するかはその内決めます。

大学卒業など

おはようございます。zero_kprです。Twitterの裏垢は(@ero_kpr)です。
ブログとか書かずに全部Twitterでいいような気がしますが、長い報告や記録はこっちの方がいいですね。という訳で2年振りに長文を書いていきます。
半分ぐらい大学の愚痴を書く予定です。

卒業

タイトルにもある通り大学を卒業しました。
休学などあり、都合5年間もいたことになります。
3年の途中からは色々ありかなり忙しく、競プロもほぼ出来ていない状況でした。
グループワークでぼく以外のメンバーがコードを書けないと宣って作業量が数倍になったこともあり、あの頃は本当に嫌気が差していました。
Twitterもちょっと荒れがちだったような気がします。途中からアイコン通りのひよこのふりをしているのが一番穏便なことに気付き、クエとかピヨしか言わなくなっていましたが。
オンライン授業もストレス要因の一つで、特に通学の運動がなくなるのが危険でした。眠りづらくなり、生活習慣が崩れやすくなりました。
何とか単位を回収しましたが、4年になっても卒業研究が忙しかったです。何故か2022年度だけ研究室に人がやたらと増えてしまい、先生の作業が倍増したせいで、僕の指導の時間があまり取ってもらえなかったのが大きいです。
論文とか進捗出してもコメントに一週間かかるとかザラにあったので無駄な作業が増えやすくなり、結構大変でした。先生も真剣にやってくれていたので、こればかりはどうしようもありません。
卒業式は顔を出さず、数少ない友人たちと居酒屋で最後にお酒を飲んで別れました。

就活

まあ卒業した大学についてごちゃごちゃ言っても仕方がありません。なんとか内定を頂けたので、4月から張り切って働こうと思います。
同じ会社の競技プログラマを見かけたことがないので一応社名は伏せておきます。オンライン会議とか進めてるとこです。心当たりのある方は是非連絡をください。ちょっと心細いので。

athleticという会社の逆求人イベントを通じて選考に入りました。普通に面接を受けたりするのと比べると、ちょっと裏口入学感があって面白かったです。(?) いや面接は何回もあったんですが。
他にも何社か受けていましたが、今思い返すと自分に合っているかどうかしか考えていなかったので、大企業を一社も受けていませんでした。
興味ない会社を受けるような性格でもないので今更ですが、雰囲気だけでも知っておくと何かの役に立ったのかもしれません。(ほんとか?)

そういえば、このブログを更新していない間にも何度か月刊「競技プログラミングは就活の役に立たない」が出版されていたようですね。
僕の場合は役に立ちました。
何しろ、僕のような半端大学謎学部に所属している人間がどれだけプログラムを書けるのかなんて傍から見て分かるはずないのです。人事はおろか、技術者でも疑いの目で見てくること請け合いです。
学歴が役に立たない以上、成果物を出すか競プロの話をするぐらいしかありません。しかし僕の作った成果物なんて高が知れてるので、そこら辺の学生よりはコード書けますよ!ということをアピールするのに競プロはかなり効率が良かったように思います。
水色の中頃だから、アルゴリズムを考える力や数学を扱う力は優秀な学生たちの中でも上位15%ぐらいはありますよ、という感じで説明すると知らない人にもイメージがつきやすいのか、多少はウケが良かったです。

直接関係ないですが、インターン見つからなくて泣いていた頃、AtCoder Problemsにほんのちょっとだけ関わらせてもらったのがかなり勉強になりました。kenkooooさん本当にありがとうございました。
他にも優しいお兄様お姉様方から励ましやお誘いなど頂いたこともあり、かなり荒んでいた心が常人のそれぐらいに戻りました。
皆さん本当にありがとうございました。

競プロ

さて、就活にも役に立つ素敵な競技プログラミングですが、前々回の記事から早2年ちょい、いつの間にか水色になっていました。もう結構前ですが……。
数学力的には水色で順当かな~と舐めたことを考えていましたが、昨日半年ぶりに出たABCで大敗を喫しました。バカ。
実は某企業で作問やらテスターやらのアルバイトをしていたので、問題自体はたまに解いているのですが、コンテストに出ないので知識は増えても腕は上がりません。
負けはしたけど、やっぱりコンテストは楽しいですね。真剣に頭を使うゲームはこれぐらいしかないので、そういう意味でも競プロ始めてよかったと思います。
在学中よりは時間を取りやすくなると思うので、今後はコンテストにたくさん出る予定です。ABC楽しみ~2022

書くことは大体以上だと思うので、これで失礼します。おやすみなさい~

チーター本の感想

おはようございます。精進不足レート冷やし子と申します。冷え冷え。

『最強最速アルゴリズマー養成講座』、所謂チーター本を読み終えたので、感想を書いておきます。

チーター本、何

チーター本、正式には『最強最速アルゴリズマー養成講座 -プログラミングコンテストTopCoder攻略ガイド』は、皆さんご存知AtCoder株式会社社長、chokudaiこと高橋直大さんの著書です。
簡単に言うと競技プログラミング未経験者の為の競プロ講座で、ヒョウ柄模様が特徴です。(チーター本なんだからチーター柄なのかもしれませんが)
chokudaiさんのITMediaでの連載『最強最速アルゴリズム養成講座』にアプリケーションプラネットでの『TopCoderレーニング講座』教材の資料を組み合わせたものとのことで、TopCoderの過去問を例題に、競技プログラミングにおける基本的な考え方が解説されています。

・対象レベルは?

上記の通り未経験者~初心者向けです。
例題のレベルが準備編、初級編、中級編、上級編に分かれています。上級編はかなり難しくほとんど自力で解けませんでした。
2020年2月10日現在のAtCoderのレートで言うと、灰色~緑色向けだと思います。

・どうでしたか

この本の方針は全探索を軸に、コンピュータに上手く問題を解かせるための考え方を身に着けるというものです。
些末な知識はほとんど載っていません。
基本的なアルゴリズムであるダイクストラ法なども後述するような丁寧な説明があるものの、例題などは用意されていませんでした。
前回のクソ長い記事の最後の方で紹介した動的計画法や貪欲法の項目で、
「こういう名前のアルゴリズムがあるわけではなく、あくまでアルゴリズムの設計手法、方針にこういう名前が付いている」
というようなことを書いたと思います。
そういった、アルゴリズム設計の中心的な部分を主に解説してくれる本だと思っていただいて大丈夫です。

上記のように方針が明確な分読み進めやすく、僕のような初心者にはとても良い本でした。
各章のテーマ分けも分かりやすく、「全探索する」「計算量を評価する」「動的計画法・メモ化で計算短縮」「探索範囲を狭める」「貪欲法」などが解説されています。
これらの方針を気にするようになってから、プログラミングの見え方が随分変わった気がします。

一方、知識量は大して増えないと思った方がよいです。
あくまで根本的な思考力の養成が目的だからか、Union-FindやDijkstra法なども、アルゴリズムの考え方に重点が置かれて解説されていました。
そうしたアルゴリズムの知識量を増やしたい方は蟻本(正式には『プログラミングコンテストチャレンジブック』といいます)を読むと良いと思います。(蟻本はまだ読み終えていませんが、今読んでいる部分だけでもアルゴリズムの種類数が段違いです)
僕のようにチーター本→蟻本というのも全然ありだと思います。(あり本だけにw)

以下は気になった点。
TopCoderのデザインがクソ分かりにくく変更されており、登録が難しいです。注意。
TopCoderの過去問、どういう訳か表示がクソ遅い時があります。後時々バグります。
・プログラミング全くやったことない人は注意ですが、クラス等分からないことがあると思います。一応説明はありますが、ある程度は仕方ないので調べましょう。
・説明が分かりにくい部分があり、何度か読み直すことになりました。ソースコードと読み比べながら根気よく読むことが求められます。
・確認した限り一か所だけ数式の誤字(p281, 多分2C→2^C)がありましたが、ソースコードの方は合っていたのでそちらをよく読むようにするのが良いと思います。

総括するととても良い本でした。夢月ロアちゃんの動画も見てみると尚良いと思います。

www.youtube.com

ロアちゃんかわいい。ではおやすみなさい。

競プロ始めてから一年間のうちに勉強したアルゴリズム(≒AtCoder緑になるのに必要な知識?)

おはようございます。おはようございますです。(私の名前はおはようございますです)

競プロを始めてもうちょいで1年になります。折角なのでここまで勉強したデータ構造とアルゴリズムについての知識を列挙してみようと思います。

現在の僕のレートが緑なので、この辺を覚えておけば緑になるには十分なのではないかと思います。数学とかいうのは知りません。



僕よりも後に始めた初心者(主に灰色、茶色)向けです。
なのでなるべく分かりやすい説明を心がけたいとは思いますが、変数や基本的な制御構文(for文とかif文とか)は知っているものと仮定します。
仕様言語はC++を前提にするので、Pythonを使っている人は少し分かりづらい部分があるかもしれません。配列とか。

クソ長いので全部読む必要はありません。
全部読む必要は全くありません。目次付けたんで気になるところだけでいいです。
あくまで説明は紹介程度です。詳しい実装や数学的証明は適当にググってください。
あと、順番をあまり気にせずに書いたので、この順番が難易度の低い順になっているわけではありません。
いずれも便利なアルゴリズムで、様々なところで使います。気になったら詳しく調べてみてください。

もし「これ必要だろ!」みたいなのがあったら@zero_kprまでご連絡ください。よろしくお願いします。

今のところ使っている競プロライブラリです。
ユークリッド素数判定、mod上のべき乗計算、mod上の二項係数計算、segment-tree、Union-findが入っているはずです。
バグがあっても責任が取れず、かついかにもバグがありそうなので、実装の参考程度にしてください。
https://github.com/zerokpr/Kpr_Library


目次!

0.データ構造とアルゴリズム

そもそも「データ構造とアルゴリズムってなんやねん」みたいな人もいらっしゃるかもしれないので概略だけ書きます。
データ構造はその名の通り、数字などのデータをどのように保存するか、扱うかという話です。
次にあげるような配列や構造体、そして今回は載せませんが、ポインタなどの機能を駆使し、プログラマーが扱いやすい便利な形にします。

アルゴリズムは「コンピュータで問題を解くためにどういう手順を踏ませるか」という話です。
高校までの数学では、恐らく人間がぱっと解けるような問題を習ってきた方がほとんどだと思います。
世の中には「一般的な解は出せないが、この手順を踏めば必ず解ける」という問題が沢山あって、この「手順」のことをアルゴリズムと呼びます。
高校数学でも「ユークリッドの互除法」と呼ばれるものがありますが、これもアルゴリズムの一つです。実装も簡単。

もう少し踏み込んだ話をすると、アラン・チューリングという偉大な数学者が「計算可能性」という性質について議論をしましたところから話が始まるそうです。
コンピュータ、すなわち計算機械の理想的な形を数理モデルにし、これにより計算機を数学的に記述するようになりました。
より詳しい話はオートマトンなどを調べるとよいと思いますが、僕もそんなに知らないのでここまでにします。

アルゴリズムの利点として、どんなプログラミング言語でも使えるというのがあります(例外はあるかもしれませんが……)。
アルゴリズムは理想的な計算機械が持つ性質のみを用いて、どのような手順を踏めば高速に目標を達成できるかという話なので、言語は関係ありません。
そして方法論の問題なので、実際に実装する段階でも言語毎の細かい仕様とある程度離れた段階で問題を考えることが出来ます。
競プロerの間でたまに「どの言語がいいか」みたいな話になるんですが、アルゴリズムだけ見るのならどうでもいい話なのです。

競技プログラミングはデータ構造とアルゴリズムによって、数学的問題をいかに解決するかを素早く考える競技だと言ってもいいかもしれません。(数学的問題に限るわけではないですが、基本的にアルゴリズムの裏には数学的な構造があるようです。数学が苦手な人も勇気を出して触れてみると、意外と楽しいですよ)

始めたばかりで困っている方向けにオーダーについて簡単に説明します。
アルゴリズムの重要な部分として計算量があります。競技プログラミングでもこの計算量が重要で、無駄に計算量の多いアルゴリズムを組んでしまうと時間がかかり過ぎてしまい、TLE(時間切れ)を起こしてしまいます。
同じアルゴリズムであってもOSや処理系が異なると計算時間は違うので、アルゴリズムの計算量の評価はループ回数によってなされます。
O(n)のような記法を見たことがあると思いますが、これは大雑把に言うと「nが十分大きいとき、nに比例する計算時間がかかる」という意味です。
競技プログラミングではn=10^5など大きい値を使うので、ざっくり「O()はかっこ内の式に比例するんだな」ぐらいに思っていて大丈夫です。
また、O(1)は定数時間という意味で基本的に高速ですが、あくまでデータ数に比例しないだけで計算量が小さいとは限りません。
オーダーは重要な考え方ですが、最終的にはループ回数を意識すべきです。C++だと10^8回が限界だと思ってください。(ループ内の処理が単純で簡単なループであれば、10^9回ぐらいでも1秒程度で済むことがあるようです。が、これは通ると思わない方がいいです。最終手段。)

さて、本記事では予告なく計算量の評価にO(n)を使うことがあります。「nってどっから出てきたんだ」と思ったら、その時考えているデータ個数がn個程度なんだと思ってください。

1.配列

コンピュータには「メモリ」という場所があります。メモリ空間とか言ったりもします。
変数はよく箱に例えられますが、これからメモリと言った時には変数の箱が横一列に並んだものだと思ってください。
配列はメモリの連続している部分にずらりとデータを格納します。(言語によってはそうじゃないのもあるかもしれませんが)
int a[100];
と宣言すると整数型を入れられる箱(変数)がメモリ上に100個並んだ状態で作られます。
一番先頭から数えていき、i番目のデータはa[i]というように調べることが出来ます。
配列の「何番目か」、つまり配列の位置に当たるものをインデックス(index)と呼びます。数列の添え字に相当。

ここで注意ですが、大体の言語では0-indexedと呼ばれる方式が取られていて、配列の先頭を0番目と数えます。
AtCoderの問題文で数列が出てくる時の添え字は1-indexedなので混乱しがち。
これが中々の曲者ですが、便利なところもあるので頑張って慣れておくと嬉しいことがあるかも?

これだけ見ると「ただの変数の羅列やんけ!」と思う方もいるかもしれませんが、適当な値を適当な場所に置くことが出来るというのはとても重要なことです。
後述するstack, queueやunion-find、さらにはsegment-treeのようなデータ構造を知ってもらえれば、便利さを実感出来ると思います。

2.線形探索

皆大好きLinear-searchです。
線形探索は調べる対象の中から答えをしらみつぶしに探していく「全探索」と呼ばれるアルゴリズムの一種です。
(この「答え」とか「探す対象」みたいな単語はちょっと曲者なので、慣れた方がよいです。)

データが一直線に(線形に)並んでいる場合の全探索を線形探索と呼びます。実際にはもう少し幅広いですが。
代表的な問題例としては、1 3 6 8 7 ... という入力が与えられこれを配列に格納した時に、「9という値が入っているか?」という問題が考えられます。
データ構造は配列とは限りません。連結リストなどを見ていく場合も線形探索です。

分かる人が見ればfor文などのループで配列を順番に見ていけばいいだけの話ですが、最初は線形探索でも結構厄介かもしれません。
ループ回数が10^8を越えそうなら気を付けましょう。TLEを起こします。

大体次のように書きます。

for(int i = 0; i < n; ++i){
    if(問題の条件を満たす答え) return 解;
}

全探索一般の話は色々あるのでまた後でしようと思います。
(そういえば全探索って英語でExhaust-Searchって言ったりするらしいです。面白い)

3.スタック、キュー

スタック(stack)、キュー(queue)は非常に有名で、基本的なデータ構造です。
配列を使って作られた、値を出し入れできる変な筒だとでも思っておけばいいです。
push()で筒に値などを入れて、popで値を取り出します。
このとき値が出てくる順番が、stackでは最後にpushした値から、queueでは最初に入れた値から出てくるようになっています。

後述するdfsやbfsというアルゴリズムに使うのですが、正直それ以外の使い方はよく分かっていません。
(実はOSとかコンパイラとか、めっちゃ低レイヤ部分で使います。関数へのポインタをstackに積んだり、操作をqueueに入れたりするらしいです)

それでもたまに使います。
B - Unhappy Hacking (ABC Edit)

実際のところ、単純なものであれば実装はとても簡単なので、その場でstackやqueueに相当するものを気づかない内に実装していた~という事もあります。
なので僕はstack, queueと言った基本的なデータ構造そのものよりも、問題の数学的構造を見抜いてこうしたデータ構造を使えると判断する方がよほど難しいのではないかと思っています。人によるのかもしれませんけどね。
現状のAtCoderでは、少なくとも初心者については、後述する優先順位付きキューなどを上手く扱えるかの方が重要だと思います。

4.両端キュー(deque)(読み方がよくわかりません)

dequeの読み方は諸説あるようです。僕は「デック」と呼んでいます。
両端キューはキューの拡張版のような感じで、両端から値をO(1)で追加、削除できます。
キューと同じくこれと言って高度な使い方を思いつかないんですが、シミュレーション問題、順序管理に使うことがあります。
一応dequeを使う問題がABC-Dに出てたことがあります。これも確かシミュレーションっぽい感じの全探索だったかな?

deque一般の性能ではないんですが、C++のdequeはO(N)で特定半開区間のデータを削除できたりします。

5.グラフ

丸とかで表現される頂点が矢印やただの線(辺と言います)でつなげられたものです。
座標平面上の曲線とは違い、こちらは離散数学という分野で扱われます。

電車の路線図とかもある種のグラフです。
都市を頂点、道路を辺に見立てて考察したりとか、応用は非常に幅広いです。(巡回セールスマン問題という言葉を知っている人も多いでしょう)
データ構造なのかちょっと怪しいですが、まあデータ構造みたいなもんです。少なくともデータ構造としてのグラフはあると思います。

頂点が矢印でつなげられたものを有向グラフ、線でつなげられたものを無向グラフと呼びます。
無向グラフは、線を両側へ行き来できる二組の矢印として置き換えると有向グラフと見なすことができます。
実装上も機能、考察上もそのように考えられます。

とりあえずよく使う用語を並べておこうかと思います。他の記事の方が図とかつけて詳しいとは思うんですが、折角なので紹介程度に。
この章と次章を読んで「自分でも行けるかも!」と思ったら是非グラフを使う問題に挑戦してみてください。解けなくても解説を見てみてね。

・頂点(vertex, node)
グラフを構成する点の部分です。白丸で表現されることが多いですが、「何を点と見なすか」で問題がガラリと変わることがあります。
何らかの状態が変化していくとき、各状態を頂点と見て推移全体をグラフで表現するとかはよく見かけます。
頂点は頂点番号を付けて管理することもあれば、後述する構造体などを使うこともあります。

・辺(edge)
グラフのうち、頂点同士を繋ぐ矢印や線のことです。
矢印の場合(有向辺といいます)は一方向にのみ移動でき、線の場合(無向辺といいます)は頂点を自由に行き来できます。
上述した通り、無向辺は有向辺二組で表現できます。

こちらは頂点と違い、シンプルにどの2頂点を繋いでいるかと、重みという情報のみで構成されていることがほとんど。
そもそも辺が存在するかだけが重要な場合も多いです。
重み(コストなど言い方は色々あります)を持つ場合があって、この辺を道のように見立ててこの上を通りたい時にどのぐらいの時間がかかるか、費用がかかるかなど、使い方は様々です。

グラフは頂点と辺で構成されます。離散数学ではグラフを頂点集合と辺集合を含めた集合として表現します。

・連結グラフ(connected-graph)
全ての頂点が辺でつながっているグラフを連結グラフと言います。
たまに勘違いしている人を見かけるので補足しますが、辺でつながっていなくてもグラフはグラフです。
上述した通り、頂点と辺の集合がグラフなわけですが、辺集合が空集合、つまり頂点のみで辺が存在しないような場合もグラフと呼びます。(この場合グラフとしての意味はあまりないですが、例えばUnion-Findを扱うような問題ではグラフの初期状態はこのようになります)

・次数(degree)
ある頂点についてのつながっている辺の数です。
有向グラフの場合は出次数と入次数があります。
出次数はその頂点から出ている有向辺の数、入次数はその頂点へ向かっている有向辺の数です。

・道(path)
ある頂点からどこかの頂点まで、辺を辿って行く道筋のことです。
言い換えると、辺でつながれた頂点の列とも言えます。
道の始まりの頂点を始点、行き先になる終わりの頂点を終点と言います。

・閉路(cycle)
始点と終点が同じ道です。
巨大なグラフに閉路があるかどうかを調べるのは重要な話題だったりします。

・木(tree)
閉路がない連結グラフです。

他にもたくさんありますが、本記事ではここまでにします。

グラフは離散数学と呼ばれる分野でよく扱われます。様々な事象をグラフで表せる上に、大概のグラフは計算機上で実装が出来ます。
データ管理の典型ですが、各頂点に番号(頂点番号といいます)がついています。この番号を利用して様々なアルゴリズムが使えます。
実装には大きく分けて二種類あります。

・隣接行列
すごくシンプルな考え方です。
頂点数をn個としたらn^2の配列を用意して、i行j列の値が1なら頂点iから頂点jへの辺が存在する、0なら存在しないと考えます。
この方法は頂点数に対して辺の数が多い時に有効で、また辺に重みやコスト等数字が割り振られている場合にも便利です。上の値の1をコストに変えるだけなので。(コストが0の辺は存在しないのと同じ)
先述した無向グラフと有向グラフの関係から、無向グラフでは、隣接行列は対角線について線対称になります。

・隣接リスト
こちらはC言語だとポインタを扱ったりするので、少し厄介かもしれません。
上述したリストというデータ構造の配列を用意します。
i番目のリストに含まれる数が、頂点iに隣接する頂点番号を表します。
実装次第で辺を含ませることも出来ますが、後述する構造体の知識が必要だったり、構造体を使わない場合はさらにややこしいことになります。
ただし、cppだとvector>などを使って実装できます。
この方法は頂点数に対して辺の数が少ない時に有効です。隣接行列ではO(n^2)のメモリが必要ですが、こちらはもっと少ないメモリで実装できます。
(一応補足しておくと、AtCoderでは一つのプログラムで使用可能なメモリに制限があり、これを超えるとMLEというエラーになってしまい不正解です)
構造体を使うのは少し慣れが必要かもしれません、他の人の実装を見てみるとよいです。

実際には、上の様な方法でグラフを実装する必要はなくて、6に上げるdfsやbfsなどのアルゴリズムが使えさえすればいいという場合も多いですが。(とはいえグラフが与えられる場合はグラフの構築をしなければいけません)
グラフに対する考察は色々なされているので、色々調べてみると面白いです。AtCoderでも死ぬほど出てきます。

6.構造体

これもデータ構造か怪しいですg(ry
非常に重要な概念で、大体の言語に構造体に相当するものが用意されていると思います。
ざっくり言うと、数字やら文字列やら、いくつかの要素を纏めたものです。
C++のpairやtupleも一応これに相当します(多分)。pairとかpairとかは皆さんも使ったことがあるのではないでしょうか?
一般の構造体では、メンバ変数と呼ばれる名前付きの箱に値を格納しておきます。
(ちなみに宣言の方法にはstructとclassがありますが、大して変わりません)
それぞれ型を持っていて、各要素にアクセスする時は大体ピリオド演算子を使うことになります。
そして構造体を定義すると、それ自体を一つの型のように扱うことが出来ます。
構造体の配列などもあり、次に紹介する深さ優先探索幅優先探索では非常に重要な役割を果たします。
また色々と便利な使い方があります。
例えばゲームのキャラクターのステータスを

struct character{
    int hp, attack, defence, speed;
};
character hero;
hero.hp = 100;

みたいな感じで管理できます。

重要だけど難しいシリーズその1です。
先述したグラフの頂点を順番に調べていきます。
大抵のグラフには分岐がありますが、この分岐の時にどういう順番で調べていくかがdfsとbfsの違いです。
dfsではstackを、bfsではqueueを使います。

//queue または stack を使います。今回はlistと表記します
while(!list.empty()){
    T now = list.front()またはlist.top(); // 現在の状態
    visited[now] = true;  // nowを訪問済みに
    // nowに対する何らかの処理
    for(next = nowに隣接する頂点){
         if(nextを訪問してなかったら) list.push(next);
    }
}

という具合です。(visited[now]で何をしているか分からない方へ。単にnowを調べたかどうかを見ているだけです。trueかfalseが入っていて、訪問済み、既に調べたならtrueを入れています。)

dfsに関しては再帰関数を使うことが多いです。

重要な工夫として、メモ化や枝刈りというのがあります。
・メモ化:一度計算した結果を配列などに残し、無駄に何度も計算してしまったり、関数呼び出しをしてしまうのを防ぐこと。
・枝刈り:無駄な計算をしそうな場合探索を打ち切ること。メモ化もこの一種。

この辺は言葉で説明するのが難しいので、wikipediaも参照してください。

8.bit

「コンピュータは0と1で計算する」みたいな漠然としたイメージを耳にしたことがあると思います。
これは正しくて、コンピュータは1と0、ONとOFF、HighとLowなど、2つの値から成り立っています。
細かいところでは電子回路でそのようにコンピュータを作っているからなのですが、僕は苦手なので放っておきます。

重要なのはコンピュータにおける数がbitと呼ばれる1か0が格納された二進数であるということです。
アルゴリズムを考える上では、数自体が1か0のみ格納可能な配列とも言えるのです。
無駄に配列を使わずに、bitで表現が出来る場合はbitを使うと高速化できることがあります。

bitは1の時に真、0の時に偽を表すと考えるとブール代数という分野に繋がります。この章で表すbitはこのブール代数と関わりが深いです。
この二進数についてはコンピュータの最も得意とするところであり、数の四則演算とはまた別の演算「bit演算」というものが用意されています。

列挙しますが、こちらのけんちょんさんの記事が非常によいので先にこっちを見てもいいと思います。
ビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜 - Qiita

よく使うbit演算は次です。二進数では先頭に0bを付けます。
予めイメージを伝えると、それぞれ「かつ」とか「または」のような論理演算を、各bit毎にやる感じです。
なのでまずは使い方よりも各bitにおける変化を理解するのがいいと思います。

論理積and &
a&bはaとbの各bitを見て、両方が1のものを1、それ以外が0になっているような値を返します。
2と3だったら二進数で0b10, 0b11 なので、2&3なら0b10となり2&3 = 2となります。
同様に、6&3なら0b110と0b011の各bitを見比べて、6&3 = 2となります。
論理和or |
a|bはaとbの各bitを見て、片方でも1ならそのbitが1になっているような値を返します。
上と同様に二進法を考えて、2|3 = 3, 6|3 = 7となります。
・否定not ~
各bitを反転させた値を返します。 つまり0b10001は0b01110に、0b00101は0b11010になります。
こういうのを補数と言います。あまり使わない方がいいかも?(補数は厄介なイメージがあります)
排他的論理和(とても重要)xor ^
a^bはaとbの各bitを見て、一方のみが1の場合1、両方が同じ値なら0になるような値を返します。
2^3 = 1、 6^3 = 5となります。
排他的論理和は非常に面白い性質を持っていて、AtCoderの問題でよく出てきます。
この性質を列挙すると長くなるので、気になったら次のサイトを参照してみてください。
排他的論理和について移項が出来るとか色々面白いです。
競技プログラミングにおけるXORのTips - Qiita
実際の応用も多く、「パリティ 排他的論理和」とかで検索するといいかも。

・シフト演算 <<, >>
bit全体をずらす演算子です。
左シフト演算子<<、右シフト演算子>>があります。
見た目と名前の通り、<<はbit全体を左に、>>は右にします。
次のようになります。
1 << 1 = 2, 1 << 2 = 4, 3 << 1 = 6
2 >> 1 = 1, 3 >> 1 = 1, 7 >> 2 = 1
お気づきの方もいらっしゃるかもしれませんが、1 << aだと1を2のa乗倍しています。
指数の計算には繰り返し二乗法というアルゴリズムで早くてもO(logn)程度かかるのですが、2のべき乗だけは特別なのです。


さて、このbit演算を利用して様々なことが出来ます。
各bitの状態は、例えばi番目のbit(調べたい数をxとして)であれば if(x & (1 << i) )のように調べることができます。
このリンクで表示される項(3.ビット演算を用いたフラグ管理)を参照。
ビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜 - Qiita
ゲームキャラクターのステータス管理とか、集合の管理とか。(毒のbitが1になっていたら毒ステータスを持っている感じです。)
競プロでよく使うのがbit全探索です。
bit全探索は二分木の深さ優先探索に相当し、しかし深さ優先探索に比べて必要なメモリ数がずっと少ないです。
この探索では各状態をbitの01で表現し、1になっているbitに付いて探索をしていきます。
bitじゃなくても出来なくはないですが、覚えておいて損はありません。それどころか重要な知識です。
次はちょっと実装が難しいですが、bit全探索で出来ます。試しにやってみてください
(難しいので、もう少しいい問題が見つかったらそっちも貼ろうかと思います)
C - Many Formulas

9.累積和(cumulative-sum)

競プロに限らず、配列の連続する任意の区間について配列の部分和を求めたい場合があります。
つまり、非負整数x, y(x < y) についてa[x]からa[y]までの数列の和が知りたい時です。
「普通にfor文で求めればいいのでは」と思う方もいらっしゃるかもしれませんが、これは最悪n回のループをしなければいけません。
単純に求めるだけならいざ知らず、この部分和を色々な区間で、しかも何度も求めたい場合には使えないかもしれません。
この部分和をn回求めるような問題があったら、計算量はO(n^2)になってしまいます。TLEまったなしです。
そこで累積和という、非常に有名でしかも実装のしやすいデータ構造を使います。
累積和では、前計算をしておくことで、配列の部分和を高速に求めることが出来ます。
まず配列aに対し、累積和配列asumを次のように実装します。

int a[n]; // 適当に入力する
int asum[n+1];
asum[0] = 0;
for(int i = 0; i < n; ++i) asum[i+1] = asum[i] + a[i];

asum配列はaの先頭からの和を格納しています。asum[i+1] がa[0]からa[i]までの和になります。
a[x]からa[y]までの区間和は、a[y+1]-a[x]で求められます。

「[x,y]の区間和なのにa[y+1]-a[x]なのか」と思った方がかなりいらっしゃると思いますが、実装上この方が便利なのです。
数学的に言うと、a[y+1]-a[x]で半開区間[x, y+1)についての和を求めているわけです。プログラミングではこの半開区間が色々なところで出てきます。
半開区間についても知っておくとよいかもしれません。

これで準備段階の前計算でO(n)、実際に求める時にはO(1)で部分和を求められます。
競プロを始めた人が一番最初に覚える高速化アルゴリズムではないでしょうか。知らなかった方は是非この機会に覚えてみてください。

このように、配列に記録した結果を利用して、計算を省くアルゴリズム動的計画法と言います。
厳密な定義があるわけではないので、配列の結果を利用して無駄な計算を省いて、かつ配列の値同士に漸化式のような構造があるものが動的計画法だと思っておいて問題なさそうです。僕に石を投げる前に厳密な定義をせずこちらが適当な発言をする隙を与えた世界に石を投げてください。

10.二次元累積和

累積和を二次元配列についても求めるアルゴリズムです。
二次元配列の中の長方形の区間に対し、長方形で囲われた要素の和を高速に求めます。
正直こちらはあまり使わない気がしますが、たまに使います。(結構前のABCのD問題で出たことがあります。)
こちらも一次元の累積和と同様に、半開区間を使います。
実装は少し面倒なので適当にググってください。もし分からなかったら僕のGitHubのデータ構造ライブラリのページにあったと思うので、そちらを確認していただいても結構です。(コメント書いてたと思うので)

11.尺取り法

緑になるのに使うのか……?という感じではありますが、ABCで何度か出ていますし覚えておいて損はありません。
しゃくとり法は次の条件を満たす問題をO(n)で解くことが出来るアルゴリズムの設計手法です。

・ある区間で条件が成立する⇒これを含む区間でも条件が成立する
・ある区間で条件が成立する⇒これに含まれる区間でも条件が成立する

似て非なる条件です。
しゃくとり法は何らかの条件を満たす区間の数え上げなどでよく出てきます。

けんちょんさんの記事が本当に分かりやすいので、是非読んでみてください。
しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita

12.Union-Find-Tree

皆大好きUnion-Findです。僕は心の中に夢月ロアちゃんとUnion-Findの神を住まわせています。
グラフの2頂点が連結しているかを判定するアルゴリズムに用います。

グラフの各頂点に1からnまでの頂点番号が振られているとします。
1と3を連結、3と5を連結、5と9を連結、5と11を連結、3と9を連結、8と3を連結……と、いくつかの頂点を連結させるとします。
ではこのとき、1と8はつながっているでしょうか?

こういう問題を解く時、どのような方法を取ればよいでしょうか。
通常のグラフでは連結の度にその二頂点の間に辺を作り(つまり隣接行列などでgraph[i][j] = 1 にするなどして)、片方の頂点からbfs、dfsなどでもう片方の頂点を探します。
しかしこれでは、最悪O(n)の時間がかかってしまい、累積和の時のように何度も使うことができません。

そこで、Union-Findの出番です。
このデータ構造では、連結された頂点のグループごとに一つ、代表となる頂点を決めておきます。
そして、連結する時に、片方の代表頂点をもう片方の代表に書き替えます。(簡単に言っていますが、自分で1日そこら考えて思いつくようなものではないです……)

これで二頂点が連結しているかをO(α(n))の計算量で求めることが出来ます。
このα(n)というのはアッカーマン関数という関数の逆関数で、まあほぼ定数倍みたいなもんです。実質O(1)と思って大丈夫です。
これも毎回という程ではないですが、結構頻度が高いです。
しかし実装しやすい部類なので、初心者におすすめです。
僕も最初に自力で実装したデータ構造がこのUnion-Findだったので、とても愛着があります。
実装する時、必ず次の二つの工夫をしなければなりません。
・グループの頂点数がよ多い方に、小さい方をくっつけるようにする(マージテクとかいうらしいです)
・根を調べる際、再帰的に見ていくときに各頂点を根に直接つなぎ直す(経路圧縮といいます)
この工夫が片方でもないUnion-Findは判定等の計算量がO(logn)になってしまいます。(それでも十分速いですが……)
両方ないと最悪O(n)になっちゃいます。困る。

連結を利用することで、辺を追加する時に閉路が出来てしまうかを判定することも出来ます。
二頂点i, jを連結する前に既にisConnected(i,j) がtrueなら閉路が出来てしまいます。

他にも色々な応用がありますが、列挙すると書ききれなくなってしまうので割愛します。

13.ソート

ソート(sort)とは並び替えるという意味です。
文字通り、配列の要素を適当な順序に並び替えるようなアルゴリズムの分野をソートと呼びます。

a[] = {4, 8, 9, 3, 11, 30, 15, ... }

というデータを小さい順(昇順)、大きい順(降順)に並べるにはどうすればいいか、という話です。

一番簡単なソートはバブルソートと言われるものです。昇順に並べるなら、

「隣合う二つの要素について比較し、左の方が大きければ二つの要素を交換する」

という作業をひたすら繰り返し、全部並び終えたら終了です。バブルソートの計算量はO(n^2)で、n<= 10^5ぐらいになるとAtCoderでは使えません。

ここでは詳しく説明しませんが、ソートにはもっと高速なものが多く存在します。
名前だけ列挙すると、マージソートクイックソートヒープソート、基数ソートなどがあります。
基数ソートはものすごく限定的(要素数が小さい場合にしか使えない)なので例外として、他の「大小比較を用いた」ソートは、どう頑張ってもO(nlogn)より高速にはならないことが数学的に証明できます。(結構簡単でかつ面白いので興味のある方は是非調べてみてください)

AtCoderでは、これらのソートを実装しなければならない機会は中々ないと思います。
というのも、競プロで用いる代表的な言語(C++C#Python)ではソートアルゴリズムが用意されていて、これらの計算量はO(nlogn)になっています。(どのソートアルゴリズムが用いられているかはよく分かりませんが……)
書き方を決めてしまえば、詳しい実装の知識がなくても使えるようになっているので余り気にする必要はないかもしれません。(とはいえ、アルゴリズムの知識としてマージソートやらを知っておいた方がいいのは間違いないと思います)

ソートアルゴリズムは、数学的には並べる対象が全順序集合(どんな二つの要素についても比較が出来る集合のこと)をなしていれば適用可能です。
例えば、文字列であれば辞書順という順序が定義されるのでソート可能ですし、pairも一番目の値を優先的に比較することでソートできます。
C++では順序関数を定義することで、sortの順序の定義をこちらで操作することが出来ます。
自作の構造体にも順序を定義することができるので、この順序によって全順序集合になっているかに気を付けると、上手く定義することができます。

ソートをすると、データ上を二分探索することができます。二分探索については後述しますが、線形探索よりずっと早くて嬉しいです。

14.トポロジカルソート

「お前緑になるのに必要ない知識やろシリーズ」第一弾です。ABC-Dまでではまず使いませんが、勉強したものをなるべく列挙したいので紹介しておきます。

トポロジカルソートはソートの一種ですが、上記のソートたちとは本質的に違うものです。
このソートは、グラフの頂点を(つまり頂点番号を)次に説明する基準で並び替えるもので、このグラフはDAGと呼ばれる有向グラフ上で用いることが出来ます。
DAGは競プロだとこのトポロジカルソートでしか使わない(と思う)ので、ここで軽く紹介するに留めておきます。
(追伸:この記事を公開した後にコメントを頂いたんですが、めっちゃ使うらしいです。状態の遷移がDAGにならないとDP出来ないんだとか。)

DAG(Directed acyclic graph, 有向非巡回グラフ)はその名の通り、巡回路の無い有向グラフです。
つまり、どんな頂点についても、そこから矢印を順番に辿っていって一度通った頂点を通ることがないような有向グラフのことを言います。
DAGの重要な性質として、「矢印によって頂点に順序を定めると、半順序集合になる」というものがあります。
(半順序集合とは、全順序集合と対照的に、「一部比較可能でない要素の組があるが、いくつかの要素の組に順序が定まっている」集合のことです。「順序集合の内、比較不能なものを許容したもの」と言い換えることも出来ます。)
また、逆に半順序集合をDAGで表すことも出来ますし、DAGで表せないものは半順序集合ではありません。

上のソートの章で述べましたが、一般的にソートというのは全順序集合、つまりどの二つの要素についても比較可能でないと適用できません。
しかし、トポロジカルソートではDAG上を深さ優先探索で走査することで、この半順序集合を強制的にソートすることが出来ます。

トポロジカルソートでは、ソートの結果が1つに定まりません。
条件を満たすような順序が複数存在する可能性があり、このためソートとしては例外的です。
実装をする上でも、始点によって結果が変わると思います。

トポロジカルソートの何が嬉しいかまでは僕も詳しく勉強していないので割愛しますが、DAGについては因果関係の表現やネットワークの表現など、色々な応用があるようです。
有向非巡回グラフ - Wikipedia

トポロジカルソートの唯一知っている利用例は、作業のスケジューリングです。
矢印で優先度を表現し、これが半順序集合の場合でも順番を与えることができます。

詳しく知りたい人は次でも見てください。応用例が簡単に載っています。
トポロジカルソート - Wikipedia

15.ダイクストラDijkstra)法

グラフ上の二つの頂点について、最短経路を及び最短距離を求めるアルゴリズムです。
辺の重みが1なら深さ優先探索幅優先探索で事足りるのに対し、辺の重みが1でない場合に役立ちます。

このアルゴリズムはグラフが負の重みの辺を持たない場合にのみ使うことが出来ます。
もしグラフが重みが負の辺を持つなら、後述するベルマンフォード法を用いなければなりません。

最短経路を保存することが出来ます。配列に値を格納し、ゴールから逆に辿っていくバックトラックという方法を使います。
アルゴリズムの実装内に一行追加するだけで済みます。

実装はそう難しくないですが、どうして正しく動くのかを理解するのは難しく感じました。
機能の追加などを考えると実装をここに載せても仕方がない気がするので適当に調べてください。
ちなみに後述する優先順位付きキューを使います。
アルゴリズムはとても参考になるので、疑似コードから自力で書いてみることをお勧めします。(気が向いたらここに疑似コードを載せておきます)

実装が難しい場合は、どなたかのライブラリから頂いてくるのも良いかもしれません。(この章を書いた時点で僕はダイクストラ法をライブラリにしていません。悪しからず)

十分速いものは2種類ありますが、大体計算量はO((E+V)logV)ぐらいです。(Eは辺の数、Vは頂点数)
使う優先順位付きキュー、というかヒープの種類によって異なります。

これも有名なアルゴリズムで、実際の応用も沢山あるので知っていて損はありません。
競プロでもよく使います。

16.ベルマンフォード(Bellman-Ford)法

これもダイクストラ法と同じで、グラフの二頂点間の最短コストを求めます。
ただし、ダイクストラ法は負の辺があったら使えなかったのに対し、こちらは負の辺があっても使うことが出来ます。

勿論、グラフ内に負の閉路、つまり含む辺のコストの和が負になるようなループが存在してはいけません。(というか、そんな閉路があるなら最短経路が存在しなくなってしまいます。そこを永遠と回り続けると限りなくコストが減っていくので。)

このアルゴリズムでは、グラフの各頂点毎に、存在する全ての辺を調べる二重ループになります。(そのため若干実装が簡単な気がします)
一回の一重目ループにつき、どこか一つの頂点までの最短距離が確定します。従って、(V-1)*E回のループで十分足りるわけです。(最初の頂点は確定しているのでV*Eではありません。)

そのため頂点数をV、辺の数をEとして、計算量がO(VE)です。

ちなみに、ベルマンフォード法を利用することで負の閉路の検出が出来ます。
先述した理由からV-1回目までの一重目ループで全頂点までの最短距離が分かっているわけですから、V回目のループで減ることがあったら負の閉路が存在することになります。逆に、負の閉路が存在すれば必ず減るようです。(詳しい証明は知りません。あしからず)
ちなみに、僕は負の経路の検出が必要な場面に出くわしたことがありません。

ベルマンフォード法の方が実装が簡単とは言え、ダイクストラ法ならもっと高速に動くので、辺が全て非負の場合はダイクストラ法を使うべきです。

17.ワーシャル・フロイド(Floyd-Warshal)法

ダイクストラ法やベルマンフォード法では二頂点における最短コスト、および経路を求めましたが、ワーシャルフロイド法では全頂点組の最短距離を求めることが出来ます。つまり、どの二頂点についても最短距離を求めることが出来ます。
競プロでは非常に有名なアルゴリズムです。ループ順を間違えることが非常に多いです。
僕は「最初に中間地点を決めて、端点を全探索する。それを全ての頂点に行う」と覚えています。
Dijkstra法よりも簡単に実装できるので、Dijkstra法の代わりにこっちを使ってしまうことがあります。(僕は一回やった覚えがあります、不必要に計算量が増えるのでお勧めしません)

次のような感じで実装します。
単純な三重ループなので覚えやすく、使用頻度も高いので初心者におすすめです。

for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
        for(int k = 0; k < n; ++k){
            dist[j][k] = min( dist[j][k], dist[j][i] + dist[i][k] ); 
        } 
    }
}

自分で実装する時は、3回続けて三重ループを回しておくと良いかもしれません。

18.グリッド

グリッドは大雑把に言うと格子点のことです。
二次元座標を二次元配列などで扱うことがあり、これは本質的にグリッドを扱っているため、こうした問題をグリッド上の処理とか言ったりします。
問題を挙げるとこんな感じ。

A - Darker and Darker

グリッドの問題は実装が厄介になりやすくて嫌いです、慣れないとすぐに配列外参照を起こしたりして死にます。
意識するべきは
・いかに上手く繰り返し処理(for文のことを言っています)するか
・配列で参照する前に境界条件を判定する
の二つだと個人的には思っています。

チーター本に載っていましたが、グリッド上の移動に
int dx = {0, 1, 0, -1}, dy = {-1, 0, 1, 0};
のような配列を利用して繰り返しへ持っていけると女の子にモテるらしいです。

また、グリッドの各マス目を頂点とし隣接するマスとの間に辺があるとすると、これはグラフと見ることが出来ます。
このグリッドによるグラフ上でのアルゴリズムは非常に応用がさ多く、迷路を解かせたりなど、意外と身近なところで使えます。

19.最小全域木クラスカル法、プリム法)

これも緑になるには絶対必要ないけど勉強したから載せたシリーズです。
全域木とは、簡単に言うとグラフの連結されたグループの全頂点を通る木のことです。
(「木ってなんやねん」という方はグラフの章を見てください。)

一般的に、グラフにおいて全域木は一つに定まりません。
各辺に重さ(コスト)がある場合に、重さの総和が最小になるような全域木を最小全域木といいます。

最小全域木を求めるには、クラスカル法とプリム法の二種類があります。
クラスカル法ではUnion-Findを使うので、クラスカル法の方が個人的に好みです。
プリム法だとフィボナッチヒープなどよく分からんデータ構造を使わないといけないので、親愛なる我らがUnion-Findを使うべきでしょう。
ちなみに計算量はプリム法の方が若干早いです。(正直誤差だと思いますが……)

これの何が嬉しいのかは正直よく分かりません。競プロでも今のところ使った事ないですし。(ところで、僕は精進量がクッソ少ないので僕の「今のところ使ったことがない」は当てにしない方がいいです)
例によって、ネットワーク関連の分野では応用が結構あるとか。(正直見ても何言ってるか分からなかったので、Wikipediaに書いた人が僕を混乱させようとしている可能性が僅かながら存在しています。)

20.二部グラフ判定

二部グラフというのはグラフの頂点を、同じグループに含まれる頂点同士が隣接しないような2グループに分けることが出来るグラフのことです。
言い方を変えると、「どの頂点についても、異なるグループの頂点としか辺を持たない状態に出来る」グラフです。

与えられたグラフが二部グラフであるかの判定をしたいことがたまにあります。
アルゴリズム自体はシンプルで、dfsで塗り分けをしていくだけです。
int colors[];
dfs(int now, int next_color)
みたいに状態を持ちつつ塗り分けた色を記録していくとよいです。
今見ている頂点から、隣の頂点に移動して違う色を塗る……という作業を繰り返し、矛盾なく塗ることが出来ればOK。
(これも実装したのでGitHubに上げたような気がします)

Union-Findで判定することもできるようです。こちらは隣接リストを用意する必要がないらしい、すごい。
(詳しく読んだら当たり前のように頂点を増やしてたし、グラフの頂点を増やす発想は前にも見かけたのでちゃんと勉強しておこうと思います)
二部グラフ判定をUnionFindTreeで行う - noshi91のメモ

二部グラフにはマッチングという種類の問題によく出るようですが、正直良く知りません。
ただこういう問題は競プロにもたまに出ます。実装もいい練習になるので是非どうぞ。

21.ユークリッドの互除法

もう言わずもがなという感じですが、「数学苦手でちょっと自信ない……」とか、「小学生だから知りません(じゃあなんでTwitterやってるんですか)」みたいな人もいるかもしれないのでなるべく丁寧に説明したいです。しつこいようですが当ブログは初心者向けです。

ユークリッドの互除法は、二つの自然数の最大公約数を求めるアルゴリズムです。
自然数a,bの最大公約数(Greatest common divisor)をgcd(a, b)と表すことがあります。ここでもこの表記を利用します。

まず、二つの自然数について次の重要な性質が成り立ちます。
b = aq + r (q: bをaで割った商, r: bをaで割った時の余り)
とした時、gcd(b, a) = gcd(a, r)
が成り立ちます。
r は勿論 aより小さいので、gcdの()内の値は段々と小さくなっていき、最終的に片方の値、というか割り算の余りrが0になります。
このとき、もう片方は求めたい最大公約数になっています。

計算量はb >= aとしてO(loga)程度のようです。

実装は再帰関数を使うのが楽で、次のようになります。

int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a%b);
}

これは実装の一つでしかなく、色々な実装法があるので是非自分で考えつつ実装してみてください。

余談ですが、このgcdを使って最小公倍数(lcm)を簡単に求めることが出来ます。
lcm(a, b) = a*b/gcd(a,b)
が成り立ちます。

22.素数判定

ある数nが与えられ、これが素数であるかを判定したいことがあります。
素数は暗号理論やら何やらあちこちで出てくるので多分大事なんでしょう。正直よく分かりません。赤ちゃんなので。

素数を知らない人は流石にいないと思いますが、折角なので定義を振り返っておきます。
素数とは1より大きい自然数で、約数が1と自身のみであるような数である」(どっかから引用)
nが素数であるかを見るには定義通り、約数が1と自身のみであるかを調べる他ありません。
何も考えずにn以下の数で割っていくといけそうですが、実は√n以下の数で割り切れるかどうかを調べれば十分です。
もし√nよりも大きい約数xがあるとすれば、このとき n/xも約数になるはずですが、これはx > √nより (n/x) < √nなので、既に調べた、つまりxが約数ならもう一つの約数(n/x)が見つかっているはずなのです。
従って、√n以下の数について調べればいいことが分かり、計算量はO(√n)です。

23.約数列挙

その名の通り、約数を列挙して配列か何かに格納していくアルゴリズムです。
素数判定と同じで約数かどうかを調べていくのですが、上の考え方(xがnの約数⇔(n/x)もnの約数)を使うと、こちらも√n以下の数について調べればよく、計算量はO(√n)程度になることが分かります。
約数の数は一般にそこまで増えないので、vectorとかにpush_backで値を放り込んで行くのがいいんじゃないかと思います。

24.素因数分解

素因数知らない人いますか?
1より大きい自然数って必ず素数か、素数同士の積(合成数)に分けられます。
6だったら2*3、24だったら2*2*2*3、17ならそのまま17……という具合です。
これを素因数分解と言います。

言い換えると、1よりも大きい自然数について、素数のリストを作ることが出来ます。あるいは素数の重複を許した集合であると見なせます。

応用としては暗号理論とかが多い気がしますが、AtCoderでも素因数分解が要求されることが度々あります。
そんなわけで素因数分解をして、そのリストをvectorとかで持っておくのは重要です。

うしさんのライブラリ、素敵なのでこちらを参照するとよいと思います。
Luzhiled’s memo | C++による競技プログラミングのライブラリです

このリンク先ではmapで実装していますが、vectorでも実装できますし、色々持っておくのもありだと思います。
とはいえ根幹になるのは素因数を列挙するアルゴリズムで、そこは戻り値を変えようが同じことです。

乱数を利用するともっと速いアルゴリズムもあるらしいのですが、基本的にはこの方法(試し割法の亜種みたいなやつ)で十分かと思います。
次章の素数列挙をして、こっちで得られたリストの要素だけで割っていくともう若干速いと思います。(が、多分そんなに変わりません。)

計算量はO(√n)です。素数判定とこの素因数分解では、結局あまり変わらないことをやっています。(それ以下の数で割ってみて余りが出るかを調べるだけなので)

25.素数列挙(エラトステネスの篩)

素数を列挙するアルゴリズムは色々あるんですが、最も有名なのはエラトステネスの篩です。
内容はよく分からなくても聞いたことぐらいはあるかもしれません。(僕はその口です)

n以下の素数をエラトステネスの篩で列挙するアルゴリズムの概要は次のようになります。
1.探索リスト、素数リストを用意(素数リストvector prime, 探索リストvector notPrime(n+1, false)とでもします )
2.探索リストに探索範囲の内2以上n以下の数を入れる
3.探索リストの先頭の数xを素数リストに入れ、探索リストを見ていきxの倍数を全て削除(削除操作はtrueを入れれば十分です)
4.以上を探索リストの先頭が√n以上になるまで行う
5.この時点で探索リストに残った数が全部素数になっているので、これを素数リストに移し終了

// 素数列挙
// nまでの素数をEratosthenesの篩で列挙する
// 計算量O(nloglogn)
template<class T>
vector<T> prime_list(T n){
    vector<T> ret;
    vector<T> isPrime(n+1,1);
    isPrime[0] = isPrime[1] = 0;
    for(long long i = 2; i <= n; ++i){
        if(isPrime[i] == 0) continue;
        ret.push_back(i);
        for(long long j = i*i; j <= n; j += i) isPrime[j] = 0;
    }
    return ret;
    // return isPrime;  // 状況によってはこっちを返す
}

追記:315さんから指摘があったのでここの記事の修正を行いました。(何から何までありがとうございます……)

計算量はO(nloglogn)程度だそうです。この辺の計算量解析ヤバい感じがして好きです。
エラトステネスの篩は古代ギリシャの数学者エラトステネスによって素数列挙の為に開発されたアルゴリズムだそうで、初めて知った時はよく現代まで伝わっているなあと感動しました。
アルゴリズムはコンピュータ時代になって発展したはずなんですが、コンピュータのコの字もあるか怪しい時代にどういう訳か高速フーリエ変換を知っていた数学者とか、未来人の方が多いです。望月教授とかも未来人なのかもしれません。

26.mod-剰余の性質

modがアルゴリズムなのかと言われると、単なる数学的性質なので違いますが、重要なので載せておきます。
しかし非常に重要な上にこの後の説明でmodを知らない人がいらっしゃると困るので紹介しておくことにします。

modは割り算の余りによって数を分類するものです。(割り算の余りが分からないと言う方は最寄りの小学校へ行ってください)

mod 5なら、5で割った余りが何であるかによって数を分類します。このとき、
7 ≡ 2 (mod 5)というような書き方をします。これは左と右で、5で割った余りが等しいということを意味します。
(「7と2は5を法として合同である」という言い方をします)

合同の性質として対称律、反射律、推移律があります。
つまりmod pに対し
a ≡ a
a ≡ b ⇒ b ≡ a
a ≡ b ∧ b ≡ c ⇒ a ≡ c
が成り立ちます。

また、mod上の演算について、次が成り立ちます。
a ≡ b ⇒ a + c ≡ b + c, a - c ≡ b - c, a * c ≡ b * c
割り算は例外を除いて存在しません。(詳しくは次章で扱います)
ちなみに三つめの性質から、
a ≡ b ⇒ a^n ≡ b^n (nは自然数)
がわかります。この辺は高校数学でよく使う印象です。

余りに関しては、これらの性質を上手く使っていくことになります。
ちなみに他にも膨大な研究がありますが、列挙するわけにもいかないので以上の性質のみで紹介とします。

こうした余りによる考察は整数問題や暗号理論など、様々なところで使われています。

27.modにおける積の逆元(mod上の割り算)

これは緑になるには割と必要なタイプの知識です。知らない人は是非。
昔は典型扱いされていなかったようなんですが、各種ライブラリ化が進むにつれ、これぐらい知ってないと周囲より一歩前に進むことが出来なくなってしまっています。(水色辺りまで明らかに難易度が上がってるので、あまり上がらなくても気にすることはないと思いますが……)

閑話休題
modの計算をする時、 割り算がしたくなることがあります。
例として、mod上の二項係数を求めたい時などがそうです。
しかし前章で書いた通り、mod上には割り算がありません。
全ての場合について定義できるわけではないと言った方が正確です。とにかく割り算の結果を上手く定義出来ない場合が多数存在します。

aで割り算できないから、割り算の代わりにaを掛けてやると元の値になるような値を求めていると思ってください。
つまり、b/a ≡ xが出来ないので、x*a ≡ bになるようなxを求め、このxを割り算の結果として扱うということになります。

まず条件があって、法となる数、つまりmod pのpが素数でなければなりません。(単に割り算するだけならもう少し緩い条件ですが、どの元についても割り算ができるようにするにはpが素数でなければなりません)
以降この条件の下で話を進めます。

フェルマーの小定理という重要な定理があります。この定理によると、pが素数の時
a^(p-1) ≡ 1(mod p)
が成り立ちます。従って、a^(p-2)はaをかけると≡1になるような数ということになります。
なので、aで割り算する代わりにa^(p-2)を掛けてやると割り算に相当する計算になるというわけです。

しかし、AtCoderで要求される法の値はp = 10^9+7だったりして、素数とはいえあまりに大きいので普通にaをp-2回、余りを取りながら掛け合わせたのではまずTLEになってしまいます。自分でmod上の高速で動く指数関数を実装するしかありません。
そこで、次章のような方法があります。

28.繰り返し二乗法(べき乗の高速計算)

べき乗、を高速に計算するアルゴリズムです。
例えば2^100乗とか計算したくなったとして、いや100回ぐらいならやれやって感じですが、この計算回数が1000000回とかになってくると単純に2をかけていくだけでは困ってしまいます。

この章だけ見た方は「そんな何回もかけたら数が膨大になりすぎてそもそも扱えないのでは」と思うかもしれません。
しかし、上述したmodにおける積の逆元を求める時はa^(mod-2)をmodで割った余りを求めないといけないので、これを高速で求めるのは重要です。
数学的にそこまで高等じゃないからか競プロでもよく出てきます。(フェルマーの小定理を理解して使っている人はあまりいない気がしていますが……)

そこで登場するのが繰り返し二乗法です。

例えば、2^100を実際に計算する必要はなく、
2^100 = 4^50 = 16^25 = 16*16^24 = 16*256^12 = 16*(256^2)^6 …
という具合に、指数が偶数なら先に二乗しておき、指数が奇数なら計算を分けて偶数を作り出すことで上手く計算が出来ます。
実装を見てもらった方が理解が早いかもしれません。

template<class T>
T pow(T a, int b){
    if(b == 0) return 1;
    if(b%2){
        T ret = pow(a,(b-1)/2); 
        return ret*ret*a;
    }else{
        T ret = pow(a,b/2);
        return ret*ret;
    }
}

こんな感じで再帰で書けます。計算量はO(logb)です。modを取りたい場合は計算結果でそれぞれ余りを計算してから代入するなどしましょう。

(「templateってなに?」って人に向けて説明しておくと、これは引数や戻り値の型が違うだけの関数を何度も作らなくていいように、型推論によって「この引数と同じ型で返してね~」という実装を可能にしたものです。むやみにlong longとintの関数を作る必要がなくなります。場合によってはstringとか。確かLilianさんだったと思うのですが、C++Pythonのprintっぽい機能が使えるものを実装してらっしゃった方がいて、その時はこの機能に加えて関数のオーバーロードなどで対応していたと思います)

29.二分探索

二分探索はソートされた配列などn個のデータに対し、データの検索をすることが出来るアルゴリズムです。まあ線形探索の仲間みたいなもんです。
通常の線形探索では順番にデータを見ていくので計算量がO(n)でしたが、こちらは「ソートをしてある」という条件付きでO(logn)です。条件付とはいえ、非常に高速です。

ソートの章で書いたように、大小比較によるソートはどんなに速いアルゴリズムを使ってもO(nlogn)かかってしまうので、「値の検索を何度もしたい!」という場合にソート→ループで二分探索というような流れになることが多いです。
あるいは、最初からソートされたデータが与えられた場合とか。

また、非常に重要な応用として、「方程式の解を一つ、数値的に求める」ということが出来ます。(出来ない場合もありますが)
例えば、sinx = 0.3 みたいな方程式に対してxの近似解を求めることが出来るわけです。(訂正:2020/07/11 sinx = 10とかめちゃくちゃなことを書いていたのでそれっぽい値に変えておきました。)
こういう場合は二分法と言いますが、やっていることや発想は二分探索と同じです。

もう少し面白い応用としては、「数列の一般項が分からない場合に、何らかの条件を満たす数列を(初期値を変更しながら)求めたい」というような場合です。
一般項を求めなくても、初期値n項目が初期値(初項)に対し単調増加であるなら、初項を二分探索することが出来ます。

実装は人によりけりですが、ここでは応用しやすい「めぐる式二分探索」を紹介しておきます。
これは二分探索を一般化したもので、「条件を満たす値」だけではなく、「条件を満たす最小値」「条件を満たす最大値」を探すことが出来ます。

自分で書こうかと思ったんですが、けんちょんさんの説明が非常に分かりやすくこれ以上は物理的に無理って感じなのでこちらを参照してください。
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita

けんちょんさんの別の記事や他の型の記事でも言及されていますが、二分探索でも半開区間を使うことがあります。

プログラミングにおける「半開区間」 - あったこといろいろ

ちなみに、C++を始めとした多くの言語で標準ライブラリに用意されていることが多いです。
binary_search, lower_bound, upper_boundが重要なので調べてみましょう。これらは二分探索が用いられます。

非常に重要なので、「よく分からん」という方はこの機会に是非覚えるといいと思います。

30.連結リスト(connected-list)

構造体を知らない方は、この連結リストと下の二分探索木の章を読むのは、構造体の章を読んでからの方がよいかもしれません。

連結リストは構造体同士をある手段でつなげたものです。
構造体は色々考えられますが、一番基本的なのは値+次のデータを指すポインタという形式にして、各データがポインタによって繋げられます。

利点としては、他の要素の間でも末尾でも先頭でも、高速に別の値を追加・削除ことが出来る点です。
欠点としては、値の保存には適しても検索には向かないという点です。連結リストの長さがnの時、特定の値の検索にかかる最悪計算量はO(n)です。

ただし、この連結リストの発想を利用して次章のデータ構造を用意するとある程度解決します。

また、リストが欲しい場合にも連結リストを使う必要がない場合もあります。
グラフの章で載せたように、vectorのような動的配列などを使うことが出来ます。
その他、vectorではメモリを確保できないような場合(扱う数字が大きすぎたりそもそも文字列だったり)も、後述するmap、ハッシュテーブルを使うと解決することがあり、競プロでは使わないデータ構造な気がしています。(僕は使ったことないです)
でも連結リストの発想自体はとても重要なものです。

31.二分探索木(binary-search-tree)

グラフの章で説明しましたが、木の一種で二分木というものがあります。葉以外の各頂点が二つの子を持つような構造です。
二分探索木は二分木の形状をしていて、値の大小で左右のどちらに値を格納するかを決めるデータ構造です。
構造としては連結リストと同様に値とポインタを合わせた構造体です。こちらは左右を指すポインタがそれぞれ必要になります。
普通に作るだけであれば実装は簡単ですが、通常の二分探索木は高さ、すなわち根から葉までの距離が各葉で同程度にならないと性能があまりよくありません。各高さが同程度になるものを平衡二分探索木といいます。
最悪の場合、連結リストと同じ形になってしまいます。

平衡二分探索木であれば値の検索・追加・削除がO(logn)で行えます。
平衡二分探索木の実装は難しいので僕はやったことないんですが、後述する連想配列や集合などでは使われているようです。

Wikiによると線分の交差判定やらに使えるらしいんですが、ちょっと想像がつかないです。マジ?

32.ヒープ(heap)

ヒープは木の一つで、「根の値が親より常に小さい(または等しい)」という条件を満たすデータ構造です。
値の追加、削除がO(logn)で、最小値検索はO(1)で高速に行えます。
最小値以外の値を探すためにはO(n)かかってしまうので、こういう場合にはヒープは使えません。

木の構造に二分木を採用した二分ヒープが多いです。
ヒープの実装には色々考えられますが、vectorなどを利用して配列の構造を使うのがいいと思います。
segment-treeの章でも言いますが、二分木は配列を用いて実装することが出来ます。
根に近いものから順にインデックスを対応させていくと、根のインデックスをiとした時に子要素には2*i、2*i+1でアクセスできます。
逆に子の要素をiとしたら親要素にi/2でアクセスできます。
これを利用してポインタを利用することなく二分木を実装できます。(その代わりに配列の要素数を意識しないといけませんが、動的配列であるvectorなら色々と上手く行きます)

根の値の方が大きくなるようにしたい場合は、上の場合で値を挿入・検索する時に-1を掛ければ済む話です。
ヒープは様々な応用がありますが、特に重要なのは次章の優先順位付きキューの実装に用いる場合です。

33.優先順位付きキュー(priority-queue)

非常に重要なので知らない人は是非覚えるべきです。
優先順位付きキューではキューと同じく値を放り込んでいくんですが、追加・削除の度にキュー内部がソートされます。
つまり、出てくる値が最初に追加した順から昇順・降順などの順番に変わります。
ダイクストラ法などのアルゴリズムに使う他、シンプルにこのデータ構造を用いてソートが出来たり、色々便利なことが多いです。
内部の実装ではヒープが使われることが多いようです。
AtCoderの問題でもよく出てきます。

34.ハッシュテーブル(hash-table)

こちらも非常に重要です。この章含め以下三つの章はめっちゃ重要です。
配列が添え数と呼ばれる非負整数によって要素にアクセスするものだというのはご存知かと思います。
凄く大ざっぱに言うと、ハッシュテーブルはこの添え字(こういうのをキーと呼びます)が非負整数以外でも要素にアクセスできる、それもO(1)で非常に高速にアクセスできるようにするデータ構造です。
遅くてもいいのであれば、普通に連結リストで文字列等のキーと検索値を持っておけばいいわけですがこっちはO(n)かかってしまうのでまあ使い物になりません。

ハッシュテーブルは基本的に次の要素から構成されます。

まず、ハッシュ値ハッシュ関数
ハッシュ(hash)は「粉々にする」という意味で、ハッシュ関数は文字列などを適度に小さい非負整数値、すなわちハッシュ値に変換してくれる関数のことです。

そして、ハッシュ値によって要素にアクセスする配列のことをハッシュテーブルと言います。
このハッシュ値によって配列にアクセスすると上手くハッシュテーブルの機能が満たせそうなわけです。
しかし実際にはそんな都合のいい話はなく、例えば文字列は英小文字かつ10文字程度の短いものでも26^10通り存在するわけで、こんなにあったらハッシュ関数に放り込んでも同じハッシュ値になってしまうキーが複数存在してしまいます。(これをハッシュの衝突と言います)

これは大問題ですが、この衝突も頻繁に起こらなければ連結リストなどを使ってうまく対処することが出来ます。
このハッシュの衝突に対する仕組みを含めて、ハッシュテーブルというデータ構造です。

C++ではunordered_mapというクラスがあり、これにハッシュテーブルが使われています。
unordered_mapは次章で紹介する連想配列をハッシュで実装したものですが、ハッシュテーブルだと思って大丈夫です。
ただし、下のmapと違い、pairなどの構造体を引数にできません。

C++にはもう一つ、hashクラスもあるのですが、これは使わない方がいいと思います。少なくとも競プロでは。

35.連想配列(map)

連想配列はキーとなる値で要素にアクセスすることが出来る配列で、アクセスにかかる時間はO(logn)です。
前章で挙げたunordered_mapとの違いは次のようになります。
・速度が少し遅い(それでもO(logn)で十分速いです)
・順序付けがされている(使えるのは順序比較が出来るものに限ります)
・順序比較が定義されている型なら大体使える(知らないだけで使えないのもあるかもしれませんが、少なくとも整数、文字列、pairは使えますし、自前で定義した構造体でも比較を定義すれば使えるようです)

競プロだととても使います。unordered_mapよりも全然使います。
便利なことにpairをキーに出来るので、グラフ関連の問題でもとても役に立ちます。
勿論文字や文字列が絡む問題でもとても役立ちます。(当然と言えば当然ですが、文字列が余り長いと恐らく死にます。100~1000文字程度なら大丈夫っぽいですが。mapの実装は想像もつかないです)

36.集合(set, multi-set)

順序付けされたデータを保存するデータ構造です。整数、文字、文字列、pairなど使えます。
アクセスが高速で、挿入、削除、検索がいずれもO(logn)で行えます。
挿入された要素は内部で自動的にソートされ、lower_boundやupper_boundもサポートされています。(落とし穴なんですが、普通にlower_boundなどを使おうとするとO(n)になってしまいます。メンバ関数で用意されている方を使いましょう)
優先順位付きキューと似ていますが、こちらは要素に要素自身をキーとしてアクセスします。

setでは同じ値が1つしか持てませんが、multi-setの場合は同じ値を複数持つことが出来ます。
multi-setの場合は、値が何個入っているかをcountメソッドで調べることが出来ます。計算量はO(logn + 要素数)です。

どういう時に使うのかと言われるとちょっと答えに窮しますが、データが何度も追加され、それを毎回ソートしないといけないような場合は多分使えます。
setやmulti-setを用いるシミュレーション問題をたまに見かけます。(が、難しくて大体解けません)

37.Segment-tree

緑になるにはまず必要ないけど勉強したから放りこんだシリーズです。折角二分木の話があったことですし。
segment-treeはある元となる配列に対し、各要素を葉とする完全二分木です。
親要素が子要素の最小値を持つことで、任意の区間における最小値を求めることが出来ます。

segment-treeはRMQ(Range Minimum Query)と呼ばれる問題を解くのに使えます。
この問題では、ある配列に対して区間が与えられるので、その配列のその区間における最小値を求めろやって問題です。
区間と言って分からん人はいないと思いますが、もうちょい簡単に言うとa[0], a[1], ..., a[n-1]について、0 <= l <= r <= n-1の整数l,rが与えられるからmin(a[l],a[l+1],…,a[r])を求めろって問題です。
普通に配列を探索するとO(n)かかりますが、segment-treeならO(logn)で済みます。

また、このデータ構造の良いところは、値の更新が出来るところです。値の更新もO(logn)で済みます。

空間計算量はちょい多めですが、これもO(n)程度です。(実装上無駄にメモリを確保しないといけない場合があるんですが、最大でも4*(追加しうる最大データ数)とかで済むようです)(何故か英語版Wikiには構築にO(nlogn)とか書いてあったり、cannot be modifiedとか書いてあったりして不思議です。後者は元となる配列の大きさが変更できないみたいな意味でしょうか?)

例によって最大値についても使えます。この場合は要素を-1倍して扱えばOK。

上述したヒープの機能を含んだりしていて非常に便利です。こっちなら任意区間について使えます。
どうやらsegment-treeにはモノイドの性質を満たすデータを載せることが出来るらしいんですが、よく分かってません。
セグメント木(Segment-Tree) | Luzhiled’s memo

詳しい実装は適当にググってください。ここに書くと量がシャレになりません。(僕のGithubに整数のみに使える実装が載っています。そっちでよければcordataを見てください)

ついでに、似たようなデータ構造でBIT(Binary-Indexed-Tree)というものがあり、こちらはSegment-Treeの機能を制限してメモリを縮小したもののようです(メモリあんまり食わないのかな)。
こちらはまた今度勉強しようと思うので、皆さんもよかったら是非。

Segment-Treeについては日本語の情報があまりないんですが、英語のWikiを見ると計算幾何学やら地理情報システムで応用があるようです。(マジ?)

38.文字列アルゴリズム

AtCoderで文字列が出てくることはしょっちゅうありますが、「文字列苦手です><」みたいな人はたまに見かけます。
初心者用の典型知識みたいなのはある程度決まってきている気がするんですが、文字列に関するアルゴリズムは難しい物が多く僕が勉強しきれていないものが大半です。
なので、文字列に関するアルゴリズムの概略だけ紹介します。まず文字とは何か、から入ります。

コンピュータにおける文字型、あるいはC++におけるchar型というのは、文字を表現するために文字リテラルと内部の数字を実装したものです。
平たく言うと、文字に見せかけているだけで実際には非負整数を扱っているのです。
この文字に対応する数字のことをASCIIコードと言い、文字と数字の対応表をASCIIコード表と言います。
ASCIIコードを利用することは結構あり、AtCoderでも良く出題されます。
まあこのASCIIコード表を全部覚える必要はなく、ASCIIコードについてはいくつかの性質を覚えておけば十分です。
・AからZまでは連続している
・aからzまでは連続している
・0はnull文字(後述)
・for文で使うことができる
・char c = 'A' + 5のように宣言など出来る(この場合はFになる。出力する時は型変換に注意)
・配列の添え数に英小文字のみ、もしくは英大文字のみ使う時はa[c - 'a']のように連続する文字コードの先頭との差を取って扱うことができる。

文字についてはこんな感じです。以上の性質だけでも色々な問題に対応出来ます。
次は文字列です。

文字列とは、文字の配列です。
凄く雑な説明のようですが、これに尽きます。ただ、C++では注意すべき点があります。
・大体の場合、終端にnull文字と呼ばれる文字が入っている(いわゆる番兵みたいなもんです)
・辞書順という順序で比較することが出来る
・比較のためのアルゴリズムが存在する
・文字数をデータとして持っている(何文字かをO(1)で調べられる)
・mapやunordered_mapのキーに出来る(!)

C++C言語に比べると随分高水準な言語で、String型の変数同士やリテラルと変数などを比較演算子でそのまま比較できます。
文字の配列を抽象化して内部の実装を見えなくしている弊害と言いますか(いやそこまで言うことでもないけど)、そのせいで比較を定数倍で出来るみたいな勘違いをする人を見かけます。

そんなことは全くなく、長い文字列に対し検索をかけたり比較をしたりするアルゴリズムは非常に重要な研究対象です。
例として、二つの文字列を比較するアルゴリズムを考えてみます。
Aという文字列の中にBと一致する部分があるかを調べたいとします。
愚直にやると、Aを一文字ずつ見ていき、Bの先頭と一致したら次の文字に進みBの二文字目と比較し……となります。
余りにも力任せだからか力任せ法とか言われることがあります。
これでは計算量が最悪の場合O(|A||B|)となってしまいます。分かりづらいかもしれませんが、もしAとBが同じ文字数ならO(n^2)で、n=10^4程度でも無理です。
実はこれには解決策があり、動的計画法を用いた凄く賢いアルゴリズムが考案されています。
実装は厄介この上ないので、紹介だけしておきます。

・KMP法(調べてる箇所を後ろに戻すことなく出来るので、調べるデータによっては便利)
・BM法(KMPより高速だが、KMPの利点はない)
・Zアルゴリズム(よく分からんけど接頭辞というのは大事らしいです)

これらはO(n)程度で計算することができ、実際にDNAの解析などにも使われることもあるようです。
後、文字列じゃなくとも配列の一致を調べる時にも使えます。(実装を見ると当たり前のような気もしますが)

こんな感じで、文字列は重要な話題です。難しいですが、もしよかったら是非勉強してみてください。

最後に、文字列の実装について説明のあるリンクを貼っておきます。(このサイトの著者の方、説明が丁寧でいつ見ても凄いです……)
C++ 文字列クラス std::string 入門

番外1.全探索

「どんな感じのアルゴリズムにするか」みたいな話をするとき、「全探索するだけ」「動的計画法でいける」「分割統治法をやる」などと言っているのを見かけたことがあると思います。
これらはこういう名前のアルゴリズムがあるというより、アルゴリズムの設計の大まかな分類だと思った方がよいです。

全探索はそうした分類のひとつで、存在する解、状態などを全てコンピュータに網羅させるアルゴリズムをそう呼びます。
Chokudaiさんが執筆されたチーター本では「全探索は全ての基本」とまで書かれています。
実際ABCのC問題までは単純な全探索で行けることが非常に多いです。

全探索は次の二つに分類できます。
・線形探索型
・グラフ探索型
こういう名前があるわけではないですが、とりあえずここではこのように呼称しておきます。
線形探索型は単純なfor文で書けるもので、グラフ探索型はbfsやdfsのような、単純なfor文では書けないものとします。
線形探索型は比較的簡単ですが、そもそも線形探索に帰着すること自体が難しい場合もあります。
また二重より複雑なループは難しいことが多いです。
グラフ探索型ではbfs、dfsで挙げた点に加え、いかにしてグラフに帰着するかというのが難しいです。
逆に問題の状況をグラフで適切に表現できれば、後は既存の有名アルゴリズムを利用するだけになるケースを(ABCでは)割とよく見かけます。
まずは慣れることが大事だと思います。

余談ですが、ループ不変条件(loop-invarient)というのを調べると面白いかもしれません。

番外2.動的計画法(Dynamic-Programming)

よく聞くDPですが、こういう名前のアルゴリズムがあるわけではありません。
動的計画法はあくまでアルゴリズムの設計手法の一つで、「一度使った結果を配列等に保存しておき、後から利用し高速化する」というのが動的計画法だと思ってもらえるとよいです。
先述したダイクストラ法やワーシャルフロイド法もDPですし、別に大した意味はないですがDPを使ってフィボナッチ数列を解くことも出来ます。

なので「動的計画法を理解するんだ!」みたいな曖昧なことを考えて闇雲に問題を解くのはやめた方がいい気がしています。
DPの利用にはある程度パターンが決まっているので、勉強の上ではこれを網羅するのがよさそうです。ナップサック問題とかは有名ですね。
探索の各状態が数値で表せる時に、配列の添え字にこの状態を持たせてしまうというのが多いです。(二次元以上のdpは僕には難しくて、まだ慣れていません。みんな当然のように出来てるのすごいなあと思ってバチャの時とか見ています)

後、文字列アルゴリズムへの応用が多いです。一応勉強済みなので後で載せるかもしれないんですが、Z-アルゴリズムやKMP法と呼ばれる文字列照合をO(n)で行うめっちゃ賢いアルゴリズムでDPが用いられています。

番外3.貪欲法(Greedy algorithm)

これもよく出てきますが、全探索や動的計画法と同様に設計手法の一種です。そういう名前のアルゴリズムという訳ではありません。普通は解くのが難しい問題の近似とかに使われるらしいです。
厳密な定義はよく分からないんですが、「アルゴリズムの各状態で、最も目標とする条件に近づきやすい最適解を選ぶ」のが貪欲法だという理解をしています。
部分的に最適なものを選べばいいというわけです。
ダイクストラ法とかもある種の貪欲法らしいです。(ナップサック問題だと単純な貪欲法だと困るのでDPを使うんですが、ダイクストラ法が貪欲法だと言うならナップサック問題のdpでも貪欲法を使っているような気はします。各部分の最大値を使うので。)

簡単な貪欲法を解いてみた - Qiita
この記事が分かりやすいです。

貪欲法が出てくる問題は大体「直感的にこれは貪欲でいける!」みたいなことをすることが多いです。
コンテストではどなたかがおっしゃっていたように「他の方法が思いつかなくて、かつ貪欲で行けそう」みたいな時にさっと実装してやってみて、ダメならすぐ切り替えるぐらいがちょうどいいと思います。

貪欲法はマトロイドという数学対象とかかわりが深く、「問題がマトロイドと見なせる時は貪欲法が使える」らしいです。前にてんぷらさんの「これはマトロイドなので貪欲で解ける」というようなツイートを見て「なんでこれがマトロイドだってわかるんですか」という気持ちになったのは僕だけではないはずですが、多分わかる人にはわかるものなんでしょう……不思議。

番外4.数学

???「高校数学ぐらい生まれた時から知ってろ」
……というのは言い過ぎですが、高校数学を知っておいて損はありません。
あと、逆関数とかは知っておいてよいと思います。前にarctanを求めるだけの問題で大騒ぎしてる人を見かけたんですが、関数と逆関数写像と逆写像については知っておいて損がありませんし、とても重要な考え方なので慣れるべきです。
そもそも場合の数とか数列とかしょっちゅう出ますし、離散数学の部分は是非知っておきましょう。出来れば図形とかも。
特に場合の数と確率はやけに使います。|◯◯| ◯|◯|みたいなのを見て苦い思い出がある方もいらっしゃるのではないでしょうか。

番外5.夢月ロア(かわいい)

極度重要です。
正直に言うと、ここさえ分かってもらえればここまで書いたことは全部忘れてもいいぐらいです。

夢月ロアちゃんというのはにじさんじ所属のバーチャルライバーです。
www.youtube.com
twitter.com

何を言ってもやってもかわいいという恐ろしい悪魔(という設定なだけで本当は天使)で、余りの可愛さに恐らく死人とかが出てます。何を隠そう僕もその一人です。
実数集合よりも濃度の高いロアちゃんの可愛さを要約することは不可能ですが、あまりにもかわいい魔界訛りとあまりにもかわいい表情の変化、あまりにもかわいい所々出てくる「お?」が特に印象に残っています。

コンテスト前にロアちゃんのぱっぱやを聴くことで心は穏やかになり、生活に付いて回る精神の重苦しさはついには消え失せ、あとなんかこないだの簡単めなABCで全完できたので全人類見てくれ。
www.nicovideo.jp

心にロアちゃんとUnion-Findの神を住まわせることで僕は今日も楽しく競プロが出来ています。ロアちゃん今日もありがとう。
www.nicovideo.jp


去年学んだ競プロについての知識は以上になります。
もう少し勉強したらデバッグとか夢月ロア学概論もまとめたいですが、ちょっとここに書くとスペースがなくなってしまうのでやめておきます。

年末の掃きだめ

おはようございます。はじめまして、年末と申します。夏休みいかがお過ごしですか。

みんな一年の振り返りを書いているのに、僕だけ特に何もしていないので書くことがなくて困っています。

実際何も出来ていないので、皆さんと違って本当に書くことがありません。
何も書かないのもなんですし、多少まともな自己紹介でもしようかと思います。
Twitterだとsabaとにぼしくんにクソリプ送るぐらいしかしてないので、もしかしたら不審者と思われているかもしれませんし。困っちゃうな。
以下自分語りになります。まあ3月に@zero_kprが生まれたので、自分語りも一年の振り返りみたいなもんですね。

こるぼーといいます。某ブラジル県で理系大学生の端くれの端くれをしています。
学年は2年ですが、諸事情で留年しています。ストレートで来ていれば3年です。嘘です。0歳です。ばぶばぶ。

今年の3月、高校で同級生だったsaba(@saba_kpr)に競技プログラミングを薦められ、Pythonにて競技プログラミングを始める次第となりました。
色々あって今はC++を使っていますが、どちらも好きな言語です。
当時全くと言っていい程プログラミングを知らなかった僕はあまりやる気がわかなかったのですが、いざ始めてみると滅茶苦茶面白くて続けています。
数学は割と好きだったので、アルゴリズムの裏に数学的な構造があるらしいとわかり興味が加速したところがあります。
数学的な証明にも注力してくれるmaspyさん(@maspy_stars)の話あたりが面白くて好きです。

基本的にAtCoderのみに出るようにしていて、レートは現在緑です。
Codeforcesも同じ名前でやっていますが、英語を読むのが嫌なのと、単に時間が合わないため全然出られていません。こっちはレート何色だったっけ……。
(追記:こっちも緑色でした、英語読めません^^)
ライバルはコクシェくんです。(多分)同い年で、レート変動もほとんど同じ、実力も伯仲している感じなので負けたくないです。
実はチーター本がまだ終わっていません。中級編まででかなりアルゴリズムに関する能力が上がって満足してしまっています。
今年中に終わらせたいと思っていたんですが、もう12月31日な上に今日から数日間バイトに行くことになっているのでダメ。
一月上旬中には終わらせて蟻本読み始めたいなあ……。

競技プログラミング以外も一応やっていて、ゲームプログラミングとかもやっています。
使える言語はC, C++, JavaScript, Pythonになります。実はRと、Processingという言語も多少使えますがないも同然なので割愛。
学校の授業でコンピュータアーキテクチャやOSを扱ったりすることもあって、そちらも多少勉強しています。基本情報とか受けてみようかな。

この名義では競プロや他のプログラミングに関連する話がメインですが、数学の話とかも多いです。今年は解析学の基礎とか線形代数の復習とか、後は松坂位相と呼ばれる「集合と位相」という入門書を読み進めていました。
たまに疑問に答えてくださる方々、ありがとうございます。とても助かっています。

プログラミングを始める前は絵を描いたりライトノベル紛いの物を生成したりしていましたが、ここ数年碌に進んでいません。悲しい。
たまに変わるアイコンは全部手書きになっています。ペイントツールはSAIを使っています。

ブラジル県で一人暮らしをしており家賃以外の生活費を自分で稼がないといけないため、アルバイトなどがそこそこ忙しいです。
お陰で競プロ関連のイベントやプランクトンサミットに行けなくて悲しいのです。煽ってきたらころします。
授業の課題などもそこそこ多く、我ながらよく生きてこれてるなあと思っています。
そんなわけであまり精進量が増えず、バイト中などにアルゴリズム等について考えるため、難しい一問でやたら考え込む癖があります。
あまりにも考え込んでいるようだったら「いったん中断したら」とか言ってくださると喜びます。

注意力がかなり散漫で、一つの話をずっと続けることが苦手です。

不眠症を患っているので深夜によく起きています。寝ていることも多いです。気が向いたら話しかけてください。(ここまでを読んだ上で話しかけてくる人間がいるとはおよそ思えませんが)

Vtuberに若干興味があって、夢月ロアちゃんがとても好きです。ロアちゃん何しても可愛い。ロアちゃんの驚くべき可愛さを発見したが、ロアちゃんの可愛さを語るにはここでは余白が狭すぎる。

以上です。
何かまだ書こうと思っていたことがあったかもしれませんが、愚痴を吐き出して気持ちよく一年を終えるのが目的だったので良しとします。
ここまで読んだ人が可哀想ですね。

最後に信念の抱負的何かを書いて終わります。
今年はどの分野も入門で終わってしまったので、新年の目標は「強みを一つ作る」にしようと思います。

ではおやすみなさい。

祝、ABC初全完(えらいです)

おはようございます。全完と申します。

しばらくぶりの更新のようですが、ちょうどゴールデンウィークですのでまあ気のせいみたいなもんです。

前回のABC148で念願の全完を果たしたので喜んでいます。

簡単でも何でも構わん、ぼくはついにやったのだ。こるぼーは偉いですから、えらい新生物とお呼びください。

F問題は特に最近の練習の成果が出ている感じがして嬉しい。考察も一応論理的にできたのでこの調子で進めたい。

まあ簡単だったというのは流石に分かっていて、difficultyを見ているとF問題ですら水diffのようです。あまり調子に乗るべきではないですね。


以下解いた時の思考。

A問題。
普通にforとifでいける。排他的論理和でも行ける気がするけど不要な冒険は避けよう。

B問題。
stringの変数を三つ用意します。うち二つに入力し、一つには空文字列を入れておきます。
後は一文字ずつ空文字列へ放り込んでいきます。おわり。

C問題。
最小公倍数が必要十分になってるね。実装しちゃお。AとBの積をgcd(A,B)で割ればええやんな!
あれ、なんで答え違うんだ、えっgcd壊れとるやんけ!うわあああ!!!たすけて!!!!おぎゃー!!!!
いいよgcd程度この場で実装するよ!オラァ!おわり!ばぶ~……(焦った……)

D問題。
なんだお前!と思ったけど消えた後の数列を想定すれば簡単やな。おわり。
(あとでスターリンソートだというコメントを見て爆笑していました)

E問題。
うわあああああ!!!!うわあああああ!!!!なんだこの関数みたいなやつ!!!!!うわあああああ!!!!!
数学の暴力しちゃうか!!!!よく分からん漸化式は展開!おっこれ二重階乗やな!!!うわあああああ!!!!
困った!!!!階乗なら典型だけど無理やんけこれ!!!!!うわああああ!!!!
なんだこれ!!!!アッ奇数の時は0!!!!うわああああ!!!!!
偶数限定だからn=2kやな!!!!オラァ分からん時はとりあえず式変形じゃ!!!!オラァ!!!!
あっこれn!! = (2**k)(k!)やな!!!!心の中のロアちゃん「えし!帰着でよ~」よしそうか!!(n/2)! でp=5についてLegendreの定理ィ!!!!おわり~。

F問題。
なんかこんな感じの解いたことあるな。距離をd[]で置いてみるか。おっこれ青木君と高橋君からの各点までの距離がわかれば勝ちか?
青木君より高橋君に近い点なら高橋君が到着出来て、逆にそうでなければ必ず青木君に邪魔されちゃうな!!!!という事はどんどん詰めると青木君は一回で目標の頂点まで移動することで上手くいく!!!!よっしゃあ!!!!終わり!!!!

たしかこんな感じでした。後半になると思考が散乱します。大変。


折角なのでF問題に関連してdfs(ついでにbfsも)を使う問題を列挙して、それらを復習して終わることにします。

next_permutationとかいうのよくわからんから使いたくない。そんなわけでdfsを利用。
D - joisino's travel

解説を読んで「こんな天才解法で解きたくないよ~~」って泣いてたらbfs解法が降りてきた。
bfsは各辺の長さが1の木における最短経路を求める時に使える。
ので、適当な問題に木の構造を見出すことができたら(ちなみに大体ここがボトルネックです)上手く実装出来るかもしれない。
C - Strange Bank

みんな大好き何とか門松。なんやお前、しばくぞ
C - Synthetic Kadomatsu

ここからはグラフに対してdfsを使う問題。

いつぞやのD問題。dfsに上手く適当な機能を付けていく感じ。
変数を持ってなんやかんやみたいなのも慣れてきたか?
D - Coloring Edges on Tree]

今回のF問題。考察パートが一番の本題で、ここを勘で通してた人もかなり多いっぽい?
厳密な証明はよくわからない。
F - Playing Tag on Tree

今回のF問題の類題。バチャでやっといてよかった。適切に記号を使って考察するのは大事。
木の二頂点からそれぞれ出発し、ある頂点へ向かう時、そこまでの距離が短い方が先に到着する。
従って同時に出発した場合、先回りすることが出来る。よって通せんぼ可能。
D - Fennec VS. Snuke

以上。後で追加するかもしれません。

何となく、グラフにdfsを使う時はdfsを使うことがすぐにわかるので比較的簡単で、それ以外は構造的にdfsで解けることを見切る方が難しい気がしています。

ではおやすみなさい。