１２．４ 幅優先探索（写経編）

本業でいろいろとやられてまして久しぶりの更新です。まあ写経ですが。。

d という変数名が分かりづらいので distance という名前にしたのですが、iterator の distance と ambiguous(曖昧だ)ってコンパイラに怒られました。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

enum COLOR {
  WHITE,
  GRAY,
  BLACK,
};

static const int INFTY = INT_MAX;
static const int N = 100;

static int M[N][N] = {};
static vector<COLOR> color(N, WHITE);
static vector<int> d(N, INFTY);

static void bfs(int n, int s) {
  color[s] = GRAY;
  d[s] = 0;

  queue<int> Q;
  Q.push(s);

  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int v = 0; v < n; v++) {
      if (M[u][v] && color[v] == WHITE) {
          color[v] = GRAY;
          d[v] = d[u] + 1;
          Q.push(v);
      }
      color[u] = BLACK;
    }
  }
}

int main() {
  int n;
  cin >> n;

  int number, count, value;
  for (int i = 0; i < n; i++) {
    cin >> number >> count;
    number--;
    for (int j = 0; j < count; j++) {
     cin >> value;
     value--;
     M[number][value] = 1; 
    }
  }
  
  bfs(n, 0);
  
  for (int i = 0; i < n; i++) {
    cout << i + 1 << " " << ((d[i] == INFTY) ? -1 : d[i]) << endl; 
  }

  return 0;
}

１２．３ 深さ優先探索（写経編）

間が空いた上に写経という。書籍内の回答例は変数名の意味が分かりづらくて辛いので、そこだけ修正しました。

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

enum COLOR {
  WHITE,
  GRAY,
  BLACK,
};

static const int NIL = -1;
static const int N = 100;

static int M[N][N] = {};

static inline int next(int u, int n, int next_array[]) {
  for (int v = next_array[u]; v < n; v++) {
    next_array[u] = v + 1;
    if (M[u][v]) {
      return v;
    }
  }
  return NIL;
}

static vector<COLOR> color(N, WHITE);
static int total_time = 0;
static vector<int> visit_time(N, 0), finish_time(N, 0);

static void dfs_visit(int r, int n) {
  vector<int> next_array(N, 0);

  stack<int> S;
  S.push(r);
  color[r] = GRAY;
  visit_time[r] = ++total_time;

  while (!S.empty()) {
    int u = S.top();
    int v = next(u, n, &next_array[0]);
    if (v != NIL) {
      if (color[v] == WHITE) {
        color[v] = GRAY;
        visit_time[v] = ++total_time;
        S.push(v);
      }
    } else {
      S.pop();
      color[u] = BLACK;
      finish_time[u] = ++total_time;
    }
  }
}

void dfs(int n) {
  for (int u = 0; u < n; u++) {
    if (color[u] == WHITE) {
      dfs_visit(u, n);
    }
  }
  
  for (int i = 0; i < n; i++) {
    cout << i + 1 << " " << visit_time[i] << " " << finish_time[i] << endl;
  }
}

int main() {
  int n;
  cin >> n;

  int number, count, value;
  for (int i = 0; i < n; i++) {
    cin >> number >> count;
    number--;
    for (int j = 0; j < count; j++) {
     cin >> value;
     value--;
     M[number][value] = 1; 
    }
  }
  
  dfs(n);

  return 0;
}

１２．２ グラフの表現

これは特に悩むところはなく。これから難しくなると思うので小休憩ですね。

#include <iostream>

using namespace std;

static const int N = 100;
static int M[N + 1][N + 1] = {}, p[N + 1] = {};

int main() {
  int n;
  cin >> n;

  int number, count, value;
  for (int i = 0; i < n; i++) {
    cin >> number >> count;
    for (int j = 0; j < count; j++) {
     cin >> value;
     M[number - 1][value - 1] = 1; 
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {    
      if (j != 0) {
        cout << " ";
      }
      cout << M[i][j];
    } 
    cout << endl;
  }

  return 0;
}

１１．４ 連鎖行列積（写経編）

これも写経です。線形代数の確かな知識がないと、手も足も出ませんね。。

写経だけだとアレなので、boost の matrix を使おうと思いましたが、オンラインジャッジで boost が使えるのかがよく分からなかったのでそのままにしておきました。

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

static const int N = 100;
static int m[N + 1][N + 1] = {}, p[N + 1] = {};

static inline void matrixChainMultiplication(int n) {
  for (int l = 2; l <= n; l++) {
    for (int i = 1; i <= n - l + 1; i++) {
      int j = i + l - 1;
      m[i][j] = INT_MAX;
      for (int k = i; k <= j - 1; k++) {
        m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]); 
      }
    }
  }
}

int main() {
  int n;
  cin >> n;
  
  for (int i = 1; i <= n; i++) {
    cin >> p[i - 1] >> p[i];
  }

  matrixChainMultiplication(n);
  
  cout << m[1][n] << endl;

  return 0;
}

１１．３ 最長共通部分列

またもや写経です。

• ２つの文字列の最大長を二次元配列で記憶する
• 文字一致ループの中で１つ前の最大長と比較していく

ということですが、この発想が出てこない。。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

static const int N = 1000;
static int c[N + 1][N + 1] = {};

static int lcs(string& X, string& Y) {
  const size_t m(X.size());
  const size_t n(Y.size());
  X = '\0' + X;
  Y = '\0' + Y;

  int lcs = 0;
  for (size_t i = 1; i <= m; i++) {
    for (size_t j = 1; j <= n; j++) {
      if (X[i] == Y[j]) {
        c[i][j] = c[i - 1][j - 1] + 1;
      }
      else {
        c[i][j] = max(c[i - 1][j], c[i][j - 1]);
      }
      lcs = max(lcs, c[i][j]);
    }
  }
  return lcs;
}

int main() {
  int n;
  cin >> n;

  string X, Y;
  for (int i = 0; i < n; i++) {
    cin >> X;
    cin >> Y;
    cout << lcs(X, Y) << endl;
  }

  return 0;
}

１１．２ フィボナッチ数列

動的計画法の基本とのことです。特に難しいところはなし。

#include <iostream>
#include <vector>

using namespace std;

static vector<int> M(44, 0);

static inline int fibonacci(int n) {
  if (n == 0 || n == 1) {
    return 1;
  } 

  if (M[n] != 0) {
    return M[n];
  } 
  M[n] = fibonacci(n - 2) + fibonacci(n - 1);
  return M[n];
}

int main() {
  int n;
  cin >> n;
  
  cout << fibonacci(n) << endl;
 
  return 0;
}

１０．４ 優先度付きキュー（写経編）

insert/extract ともに難しいので写経。完全二分木を使いこなすには程遠い理解度、ということがわかりました。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

const static int INFTY = (1<<30);
static vector<int> A(2000000 + 1);
static int H = 0;
 
static inline int parent(int i) {
  return i / 2;
}
 
static inline int left(int i) {
  return 2 * i;
}

static inline int right(int i) {
    return 2 * i + 1;
}

static inline void maxHeapify(vector<int>& A, int i) {
  const int l = left(i);
  const int r = right(i);

  int largest = 0;
  if (l <= H && A[l] > A[i]) {
    largest = l;
  } else {
    largest = i;
  }

  if (r <= H && A[r] > A[largest]) {
    largest = r;
  }
    
  if (largest != i) {
    swap(A[i], A[largest]);  
    maxHeapify(A, largest);
  }
}

static void heapIncreaseKey(vector<int>& A, int i, int key) {
  if (key < A[i]) {
    printf("エラー：新しいキーは現在のキーより小さい\n");
    return;
  }
  A[i] = key;
  while (i > 1 && A[parent(i)] < A[i]) {
    swap(A[i], A[parent(i)]);
    i = parent(i);
  }
}

static void insert(vector<int>& A, int key) {
  H++;
  A[H] = -INFTY;
  heapIncreaseKey(A, H, key);
}

static int extract(vector<int>& A) {
  if (H < 1) {
    printf("エラー：ヒープアンダーフロー\n");
    return 0;
  }
  int max = A[1];
  A[1] = A[H--];
  maxHeapify(A, 1);

  return max;
}

int main() {
  string command;
  int v;
  while (true) {
    cin >> command;
    if (command[0] == 'i') {
      scanf("%d", &v);
      insert(A, v);
    } else if (command[0] == 'e' && command[1] == 'x') {
      cout << extract(A) << endl;
    } else {
      break;
    }
  }
  return 0;
}