（初級者競プロer向け）グラフの探索(DFS)を1から再帰関数で実装する方法

前回の記事にてグラフのおおよその実装の仕方は分かったと思います。
前回の記事→（初心者向け）グラフの実装について - bplain’s blog

今回は、そのグラフを探索する操作の書き方です。

そして今回の記事は、再帰関数をN=0からインクリメントしてN=3で終了とすると、その動き方は0123210となっている事を知っている人を対象としています。
逆に言うと前回の記事とそれだけ知っていれば十分読めるように作りました。
もし分からない場合はそれらを復習するとわかると思います。

１、直線で連結している形

まずはグラフが横に連結しているケースを考えます。(1-3-4-6-9など)
先にコードを見てみます。

#include <iostream>
#include <vector>

using namespace std;

vector<int>gragh[100];

void dfs(int v) {//vは現在いる頂点。次の頂点のgraph[v][0]を引数として受け取ることができる。
    cout << v << endl;
    if (gragh[v][0] == 9)return;//goal地点

    dfs(gragh[v][0]);//gragh[v][0]が次の引数として取り込まれる。(graph[v][0]=bを次の町として考えるときれいに成り立っている。）
}

int main() {

    int a = 1, b = 3;
    gragh[a].push_back(b);
    a = 3; b = 4;
    gragh[a].push_back(b);
    a = 4; b = 6;
    gragh[a].push_back(b);
    a = 6; b = 9;
    gragh[a].push_back(b);

    //1-3-4-6-9

    dfs(1);//スタート地点

}

前回、頂点aから頂点bに行くためには、隣接リストだと、gragh[a][i]=bと表せるということをやりました。

このとき、dfs(int a)という関数を用意しておいて、再帰でdfs(graph[a][0])と書くと、
引数aには行き先が取り込まれます。(graph[a][i]=b(bは行き先)のため。)

そしてコードが進むとその行き先はまたdfs(graph[a][0])により変数aに取り込まれます。

とりあえずここまでを理解するのがまずは重要です。よかったら上のコードで遊んでみてください

２、円状に連結している形（閉路）

次は連結で円状の形を考えます。1-2-3-4-5-6となってから、6-1と戻る形です。

この場合先ほどのDFSを用いて、1に着いたらフラグが立っていない確認をして、立っていなかったらフラグを立て、2に着いたらまたフラグの確認をしてフラグを立て・・・と順に行っていきます。
6番から1番に行く時に1番のフラグが立っていることを確認し、6番から1番以外への道を探します。今回はないので6番におけるループを脱出といった形です。そして5番の頂点からまたループに潜ります。(5-6は探索済みとなり次の辺を探そうとする)

コードに解説を徹底的に書きなぐったので、そちらを見ると分かりやすいかもしれません。

#include <iostream>
#include <vector>

using namespace std;

vector<int>graph[100];
bool visited[10];//到達済みのflag

void dfs(int v) {//vは現在地点。vからbに行こうとしている。
    if (visited[v])return;//すでに到達しているならば一番最後の関数を閉じ、一つ前の関数に戻る(endの位置)。
    visited[v] = true;
    
    for (int i = 0; i < (int)graph[v].size(); i++) {//それぞれの頂点のリストを0から確認し、行き先がないか判断する。
        cout << v << ' ' << graph[v][i] << endl;//現在いる頂点の出力用にどうぞ
        dfs(graph[v][i]);//graghの[v][i]=bが次の引数として取り込まれる。
        //end。頂点6のループ,5のループ...,4,3,2,1と戻っていく。
    }
}

int main() {

    int a = 1, b = 2;
    graph[a].push_back(b);
    a = 2; b = 3;
    graph[a].push_back(b);
    a = 3; b = 4;
    graph[a].push_back(b);
    a = 4; b = 5;
    graph[a].push_back(b);
    a = 5; b = 6;
    graph[a].push_back(b);

    a = 6; b = 1;
    graph[a].push_back(b);
    //   　6
    // ／      ＼
    //1--2--3--4--5 

    int V = 6;//頂点数
    for (int i = 1; i <= V; i++) {//頂点全てからdfsを試みる。
        if (visited[i] == false) {//頂点1から6までのフラグ。今回は頂点１から一回ですべてを回れてしまうのでi=1の時しか関数は呼び出されない
            dfs(i);
        }
    }
    cout << "YES" << endl;//動作終了
}

正直なところ、最初は無事動作を終えるプログラムを書くだけで難しいので、コピーしてお試しください。
そして再帰関数の終了の感覚をつかみにくい方は、思い切ってreturnの地点でgoto文を使っていると考えてしまうのが分かりやすくておすすめです。
そうして自分は理解することが出来ました。

この記事を書くのにいつもよりかなりの体力を要したので、今回はおしまい。
よかったらツイッターでふぁぼでもなんでも飛ばしてくださいな(ふぁぼが来ると普通に嬉しい）

（初心者向け）グラフの実装について

タイトルの通り初心者向けです。よかったらゆっくり見ていってください。

さて、競技プログラミングの過去問を解いていると最短経路の問題など、頂点と辺に関する問題が現れます。
町Aと町Bを連結している道路dみたいな感じです。このようなグラフの問題は既にたくさんのアルゴリズムの記事があるのですが、 逆に簡単な実装の記事があまり見当たりませんでした。
なので今回は単純な実装ができるようになることを目標とします。

まずは隣接行列といった形です。簡潔でごり押しなので単純に書きたいときに役立ちます。

とりあえず、辺があるか否かの確認から。一番簡単な形です。

#include <iostream>

using namespace std;

bool graph[1010][1010];//グローバルな場所に配列を置くとすべて0に初期化される。

int main() {
    int V, E;//頂点の数V(vertex)と辺の数E(edge)がよく与えられる
    cin >> V >> E;

    graph[1][3] = true;//町1から町3に辺が出ている

    //無向グラフの場合は以下のように両方から書いておく必要があります。
    graph[3][4] = true;//町3から町4に辺が出ている
    graph[4][3] = true;//町4から町3に辺が出ている

    for (int i = 0; i < E; i++) {//入力例
        int a, b;
        cin >> a >> b;
        graph[a][b] = true;
        graph[b][a] = true;
    }

    //問題　goalまで町1から一つの町を通っていけるかどうか
    int g = 8;
    //goalの頂点が8のパターンとする
    for (int i = 0; i < E; i++) {
        if (graph[1][i] == true && graph[i][g] == true) {
            cout << "GOAL" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;//今回はNO
}

次にコストなどがある重み付きグラフのパターン。
道路を渡るコストが存在するとき、先ほどtrueとしたところをかかるコストに変えることで実装できます。

#include <iostream>

using namespace std;

int graph[1010][1010];

int main() {
    int V, E;//頂点の数V(vertex)と辺の数E(edge)がよく与えられる
    cin >> V >> E;

    graph[1][3] = 5;//町1から町3に行くにはコスト5が必要

    //無向グラフの場合は以下のように両方から書いておく必要があります。
    graph[3][4] = 10;//町3から町4には10必要
    graph[4][3] = 10;//町4から町3にも10必要

    for (int i = 0; i < E; i++) {//入力例
        int a, b, cost;
        cin >> a >> b >> cost;
        graph[a][b] = cost;
        graph[b][a] = cost;
    }

    //問題　goalまで町１から一つだけ町を通ってコスト15以内でたどり着けるか。
    int g = 4;
    //goalの頂点が4のパターンとする
    for (int i = 0; i < E; i++) {
        if (graph[1][i]!=0 && graph[i][g]!=0 && graph[1][i] + graph[i][g] <= 15) {
            cout << "GOAL" << endl;//今回は成功
            return 0;
        }
    }
    cout << "NO" << endl;
}

といった具合。頂点aから頂点bまで[a][b]=cost;となり、見やすいのが特徴。ちなみにダイクストラ法の簡単な実装も可能。
でも辺が少ないと配列のメモリの消費量が大きいのがちょっと辛い。

そこで次は隣接リストといった形。先ほどより少し難しいのでまずは簡単な例を書きます。

#include <iostream>
#include <vector>

using namespace std;

vector<int> graph[1050];

int main() {

    graph[2].push_back(7);//頂点2から頂点7へ
    graph[3].push_back(5);//頂点3から頂点5へ
    graph[3].push_back(2);//頂点3から頂点2へ

    cout << graph[2][0] << endl;//7
    cout << graph[3][0] << endl;//5
    cout << graph[3][1] << endl;//2
}

リスト番号をiとすると、graph[a][i]=bとなっています。これが隣接リストです。
先ほどと違う点は、隣接行列なら簡単にコストを入れることが出来ましたが、
こちらではその分をリストの番号に割り振ったといった感じでしょうか。

また隣接リストを用いると、ループについてかなり書きやすくなります。

#include <iostream>
#include <vector>

using namespace std;

vector<int> graph[1050];

int main() {

    graph[3].push_back(5);//町3から町5へ
    graph[3].push_back(2);//町3から町2へ
    graph[3].push_back(8);//町3から町8へ

    int a = 3;
    for (int i = 0; i < graph[a].size(); i++) {
        //頂点aに連結しているすべての頂点を最小回数で洗い出せる
        cout << graph[a][i] << ' ';//5 2 8
    }
}

いかがでしょうか。このループは上手く使えば計算量も少なくなりそうで、中々に使い道がありそうです。

最後に、隣接リストにおける重み付きグラフ、すなわちコストの存在する場合の実装のコード例を載せます。

#include <iostream>
#include <vector>

using namespace std;

struct edge {
    int to, cost;
};

vector<edge> graph[1050];//構造体にて二つの成分を持てるようになった

int main() {

    int a = 2, b = 3, co = 6;//町aから町bに行くときのコストco
    edge e = { b,co };
    graph[a].push_back(e);

    a = 2, b = 4, co = 5;
    e = { b,co };
    graph[a].push_back(e);

    for (int i = 0; i < graph[a].size(); i++) {
        edge e = graph[a][i];//aからの行き先とaからのコストを取り出せる
        cout << e.to << ' ' << e.cost << endl;
    }
}

といった感じ。構造体の知識や、vectorを使いこなす必要があるけど、とても便利。

今回はここまで。グラフを初めて見たときは実装する方法が全くわからなかったので、そういった点に絞りました。
ここまで理解すれば最短経路問題のアルゴリズムのコードは大体読めるようになっていると思います。（特にダイクストラ法）
競プロはアルゴリズムの勉強も大事だけど、基礎的な実装も大事！

map四種類の使い分け

今回はmapの４種類について。

map、unordered_map、multimap、unordered_multimapといった四つの種類がある。
mapとmultimapは木構造を用いているため自動でsortされる特徴がある。
unorder_mapとunordered_multimapは自動でハッシュを用いて値の検索用に作られている。(sortされない)

mapとunorder_mapは重複を許さず、(unique)
multimapとunordered_multimapは重複して値を持てる。(multi)

それぞれの機能は以下の通り。見るだけでは中々覚えづらかったのでコピーしてお試しあれ。

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <utility>

using namespace std;

int main() {
    map<string, int>mp;//挿入するたびsort,unique,eraseが行われる
    mp["BB"] = 10;
    mp["AA"] = 20;
    mp["AA"] = 30;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        cout << itr->first << ' ' << itr->second << endl;
    }
    cout << endl;

    unordered_map<string, int>ump;//挿入するたびunique,eraseが行われる
    ump["BB"] = 10;
    ump["AA"] = 20;
    ump["AA"] = 30;
    for (auto itr = ump.begin(); itr != ump.end(); itr++) {
        cout << itr->first << ' ' << itr->second << endl;
    }
    cout << endl;

    multimap<string, int>mmp;//挿入するたびsortが行われる
    mmp.insert(make_pair("BB", 10));
    mmp.insert(make_pair("AA", 20));
    mmp.insert(make_pair("AA", 30));
    for (auto itr = mmp.begin(); itr != mmp.end(); itr++) {
        cout << itr->first << ' ' << itr->second << endl;
    }
    cout << endl;

    unordered_multimap<string, int>ummp;//ハッシュバージョンのpair
    ummp.insert(make_pair("BB", 10));
    ummp.insert(make_pair("AA", 20));
    ummp.insert(make_pair("AA", 30));
    for (auto itr = ummp.begin(); itr != ummp.end(); itr++) {
        cout << itr->first << ' ' << itr->second << endl;
    }
    cout << endl;

    pair<string, int>pa[10];//pairが気になる方もいると思うので載せました。
    pa[0] = make_pair("BB", 10);
    pa[1] = make_pair("AA", 20);
    pa[2] = make_pair("AA", 30);
    for (int i = 0; i < 3; i++) {
        cout << pa[i].first << ' ' << pa[i].second << endl;
    }
}

ただ、競プロだとハッシュの危険性から普段は遠慮せずにmapを使い、O(1)を必要とする場合はunordered_mapを使うのが良さそう。
でもどれも色々な場面で使えそうなSTLで良い感じ。

mapを使えるC問題はこちら。
C - Good Sequence

std::mapについてシンプルに

今回はstd::mapについて。
使いどころがよくわからなくなるmapですが、どうやらキーと値が違う場面だと書きやすいようです。
そしてたまに見かけるアロー演算子はこうやって使うみたいです。

例題　N個の文字列が与えられる。そのN個の文字列を辞書順で早い順から出現した回数とともに出力しなさい。

ソースコードで表すとこんな感じ

#include <iostream>
#include <string>
#include <algorithm>
#include <map>

using namespace std;

int main() {
    int N;
    cin >> N;
    map<string, int>mp;
    for (int i = 0; i < N; i++) {
        string S;
        cin >> S;
        mp[S]++;
    }//ここまで入力

    for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
        cout << itr->first << ' ' << itr->second << endl;
    }
}

mapが使いやすい問題 B - Two Colors Card Game

atcoder茶色にすらなれなかった人が茶色になるまでのお話

まず初めにこのタイトルを見て、なんでや！茶色ぐらいになら誰でもなれるでしょ！と思った方もいるでしょう。
しかし、なれなかった時があった。そんな人のお話。

プログラミング、そして競プロを始めたきっかけ

昔からパソコンが好きではあったのですが、動画とかしか見ていなかったため、もっとパソコンで色々な事ができるようになりたい！ということでC言語を勉強しました。
その内容は汎用的で十分使う価値があると思っていましたが、パソコンの知識がほぼ無く、アプリケーションってどう作るんだといった感じでした。
そしてプログラマーの転職サイトやなんやかんや見ているうちに偶然atcoderさんのサイトを見つけて、競プロの世界を知ります。
また、よく使われている言語がC++ということで改めて覚えました。

競プロへの参加（一年前）

そして準備も整い、ABC063に参加して問題を解きました。最初にしてはそこそこ解けて、結果は2完でした。
楽しかったので意気込んで次のABC064に参加。ここで３完を叩き出します。 次のABC065では２完。まずまずの手応え。
・・・ここまでは良かったのですが、ABC066、まさかの一完。

この回のB問題は文字列。C言語から入ってしまったがゆえにstring型をあまり練習していなかったため、substrなどのSTLの使い方に混乱してしまったのです。
その時もtwitterでアカウントを作っていたのですが、周りの競プロをしている人はみな強い人が多く、自分にセンスはないのではと思ってしまいました。
その時少しだけ過去問を解いて対策をしたつもりだったのもいけないのでしょう。リアルも少し忙しくなり、しばらく競プロから離れました。

自分の欠点との向き合い、性格の変化

少しリアルの方で色々大きな変化が起きました。深くは書けませんが、自分はその当時、努力をあまり好んではいませんでした。成果が出ない時が悔しかった。ならしない方がいいのではと。
しかしそれは真逆で、努力したら何でも成果が出るということに気づいてから色々状況が変わりました。

悪い努力をすると悪いものができるし、良い努力をすると良いものができると。
結局は自分の行動次第なんだと。

ただそれだけの事でしたが、現実でそれを知った時は本当に体に電撃が走ったようでした。 ついでに性格そのものが少し前向きになりました。

プログラミング、競プロへの復帰

じゃあ先ほどの考えは正しいのか実際に試してみようじゃないかと、プログラマーになるため少し頑張ってみようかと思い、アルゴリズムを覚えるついでに競プロへの復帰もしました。そして前回の反省点を徹底的に考えました。

１、勉強量の不足（レートと解いた問題の量がほぼ一致していることを知った）
２、センスが必要だと考えてしまった（元々赤ちゃんは日本語喋れないじゃないか、でも喋れるようになる）
３、自力で考えすぎない（悩むのは楽しいが悩み過ぎるとただ疲れるだけで前に進まない）
４、他人と大きく比較せず、自分のできること、または解ける問題を増やす。目標は一つだけ先に。

４については、まだ競プロ初心者なので、自分が出来るようになったことは他の人にとっては簡単な事なので結構恥ずかしいです。それでも出来ることが増えるのは嬉しい。そういう時ぐらいプライドなんてどっかいっちゃえ精神を持つことに。
というわけで随分精神的なものが安定しました。いえい。

まさかの再び１完

そしてABC093から無事競プロに戻り、コンテストに出たり、atcoder problemsにめちゃくちゃお世話になりながら、A問題、B問題を埋め終わります。それなりに早くB問題が解けるようになり、手応えを感じ始めていました。その矢先、

ABC098。１完爆死。

えええ何だこのB問題、全探索のコードすらまとまらない。そして終了後atcoder problemsに表示されるB問題97/98。
さすがに？？？？ってなりました。でも色々過去の１完のことを思い出しているうちに、苦手な文字列だったことと、実は全探索のコードを書く練習はさっぱりしてないことに気づきます。
そして実際はC問題にもかなり時間を割いていたため、単なる実力不足と落ち着くことが出来ました。メンタル安定大事。

そんなこんなで実力が少しずつついていき、結果としてAGCの１完を無事こなせて茶色になれました。過程色々書いたけど結果が出るときは一瞬じゃい！

↓レートと精進量（ACのモチベにでもどうぞ）

色がつくまでに結果的に一年かかった人がこちらになります
忙しかったのもあるけれどなんやかんや嬉しい pic.twitter.com/BzXG1j9OWS

— bplain (@bplain2) June 3, 2018

（そして皆ふぁぼ飛ばしてくれて優しい！いい記事書けるようになったら恩返しする！）

現在は自分自身の伸びしろを感じていて精進中です。動的計画法なんかは以前は知りもしませんでしたが、現在は簡単ものは書けるようになりました。典型アルゴリズムはたくさんあるので一つ一つ習得するまでは頑張ると決めています。

次の目標は300点問題をもっと解けるようになりたいことと、AC数を増やすことでしょうか。頑張ります。

lower_boundとupper_bound

今日も今日とて簡単な例を挙げていく。 意外に違いが少ないことがわかった。

int main() {
 int a[100] = { 1,3,4,5,10,14 };
 cout << *lower_bound(a, a + 6, 6) << endl; //10
 cout << *upper_bound(a, a + 6, 6) << endl; //10
}

lower_boundはN以上となる最初のイテレータを指しているそうです。また、 upper_boundはNより大きい最初のイテレータを指してるそうです。

int main() {
    int a[100] = { 1,3,4,5,6,10 };
    cout << *lower_bound(a, a + 6, 6) << endl;//6
    cout << *upper_bound(a, a + 6, 6) << endl;//10
}

ちょっと難し目なABC B問題集

個人的にやられてしまったB問題達です。 B問題なのにしっかりした問題が多いので、ゆっくり取り組むのがおすすめです。

B - 価格の合計 bit

B - □□□□□　図形

B - Two Switches 下限と上限

B - Kagami Mochi データ構造

B - Trained? グラフ

B - 島と橋 場合分け

B - ss　文字列

個人的にB問題で一番難しかったもの

B - Cut and Count 文字列