ABC#016 C問題 友達の友達
学期末のレポートに追い立てられて逃避で競技プログラミングの問題しか解いてない.
題意
N人のグループに対してM個の人間関係が与えられるので,各人について「友達の友達」(自分と自分の友達は含まない)の数を出力する.
やりかた
要はグラフなので,各ノード(人間)について幅優先探索で距離を数える
import std.stdio; import std.string; import std.conv; import std.array; import std.range; import std.algorithm; import std.container; import std.math; void main() { int N, M; readf("%d %d\n", &N, &M); bool[][] friend = new bool[][](N, N); for (int i = 0; i < M; i++) { int a, b; readf("%d %d\n", &a, &b); friend[a-1][b-1] = true; friend[b-1][a-1] = true; } // 1人目から順番に for (int i = 0; i < N; i++) { // アクセスしたかどうかの配列 bool[] check = new bool[N]; // 自分には先にチェックしておく check[i] = true; // 距離の配列 int[] d = new int[N]; // 幅優先探索用のキュー int[] q = [i]; while(!q.empty) { // 1人取り出す int p = q.front; q.popFront; // p番の人の人間関係について foreach (int j, isFriend; friend[p]) { // 未訪問 if(!check[j]) { // 友達なら if (isFriend) { // p番の人までの距離に1を足す d[j] = d[p] + 1; // 訪問チェック check[j] = true; // j番目の人をキューに追加 q ~= j; } } } } d.count(2).writeln; } }
図解(3人いて1番と2番,2番と3番が友達だとして,1人目からの距離を数える) friend [[0, 1, 0], [1, 0, 1], [0, 1, 0]] check = [t, f, f], d = [0, 0, 0], q = [0] qから先頭の要素を取り出す(p = 0, q = [], friend[p] = [f, t, f]) 2番がtなので1番(p)と2番(j)は友達 d[j] = d[p] + 1 = 1 d = [0, 1, 0] check = [t, t, f] q = [1] qから先頭の要素を取り出す(p = 1, q = [], friend[p] = [t, f, t]) 1番は訪問済み 3番がtなので2番と3番は友達 d[j] = d[p] + 1 = 2 d = [0, 1, 2] check = [t, t, t] q = [3] qから先頭の要素を取り出す(p = 2, q = [], friend[p] = [f, t, f]) 全て訪問済みなので何もしない qが空なのでwhileを抜ける
ざっとこんな感じ? 自分で書いてみて幅優先探索の仕組みがようやく分かった気がする.あと普段自分が競技プログラミングの簡単な問題で解説を調べてるときに全くコメントが入ってないプログラムとかを見ると初心者的には「は〜(°〜°)?????キレそーーwwwwwwwwwwww」ってなるので1行毎にコメントを入れたりループ毎の変数の状態を書いてみた.お役に立てれば.良い問題だった.
その他
- std.algorithm.countは便利
- テンプレート引数に述語を渡せる(
count!("a & 1 == 0")
とか)
- テンプレート引数に述語を渡せる(
- DPの教育的問題何か教えて下さい(AtCoderとAOJとCodeforcesはアカウント持ってます)
- 某太鼓ゲームの問題は何となく理解したつもり