８．３ 二分木の表現（手動編）

高さの算出が前回と違うところですね。構造体にメソッドがつけられることを忘れていたので若干処理を移動しました。あまりキレイではないですがこれくらいで。。

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

using namespace std;

static const string ROOT = "root";
static const string INTERNAL_NODE = "internal node";
static const string LEAF = "leaf";

struct Node {
  int id;
  int parent;
  int depth;
  int height;
  int left;
  int right;

  Node() : id(), parent(-1), depth(0), height(0), left(-1), right(-1) {}

  bool hasChild() const {
    return left != -1 || right != -1; 
  }

  int getDegree() const {
    if (hasChild()) {
      if (left != -1 && right != -1) {
       return 2;
      } else {
        return 1;
      }
    } else {
      return 0;
    }
  }

  const string& getType() const {
    if (parent == -1) {
      return ROOT;
    } else if (hasChild()) {
    return INTERNAL_NODE;
    } else {
      return LEAF;
    }
  }
};

static vector<Node> TREE(25);

static void inputNode(Node& node, int id) {
  node.id = id;
  cin >> node.left >> node.right;
}

static void setDepth(vector<Node>& tree, Node& node) {
  if (node.left != -1) {
    tree[node.left].depth = node.depth + 1;
    setDepth(tree, tree[node.left]);
  }
  
  if (node.right != -1) {
    tree[node.right].depth = node.depth + 1;
    setDepth(tree, tree[node.right]);
  }
}

static int getHeight(const vector<Node>& tree, const Node& node) {
  int height = 0, leftHeight = 0, rightHeight = 0;
  if (node.hasChild()) {
    if (node.left != -1) {
      leftHeight = getHeight(tree, tree[node.left]) + 1;
    }
    if (node.right != -1) {
      rightHeight = getHeight(tree, tree[node.right]) + 1;
    }
    height = max(leftHeight, rightHeight);
  }
  return height;
}

static int getSibling(const vector<Node>& tree, const Node& node) {
  if (node.parent == -1) {
    return -1;
  } else {
    const Node& parentNode = tree[node.parent];
    if (parentNode.left == node.id) {
      return parentNode.right;
    } else {
      return parentNode.left;
    }
  }
}

static void setupTree(vector<Node>& tree, int num) {
  for (int i = 0; i < num; i++) {
    Node& node = tree[i];
    if (node.left != -1) {
      tree[node.left].parent = node.id;
      tree[node.left].depth = node.depth + 1;
      setDepth(tree, tree[node.left]);
    }
    if (node.right != -1) {
      tree[node.right].parent = node.id;
      tree[node.right].depth = node.depth + 1;
      setDepth(tree, tree[node.right]);
    }
    node.height = getHeight(tree, node);
  }
}

static void printTree(const vector<Node>& tree, int num) {
  int depth = 0, sibling = 0;
  for (int i = 0; i < num; i++) {
    sibling = getSibling(tree, tree[i]);
    const string& type = tree[i].getType();
    printf("node %d: parent = %d, sibling = %d, degree = %d", i, tree[i].parent, sibling, tree[i].getDegree());
    printf(", depth = %d, height = %d, %s\n", tree[i].depth, tree[i].height, type.c_str());
  }
}

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

  int id;
  for (int i = 0; i < n; i++) {
    cin >> id;
    inputNode(TREE[id], id);
  }
  
  setupTree(TREE, n);
  printTree(TREE, n);

  return 0;
}

８．２ 根付き木の表現（手動編）

解説を見ないで書いた版です。構造体 Node の子の表現を vector にしました。しかし解説では「左右の子のみでも解ける方法」となっており、vector は仰々しかったかなと。。深さの算出は再帰です。子の数が０になるまで回します。

節の入力時の番号が、０からのインクリメンタル値と思い込んでいて、なかなか答えが合わずに苦労しました（実際はランダムで入力される）。

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

using namespace std;

struct Node {
  int id;
  int parent;
  int depth;
  vector<int> child;
  
  Node() : id(), parent(-1), depth(0), child(0, 0) {}
};

static vector<Node> TREE(100000);

static void inputNode(Node& node, int id, int k) {
  node.id = id;

  int c;
  for (int i = 0; i < k; i++) {
    cin >> c;
    node.child.push_back(c);
  }
}

static const string ROOT = "root";
static const string INTERNAL_NODE = "internal node";
static const string LEAF = "leaf";

static const string& getNodeType(const Node& node) {
  if (node.parent == -1) {
    return ROOT;
  } else if (node.child.size() != 0) {
    return INTERNAL_NODE;
  } else {
    return LEAF;
  }
}

static void setDepth(vector<Node>& tree, Node& node) {
  for (int i : node.child) {
    tree[i].depth = node.depth + 1;
    setDepth(tree, tree[i]);
  }
}

static void setupTree(vector<Node>& tree, int num) {
  for (int i = 0; i < num; i++) {
    const Node& node = tree[i];
    for (int j : node.child) {
      tree[j].parent = node.id;
      tree[j].depth = node.depth + 1;
      setDepth(tree, tree[j]);
    }
  }
}

static void printTree(const vector<Node>& tree, int num) {
  int node, parent = -1, depth = 0;

  for (int i = 0; i < num; i++) {
    const string type = getNodeType(tree[i]);
    printf("node %d: parent = %d, depth = %d, %s, [", i, tree[i].parent, tree[i].depth, type.c_str());
    for (int j  = 0; j < tree[i].child.size(); j++) {
      if (j != 0) {
        printf(", "); 
      }
      printf("%d", tree[i].child[j]);
    }
    printf("]\n");
  }
}

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

  int id, k;
  for (int i = 0; i < n; i++) {
    cin >> id >> k;
    inputNode(TREE[id], id, k);
  }
  
  setupTree(TREE, n);
  printTree(TREE, n);

  return 0;
}

７．７ 最小コストソート

最小値を使って交換し、その上で計算式の算出と反例まで考えないと解けない難問。とても難しいので今回は写経です。本書内の回答例は変数名がかなり分かりづらいので、ちょっと直してはいます。また、ソート済のテーブルの先頭の値が最小値なので、そのまま使っています(B[0])。

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

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i];
   }
}

static void printArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cout << ((i != 0) ? " " : "") << A[i];
  }
  cout << endl;
}

static const size_t NMAX = 1000;
static const size_t VMAX = 10000;

static vector<int> A(NMAX), B(NMAX);
static vector<int> TABLE(VMAX + 1, 0);
static vector<bool> SORTED(NMAX, false);

static inline void printArray(vector<bool>& A, int num) {
  for (int i = 0; i < num; i++) {
    cout << ((i == 0) ? "" : " ") << A[i];
  } 
  cout << endl;
}

static inline int solve(int A[], int num) {
  B.assign(&A[0], &A[num]);
  sort(B.begin(), B.end());

  for (int i = 0; i < num; i++) {
    TABLE[B[i]] = i;
  }

  int ans = 0;
  for (int i = 0; i < num; i++) {
    if (SORTED[i]) {
      continue;
    }
    
    int cursor = i;
    int total = 0;
    int min = VMAX;
    int numInCycle = 0;
    while (true) {
      SORTED[cursor] = true;
      numInCycle++;
      min = std::min(min, A[cursor]);
      total += A[cursor];
      cursor = TABLE[A[cursor]];
      if (SORTED[cursor]) {
        break;     
      }
    }
    ans += std::min(total + (numInCycle - 2) * min, min + total + (numInCycle + 1) * B[0]);
  }

  return ans;
}

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

  inputArray(&A[0], n);

  const int ans = solve(&A[0], n);
  
  cout << ans << endl;

  return 0;
}

７．６ 反転数

７．５は STL のソートの話だったので、基本的にはスルーですが、std::stable_sort が使えることを知りました。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i];
   }
}

static vector<int> L(100000 + 1);
static vector<int> R(100000 + 1);

static uint64_t inversions = 0;

static inline void merge(int A[], int left, int mid, int right) {
  int n1 = mid - left;
  int n2 = right - mid;

  L.assign(&A[left], &A[left + n1]);
  R.assign(&A[mid], &A[mid + n2]);
  L[n1] = R[n2] = INT32_MAX;

  for (int i = 0, j = 0, k = left; k < right; k++) {
    if (L[i] <= R[j]) {
      A[k] = L[i];
      i++;
    } else {
      A[k] = R[j];
      j++;
      inversions += n1 - i;
    }
  } 
}

static inline void mergeSort(int A[], int left, int right) {
  if (left + 1 < right) {
    int mid = (left + right) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  } 
}

static vector<int> A(200000);

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

  inputArray(&A[0], n);

  mergeSort(&A[0], 0, n);
  
  cout << inversions << endl;
    
  return 0;
}

７．４ 計数ソート

配列 A,B を 1 オリジンにしないといけない理由を理解しないままコーディングし、その途中でインデックスがずれまくったために答えが合わず、無駄な時間を費やしてしまいました。また、A, B の配列のサイズを間違えていたため、Runtime Error を頻発させてしまいました。色々と申し訳ない感じに。。

#include <iostream>
#include <vector>

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i];
   }
}

static void printArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cout << ((i != 0) ? " " : "") << A[i];
  }
  cout << endl;
}

static const int NMAX = 10000;
static vector<int> C(NMAX + 1, 0);

static inline void countingSort(int A[], int B[], int num) {
  for (int i = 0; i < num; i++) {
    C[A[i + 1]]++;
  }
  for (int i = 1; i <= NMAX; i++) {
    C[i] = C[i] + C[i - 1];
  }
// 前から検索すると安定ソートにはならない
// for (int i = 1; i <= num; i++) {
  for (int i = num; i > 0; i--) {
    B[C[A[i]]] = A[i];
    C[A[i]]--;
  }
}  

static vector<int> A(2000000 + 1), B(2000000 + 1);

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

  inputArray(&A[1], n);

  countingSort(&A[0], &B[0], n);

  printArray(&B[1], n);
    
  return 0;
}

７．３ クィックソート

悩んだのは stable の判定ってどうするの？という部分です。過去の安定ソートと比較する、というのは思いつきませんでした。余計な時間がかかりそうですし。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>

using namespace std;

struct Card {
    char suit;
    int value;
    Card() : suit(), value() { }
  bool operator==(const Card& rhs) const {
    return this->suit == rhs.suit && this->value == rhs.value;
  }
  bool operator!=(const Card& rhs) const {
    return !(this->operator==(rhs));
  }
};

static bool isStable(Card in[], Card out[], int num) {
  for (int i = 0; i < num; i++) {
    if (in[i] != out[i]) {
      return false;
    }
  }
  return true;
}

static void inputArray(Card A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i].suit >> A[i].value;
   }
}

static void printArray(Card A[], int num) {
  for (int i = 0; i < num; i++) {
    cout << A[i].suit << ' ' << A[i].value << endl;
  }
}

static vector<Card> L(50000 + 1);
static vector<Card> R(50000 + 1);

static inline void merge(Card A[], int left, int mid, int right) {
  int n1 = mid - left;
  int n2 = right - mid;

  L.assign(&A[left], &A[left + n1]);
  R.assign(&A[mid], &A[mid + n2]);
  L[n1].value = R[n2].value = INT32_MAX;

  for (int i = 0, j = 0, k = left; k < right; k++) {
    if (L[i].value <= R[j].value) {
      A[k] = L[i];
      i++;
    } else {
      A[k] = R[j];
      j++;
    }
  } 
}

static inline void mergeSort(Card A[], int left, int right) {
  if (left + 1 < right) {
    int mid = (left + right) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  } 
}

static int partition(Card A[], int p, int r) {
  int x = A[r].value;
  int i = p - 1;
  for (int j = p; j < r; j++) {
    if (A[j].value <= x) {
      i++;
      swap(A[i], A[j]);
    }
  }
  swap(A[i + 1], A[r]);
  return i + 1; 
}

static inline void quickSort(Card A[], int p, int r) {
  if (p < r) {
    int q = partition(A, p, r);
    quickSort(A, p, q - 1);
    quickSort(A, q + 1, r);
  }
}

static vector<Card> A(100000);
static vector<Card> B(100000);

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

  inputArray(&A[0], n);
  B = A;

  quickSort(&A[0], 0, n - 1);
  mergeSort(&B[0], 0, n);
  
  bool stable = isStable(&A[0], &B[0], n);
  cout << (stable ? "Stable" : "Not stable") << endl;
  
  printArray(&A[0], n);
    
  return 0;
}

７．２ パーティション

「パーティション処理を行うと何が嬉しいのか？」が書かれてないため、あまり達成感がないですが、とりあえず。

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

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i]; 
  }
}

static void printArray(int A[], int num, int q) {
  for (int i = 0; i < num; i++) {
    cout << (i != 0 ? " " : "");
    if (i != q) {
      cout << A[i];
    } else {
      cout << '[' << A[i] << ']';
    }
  }
  cout << endl; 
}

static int partition(int A[], int p, int r) {
  int x = A[r];
  int i = p - 1;
  for (int j = p; j < r; j++) {
    if (A[j] <= x) {
      i++;
      swap(A[i], A[j]);
    }
  }
  swap(A[i + 1], A[r]);
  return i + 1; 
}

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

  vector<int> A(n);
  inputArray(&A[0], n);
  
  int q = partition(&A[0], 0, n - 1);
  printArray(&A[0], n, q);
    
  return 0;
}