こんにちは。倉内です。
paizaでは、動画講座やスキルチェック、プログラミングゲームなどさまざまな学習コンテンツを公開しています。
中でもプログラミングの練習問題を集めた「レベルアップ問題集」は、コーディング力を鍛えるのに特におすすめです！今回は、その中から最近追加されたグラフアルゴリズムに関する問題集を中心にご紹介します。
なお、アルゴリズムの学習を始めたばかりで、まずは基本問題を解きたい方は、こちらから定番アルゴリズムの問題集に取り組んでみてください。
グラフとは
「グラフアルゴリズム」の話をする前に、まずグラフについて簡単に説明しておきます。
グラフとは、下図のようなノード（頂点）とエッジ（辺）の集まりのことで、ノードとノードの関係性を表しています。たとえば、数字の1が書かれたノードと2が書かれたノードは隣り合っている、といった感じです。
グラフのエッジには、向きがある（一般的に矢印のように示す）場合と、向きがない場合があります。それぞれ、有向グラフ、無向グラフと言います。上の図はエッジに向きがないので無向グラフです。
グラフを表現する際に、上のようにノードとエッジで表現することもあれば、グリッドや隣接行列で表現することもあります。
以下の記事で、グラフに関する用語をはじめ、もう少し詳しく説明していますので、よければ参考にしてみてください。
定番グラフアルゴリズム
現在、「レベルアップ問題集」では以下の問題メニュー・セットを公開しています。それぞれどのような内容を扱っているのか、どのくらいのレベル感かをご紹介します。
ちなみにメニューはそれぞれ独立した問題を複数集めた問題集、セットは同じテーマで易しい問題～難しい問題に段階的に挑戦できるようになっている問題集です。
難易度を示すランクは、paizaが提供する「スキルチェック」というサービスで、プログラミングスキルを評価するS・A・B・C・D・Eの6つのランクに準じています。詳しくはこちらもご覧ください。
グラフ構造の入力メニュー
グラフの概念や知識を知らない人や難しいアルゴリズムを設計できない人にオススメのメニューです。グラフの入出力や隣接行列や隣接リストの実装ができるようになります。
問題数：全22問
解答例のある言語：C++・C#
難易度：A～Cランク相当
出題例（Cランク相当問題）
頂点の出現回数・無向グラフ
1, ..., n の番号がついた n 個の頂点と、1, ..., m の番号がついた m 個の辺からなるグラフを考えます。
整数 n, m と、m 個の頂点の組 (a_1, b_1), ..., (a_m, b_m) が与えられます。
頂点の組 (a_i, b_i) は、頂点 a_i と 頂点 b_i が辺で直接つながっていることを表します。
(頂点 a_i と 頂点 b_i が辺で直接つながっているとき、頂点 b_i と 頂点 a_i も辺で直接つながっているといえます。)そして、これら以外に辺で直接つながっている頂点の組はありません。
このとき、指定された頂点 v が m 個の辺のうちいくつの辺に現れるか求めてください。すなわち、a_1, b_1, a_2, b_2, ..., a_m, b_m のうち指定された頂点 v に等しいものの個数を求めてください。
ただし、a_i と b_i は異なる頂点であること、また同じ頂点の組は 2 回以上入力されないことが保証されます。
グラフ・DFSメニュー
DFSとは、Depth First Searchの略で深さ優先探索のことです。
グラフの概念はなんとなく知っているが、実際にプログラムで扱ったことがない人にオススメのメニューです。DFSを理解し、連結成分の数の判定や木の判定に使用できるようになります。
問題数：全39問
解答例のある言語：Python3
難易度：A～Dランク相当
出題例（Dランク相当）
隣接頂点の出力
1, ..., n の番号がついた n 個の頂点とそれらをつなぐ枝からなる無向グラフを考えます。ただし、自己ループと多重辺は考えません。
隣接リストとある頂点 s が与えられます。このとき、頂点 s に隣接している頂点のうち最も番号の大きいものを出力してください。
探索については、以下の記事で詳しく紹介しています。
グリッド版ダイクストラ問題セット
グリッド上でダイクストラ法を活用して最短経路などを求める問題をまとめています。
問題数：全17問
解答例のある言語：Java・Python3
難易度：A～Cランク相当
出題例（Cランク相当）
グリッド上の移動
グリッド状の盤面の左上からスタートして、「右、下、右、上、左」と順に移動したときの経路上のマスのコストの合計を求めてください。
経路上のマスには、スタートとゴールのマスも含むものとします。
こちらは全問以下の記事で解説しています。難度の高い問題も多いので、ぜひ参考にしてみてください。
ワーシャルフロイドメニュー
この問題集では、最短経路問題を解くアルゴリズムの一つであるワーシャルフロイド法を扱います。
最短経路問題とは、重み付きグラフの与えられた 2 点を結ぶ経路のうち、コスト（距離など）が最小のものを求める問題です。ワーシャルフロイド法を使うと、グラフのすべての 2 点間の最短距離を求めることができます。いくつかのステップにわけてワーシャルフロイド法の理解を深めていきましょう。
問題数：全9問
解答例のある言語：Python3
難易度：A・Bランク相当
出題例（Bランク相当）
隣接行列の出力
まずは、与えられるグラフを隣接行列に変換してみましょう。
1, ..., N の番号がついた N 個の頂点とそれらをつなぐ枝からなる有向グラフを考えます。ただし、自己ループと多重辺は考えません。
M 本の重み付き有向枝が与えられます。このとき、次のように定義される隣接行列を出力してください。
---
N × N の正方行列で、上から i 行目、左から j 列目 (1 ≦ i,j ≦ N) の要素が
i ≠ j のとき
・頂点 i から頂点 j に向かって枝が伸びていればその重み（距離）、そうでなければ 999i = j のとき
・0
DAG・メモ化再帰メニュー
DAGは、閉路を持たない有向グラフのことです。メモ化は、プログラム高速化のための最適化技法のひとつです。再帰は理解が難しい・苦手という方も多いと思いますが、ぜひ挑戦してみてください。
問題数：全11問
解答例のある言語：C++
難易度：A・Bランク相当
出題例（Bランク相当）
フィボナッチ数列
1 以上 100,000 以下の数値 N が与えられます。フィボナッチ数列 の N 項目の数を求めてください。答えは非常に大きくなることがあるので、 1,000,000,007 で割ったあまりを出力してください。
ここで、フィボナッチ数列の 1 項目は 1 、 2 項目も 1 、 3 項目は 2 とします。
この問題はさまざまな実装方法がありますが、メモ化再帰を用いて実装してみましょう！
フィボナッチ数列は、動画講座「アルゴリズム入門編」でも解説しています。
ベルマンフォードメニュー
ベルマンフォード法は、頂点 s から各頂点への最短距離を更新できるかどうか枝をひとつひとつチェックするという操作を（頂点の数）- 1 回繰り返すというアルゴリズムです。
ヒントが記載されている問題もありますので、じっくり取り組んでみてください！
問題数：全9問
解答例のある言語：Python3
難易度：A～Cランク相当
出題例（Aランク相当）
1,...,N の番号のついた N 個の頂点とそれらをつなぐ枝からなる有向グラフを考えます。ただし、自己ループと多重辺は考えません。
M 本の重み付き有向枝と頂点番号 s が与えられます。頂点 s からほかのすべての頂点へ向かう経路の最短距離を出力してください。頂点 s からの枝の移動では到達不可能な場合は inf と出力してください。
ただし、経路（枝の集合）の距離とはその経路を構成する枝の重みの和とします。ある頂点からその頂点自身へ移動する場合は、その区間の重みを 0 とします。
なお、頂点 s から各頂点への最短距離はベルマンフォード法を利用して求めてください。
まとめ
「レベルアップ問題集」からグラフアルゴリズムの問題集を紹介しました！
プログラミングの基本をある程度押さえて、もう少しプログラミングスキルを伸ばしたいと考えている方におすすめです。
特に競技プログラミングに本格的に取り組んでみたい方にとって、欠かせない内容ばかりですのでぜひ問題集を活用して理解を深めていただければと思います。
他にもさまざまな内容・難易度の練習問題を多数公開しています。随時新しいものも公開していますのでチェックしてみてください。
paizaラーニングでは、ほかにもJava、Ruby、C言語、PHP、SQL、JavaScript、HTML/CSSなど、人気言語の動画レッスンを公開しています。
詳しくはこちら
そしてpaizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
詳しくはこちら
