12.2 グラフの表現

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

#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;
}

11.4 連鎖行列積(写経編)

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

写経だけだとアレなので、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;
}

11.3 最長共通部分列

またもや写経です。

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

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

#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;
}

11.2 フィボナッチ数列

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

#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;
}

10.4 優先度付きキュー(写経編)

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;
}

10.3 最大・最小ヒープ

buildMaxHeap() と maxHeapify() が問題文に書いてあり、そのままの実装となります。

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

using namespace std;
 
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);

  const int H = A.size() - 1;
  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 buildMaxHeap(vector<int>& A) {
  const int H = A.size() - 1;
  for (int i = H / 2; i > 0; i--) {
    maxHeapify(A, i);
  }
}

static vector<int> A;

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

  A.resize(H + 1);

  int k;
  for (int i = 1; i <= H; i++) {
    cin >> k;
    A[i] = k;
  }
  
  buildMaxHeap(A);
  
  for (int i = 1; i <= H; i++) {
    cout << " " << A[i];
  }
  cout << endl;

  return 0;
}

10.2 完全二分木

ヒープ編に突入。今回は問題文通りの実装です。parent, left, right が単純な計算で決定するのが面白いですね。なお、解説の実装では、木の実装が int の配列になっており、自分の実装は無駄な箇所が多々あります。

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

using namespace std;

struct Node {
  int key;
  Node* parent;
  Node* left;
  Node* right;
  
  Node(int key = -1) : key(key), parent(nullptr), left(nullptr), right(nullptr) {};
};

static vector<Node> tree;

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

  tree.resize(h + 1);

  int k;
  for (int i = 1; i < tree.size(); i++) {
    cin >> k;
    tree[i].key = k;
  }

  int parent, left, right;
  for (int i = 1; i < tree.size(); i++) {
    parent = i / 2;
    if (parent != 0) {
      tree[i].parent = &tree[parent];
    }
    left = 2 * i;
    if (left < tree.size()) {
      tree[i].left = &tree[left];
    }
    right = 2 * i + 1;
    if (right < tree.size()) {
      tree[i].right = &tree[right];    
    }
  }

  for (int i = 1; i < tree.size(); i++) {
    auto& node = tree[i];
    printf("node %d: key = %d, ", i, node.key);
    if (node.parent) {
      printf("parent key = %d, ", node.parent->key);
    }
    if (node.left) {
      printf("left key = %d, ", node.left->key);
    }
    if (node.right) {
      printf("right key = %d, ", node.right->key);
    }
    printf("\n");
  }

  return 0;
}