競プロのグラフ問題を社内で教えてみた
最初に
社員のロジック力を向上させる目的で、月2回競プロ勉強会を開催しています。
今回チームの人からグラフ問題を解けるようになりたいとの要望があり、実際にグラフ問題を解けるようになるまでにどの問題を解いたかを書いていきます。
この記事を書いている人の実力は？
いわゆる水色エンジニアです。最近は引退気味で、時間がある時にAHCに参加しています。
どのくらいのレベルの人が対象？
灰色~茶色レベルの人が対象です。社内でもこのくらいのレベル感の人が多いです。
新卒の方にも参加してもらえたので、プログラミングがある程度わかっている人くらいが対象かな？と思います。
目標は？
今回は全員がダイクストラを書けるまでを目標にしました。
単純なグラフ問題が解けるより、最短経路問題が解けるってなった方が満足度というか、やり切った感があるとなと思ったので、これを目標にしました。
実際に解いた問題
グラフをデータとして持つ方法
ここはグラフ問題の基礎の基礎なので、2回に渡って行いました。
グラフをどのような形式で保存するか、という初歩的だけど重要な部分を学ぶための問題です。
この問題に取り掛かる前に、グラフのデータの持ち方を2つ説明しました。
1. 2次元配列で持つ方法
2. 連想配列で持つ方法
なんとかの忘却曲線を意識して、グラフのデータを作成する問題をもう一度やりました。
今回は説明なしで、自力で解いてもらいました。
深さ優先探索
深さ優先探索を学ぶための問題です。
問題としては幅優先探索でも解ける問題なのですが、深さ優先探索で解いてもらいました。
幅優先探索
幅優先探索を学ぶための問題です。
グラフ系の問題ではないのですが、いい塩梅の問題が見つからなかったので、幅優先探索という概念を学んで貰えば良いかなと思ったのでこれで代用しました。
優先度付きキュー
グラフ系の問題ではないですが、ダイクストラで必要なため用意しました。
ダイクストラ
本命のダイクストラ問題です。最初に考え方を教えてから解いてもらいました。
この問題はダイクストラで解けますが、以下の3つが一番最初に解いてもらう問題としてはネックかなと思ったので別の問題の方が良かったかな？と思いました。
- グラフが無向グラフ、最初に解いてもらうなら有向グラフがわかりやすかったかも
- 到達できない場合が存在します。連結グラフの方がわかりやすいと思う。
- ダイクストラはある点からある点までの最短距離を求めるものですが、この問題は全ての頂点までの最短距離を求めなくてはいけない問題でした。実際に何人かはそこの違いに戸惑っていました。
ここら辺を満たす問題を探してみましたが見つからなかったので、とりあえずこの問題が今の所のベストかなと思います。
実際にやった感想
上記の問題を２週間で1問くらいのペースで解いて行きました。
1問解いてもらうのに、最初の説明を含めて1-2時間ほどかかりましたが、ダイクストラを書いてもらうという目標は達成することができました。
最初はグラフを辞書で保持するという部分に手こずっていた方が、最後のダイクストラの時には最初のアルゴリズムの説明のみでコードを実装できるようになっていたので、ロジックの実力はだいぶ上がったなという様に感じました。
最後に
競プロって実務で使わないよね〜〜〜っていう人もいて、実際にこのようなアルゴリズムを書く機会は少ないと思います。
しかし、筋トレと同じで確実に基礎能力は上がるなーと個人的には感じているので、ぜひみなさん社内勉強会で取り入れてみてはいかがでしょうか。
Discussion