ロアちゃんかわいい

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

チーター本の感想

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

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

チーター本、何

チーター本、正式には『最強最速アルゴリズマー養成講座 -プログラミングコンテスト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 = 10みたいな方程式に対してxの近似解を求めることが出来るわけです。
こういう場合は二分法と言いますが、やっていることや発想は二分探索と同じです。

もう少し面白い応用としては、「数列の一般項が分からない場合に、何らかの条件を満たす数列を(初期値を変更しながら)求めたい」というような場合です。
一般項を求めなくても、初期値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程度でも無理です。
実はこれには解決策があり、動的計画法を用いた凄く賢いアルゴリズムが考案されています。
実装は厄介この上ないので、紹介だけしておきます。

・KNP法(調べてる箇所を後ろに戻すことなく出来るので、調べるデータによっては便利)
・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で解けることを見切る方が難しい気がしています。

ではおやすみなさい。

Union-Findの利用?

おはようございます。進捗ダメすぎて死にました。この文章は私の思考をトレースしたAIが書いています。

このブログには一応、「プログラミング未経験者がプログラミングをゼロから勉強していく過程を残そう!」みたいな健気な理念があった気がするんですが、なんかどこかへ行きました。不思議ですね。

いや記事を書くより勉強するスピードの方が早いので仕方ないですね(笑)(嘘です、私の名前は怠慢です)

動的計画法の記事とか書いた覚えがあるんだけどどこにやったか、さては下書きに残ってるな、ワロタ。(ワロタじゃありません)

今回はUnion-Findの利用が重要な問題を二つまとめて今後の参考に残したいと思います。

atcoder.jp

この間の京大プログラミングコンテストのB問題です。sabaくんが京大まで行って出場していたっぽいですね、ずるい。ばーかばーか。

名前の通りナップサック問題です……が、普通と様子が違います。このままじゃ解けない。

頭が悪いので次のように思考を展開しました。

ナップサックに帰着できるorできない。前者を仮定。
「aが使われる時はbも使われないといけない」というような荷物をひとまとめにすれば普通のナップサック問題に帰着出来る。つまり動的計画法でO(n^2)で解ける。
ではどうやってひとまとめにするか?→Union-findで番号の繋がりを管理すればよい。

数学の問題を解くときとかはこんな感じで深さ優先探索のように解法を考えるんですが、他の人がどうなのか聞いたことがありません。もしよかったらTwitterとかで教えてください。

と言うわけでコードです。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < int(n); ++i)

ll dp[101][1000005];

int main(){
    int n, m, W; cin >> n >> m >> W;
    int w[n], v[n]; rep(i,n) cin >> w[i] >> v[i];
    union_find u(n);
    
    //ひとまとめにする
    int a, b; rep(i,m){
        cin >> a >> b;
        a--; b--;
        if(a > b) swap(a, b);
        u.unite(a,b);
    }
    
    //子の要素を親へ集中させる
    rep(i,n){
        if(i != u.root(i)){ 
            w[u.root(i)] += w[i]; v[u.root(i)] += v[i];
            w[i] = 0; v[i] = 0;
        }
    }

    //ナップサック問題に帰着
    rep(i,n){
        rep(j,W+1){
            if(j < w[i]) dp[i+1][j] = dp[i][j];
            else dp[i+1][j] = max(dp[i][j-w[i]] + v[i], dp[i][j]);
        }
    }
    cout << dp[n][W] << endl;
}

相変わらず読みやすいコードですね。うっとり。

Union-Findの実装は省略しています。分からない部分があったら以前の記事(
自作の関数の保存というのをやってみました - Re:ゼロから始めるプログラミング生活
)か、GitHubを参照してください。
(記事との変更点はクラスにしてコンストラクタを入れたことぐらいなので大丈夫だと思います。)

今回の問題の教訓ですが、次の二つが気になりました。

・グループの要素数が減らない場合、つまり連結しか行われない場合は対象に番号を割り振ることで、Union-Findでグループ分けが出来る。
ナップサック問題で荷物の重量と価値を0にしておけば、その荷物はないものとして、荷物の数を変えないまま実装出来る。(要検証)

2つ目は他で使うのか?って感じなので放っておきます。

1つ目は、連結判定が本質的にグループ分けになっているという話です。考えたら当たり前のような気がしますが、Union-Findでグループ分けを手軽に行えるようになるのは大きいと思います。

次の問題です。

atcoder.jp


これDifficulty低くないですか、みんな当たり前のように全探索出来たりUnionFind使えるのなんなんでしょう。
sabaとか水色なのにUnion-findわからーん!とか言ってた時期があった(僕がプログラミングを始めた当初の話です)し、chokudaiさんの言うように各色の平均的な実力が上がっているのかも。つまりぼくはえらい。

さて、この問題ではまず実質的にA_xi+A_yiの偶奇が与えられているところから始まります。
A_xiとA_yiのどちらか一方の偶奇がわかればもう片方の偶奇も分かるということになります。
そこで、これらをグラフの要素とみて、繋いでおきます。
こうして繋いで行くと、グラフの繋がった頂点の集合では、どれか一つの偶奇がわかれば他の偶奇も分かることになります。

結局、頂点がグループになっていて、このグループ数を求めたいわけです。明らかにUnion-Findの出番です。

int main(){
    int n,m; cin >> n >> m;
    union_find graph(n+1);
    int x,y,z;
    int ans = 0;
    rep(i,m){
        cin >> x >> y >> z;
        graph.unite(x,y);
    }
    rep(i,n) if(graph.root(i+1) == i+1) ans++;
    cout << ans << endl;
}

このように解けます。

Union-Findの利用例はもっとありますが、体力が切れたのでここまでにします。

今回当たり前のようにナップサック問題を解いていましたが、結局動的計画法の勉強記録を載せていないので流れとして不自然な気がしますね。気がするだけなので諦めることにします。

ではおやすみなさい。

二部グラフ判定

おはようございます。愛と正義の侵略者です。そろそろゴールデンウィークですね。

AGC039お疲れ様でした。何も分からなかった。

Aだけ解いて水パフォ出してレートを少し上げるみたいな生活をそろそろやめたいです。まだ緑で消耗してるの?(笑)

そんなわけで少しずつ学習を進めていくべく、二部グラフについてちょっと勉強しました。

二部グラフってなに? 調べてみた!

いかがでしたか? 二部グラフというのは頂点が二つのグループに分けられ、同じグループ同士の頂点同士を繋ぐ辺が存在しないようなグラフのことなんですね!


二部グラフの応用例は広く、中々全部を網羅するのは難しそうです。

ひとまずグラフが二部グラフに出来るかの判定をする関数を書いてみました。

深さ優先探索でグラフを見ていきます。
各頂点に色を交互に(つまり同じ色が隣合わないように)割り振っていき、既に探索済みのところに当たったらその頂点の色と現在引数で持っている色との整合性が取れるかを判定します。
(色は配列に収めるようにします。)
整合性が取れるなら問題なし、取れなければ二部グラフには出来ません。

//二部グラフに出来るかを判定
//now:現在の頂点番号
//color:1か2
//colors[i]: i番目の色、1か2を入れる。初期値は0で、このときi番目は未訪問
//graph: 探索対象のグラフ。適当に構成する。
//呼び出し方はisPartited(0,1)とかでよさげ
int colors[10000];
vector<vector<int>> graph(10000);
bool isPartited(int now, int color){
    if(colors[now]){ //探索済み
        if(colors[now] != color) return false; //探索済みなら色の整合性が取れないとダメ
        else return true;
    }
    colors[now] = color;
    int g_size = graph[now].size();
    for(int next = 0; next < g_size; ++next){ //ここの処理はグラフの実装によって適当に変えます
       if(!isPartited(graph[now][next], 2-((color+1)%2))) return false; //1つでもfalseがあったら二部グラフにはならない
    }
    return true; //分岐が全てtrueならtrue
}

昨日のB問題を通す時に使ったのを元に書いたので多分バグはないと思いますが、使う人(いるのか?)は自己責任でお願いします。

グラフの構成とかは適当にやってください。僕は基本的にvector> graph(適当なサイズ)をやってここに要素を追加して隣接リストにして作っています。

しかし「そんな甘っちょろいことやってられるか!」みたいな人がいる(訳ないけど万が一いる)なら上手く実装を変更してどうぞ。

(このブログ見るの僕と同じかそれ未満の実力の人ぐらいだと思うので、そんな人はいないとは思うんですが)


そういえばグラフの直径を求める時にワーシャルフロイド法を使えるのは知りませんでした。考えたら当たり前なんですが……><

いやもっと精進しないといけない。某に「精進グラフが対数になってるよ?(笑)怠惰くん大丈夫?(笑)あっこるぼーくんだった(笑)」とか煽られました。

ではおやすみなさい。

大雑把に夏休みのまとめ

おはようございます。ブログの方は随分ご無沙汰だったので、夏の間の成果を自慢しておこうと思います。

というのは冗談で、あまり満足できる感じではなかった。

以下進捗。

・「徹底マスター JavaScript」: 完了
 クソ分厚い黒い本。JavaScriptは完璧……と言いたいが、この言語やべえ。マスターとか考えない方がよさそう。
 ブラウザに関する知識を付けるのが目的だったしまあ良しとしましょう。Reactの学習にも手を出せそう。
 使える言語がC、C++PythonJavaScriptの4つに増えました。

・集合と位相: だめ
 松坂位相、なんとかzorn補題までこぎ着けたが、いかんせん内容が重たすぎる。
 副読本というか、もう少しかみ砕いてある本を借りることに。早く次の段階に進みたい……。

・ゲームプログラミング: だめ
 参考にしていたサイトの内容は大体抑えた。Dxlibに多少慣れた。
 ……が、実際にゲームを作るには素材を作らねばならず、断念。シナリオすら進んでいない。

・競プロ: だめ
 まだ緑ってマジ? 600どころか500覚束ないんですが????
 チーター本多少進んだ。夏の間に終わらせたかったなあ
 後述しますが、セグメントツリーを実装できたのはよかった。C++周りの知識も多少増えた。

・知識全般: まだマシ
 クソ時間かかってるけど、知識量自体は着実に増えつつある。
 もう少しすれば全体の伸びが期待できそう。

というわけで大体撤退です、人生は厳しい。


次はここ数日の近況ですが。
一人でゲームプログラミングのお勉強をしていると、圧倒的先輩のぽうえっと(@poet_official)に誘われ(というか煽られ)数人の集まりを結成。
sabaも誘ったけど忙しそうなので数に入れないとして、slackでぽうえっと、福知ダイズ(@FukucheeDaize)、ぼくの3人で集まりちょっとずつゲームを作ることに。
しかし知識が皆無、特に集団開発とか出来ないのでGitHubの使い方から覚えています。(ぽうえっとくんマジでなんでも知ってて感動しています)
追伸:sabaが多少時間ありそうなので参加してえ!という事になった。Pythonでサーバーサイドを皆殺しにしてくれるかもしれない。Unityを授業で扱うとかで、その辺にも乗り気のようです。

とりあえずリポジトリとかいうのを作って競プロ用ライブラリを上げてみました。
https://github.com/zerokpr/Kpr_Library

cordata.cppには適当なデータ構造を放り込んでいこうと思います。今のところunion-findとsegment-treeのみ。
cormath.cppには適当な数学関数を入れていこうと思います。今のところ最大公約数と素数判定、指数関数と二項係数です。
後は文字列操作用の関数を用意していますが色々難しいのでまたあとで上げようと思います。
後者二つは普通に第二引数までの使用の他、第三引数にmodを入れればmodの範囲内で計算してくれます。Pythonのと同じ感じにしたかったんですよね。素因数分解作りかけになっててワロタ

多分見られるはず。もう少し使い方を覚えればもっと色々出来そうだけどまだよく分からない。プッシュってなんだ、なんか押すのか。

眠い。さらば。