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はアカウント持ってます）
  • 某太鼓ゲームの問題は何となく理解したつもり