読者です 読者をやめる 読者になる 読者になる

データ・サイエンティストは可視化の夢を見るか?

Does Data Scientist Dream of Visualization?

みずからコード・レヴューしてみたいのに

プログラミング冥府魔道

以下は『プログラミングコンテストチャレンジブック [第2版]』(蟻本)の『食物連鎖(POJ 1182)』の例題の写経です。
ほとんど書き写しですが、入出力部分などは当然のごとく自家製です。

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

『Union-Find 木』というデータ構造はこれまで知りませんでした。
「グループ分けを管理する」ためのデータ構造だそうです。以下の 3 つの特徴があります。

  1. 要素 a と要素 b が同じグループに属するかを調べる
  2. 要素 a と要素 b のグループを併合(merge)する
  3. グループの併合はできても分割はできない

冒頭の 4 関数が此のデータ構造を実現するための関数です。
データ構造は配列 2 種の併用でとりあえず済ませています。

数十行程度の内容ですが、要は『食物連鎖(POJ 1182)』のお題に沿って【関係性】を実装するのですが、此の内実を定義しているのが solve() です。つまり「ルール」を如何にコード化するかが、このような問題の勘所なのですね。正直、まだ発想が追いつかなくって困っています。「// x, x+N, x+2*N を x-A, x-B, x-C の要素とする」というところが動物種 A, B, C のあいだの基本関係になっています。そして、これに当てはまらないような『(入力)情報』を弾いていく訳です。


それにしても難しい。
こういったアルゴリズムの動作を確認していくには、ところどころにデバッグ・プリントを差し込んで全体の流れを把握するしかないんでしょうね……。

//
//  main.cpp
//  FoodChain-01
//
//  Created by renpoo on 2016/12/15.
//  Copyright © 2016 renpoo. All rights reserved.
//

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

const int MAX_N = 100000;
const int MAX_K = 100000;


int par[MAX_N];  // 親
int rank[MAX_N]; // 木の深さ

// n 要素で初期化
void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i]  = i;
        rank[i] = 0;
    }
    return;
}

// 木のルートを求める
int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

// x と y の属する集合を併合
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    
    if (rank[x] < rank[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}

// x と y が同じ集合に属するか否か
bool same(int x, int y) {
    return find(x) == find(y);
}


int N, K;
int T[MAX_K], X[MAX_K], Y[MAX_K];

void solve() {
    // Union-Find 木を初期化
    // x, x+N, x+2*N を x-A, x-B, x-C の要素とする
    init(N * 3);
    
    int ans = 0;
    for (int i = 0; i < K; i++) {
        int t = T[i];
        int x = X[i] - 1;
        int y = Y[i] - 1;
        
        // 正しくない番号の場合
        if (x < 0 || N <= x || y < 0 || N <= y) {
            ans++;
            continue;
        }
        
        if (t == 1) {
            // 「x と y は同じ種類」という情報の場合
            if (same(x, y + N) || same(x, y + 2 * N)) {
                ans++;
            } else {
                unite(x, y);
                unite(x + N, y + N);
                unite(x + 2 * N, y + 2 * N);
            }
        } else {
            // 「x は y を食べる」という情報の場合
            if (same(x, y) || same(x, y + 2 * N)) {
                ans++;
            } else {
                unite(x, y + N);
                unite(x + N, y + 2 * N);
                unite(x + 2 * N, y);
            }
        }
    }
    
    printf("%d\n", ans);
    
    return;
}


int main() {
    
    // N = 100
    scanf("%d", &N);
    
    // K = 7
    scanf("%d", &K);
    
    // (T, X, Y)[] = "1 101 1"
    // (T, X, Y)[] = "2 1 2"
    // (T, X, Y)[] = "2 2 3"
    // (T, X, Y)[] = "2 3 3"
    // (T, X, Y)[] = "1 1 3"
    // (T, X, Y)[] = "2 3 1"
    // (T, X, Y)[] = "1 5 5"
    for (int i = 0; i < K; i++) {
        scanf("%d %d %d", &T[i], &X[i], &Y[i]);
    }
    
    solve();
    
    return 0;
}