７．７ 最小コストソート

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

７．１ マージソート

解説どおりの実装です。「Runtime Error」が頻発して悩みましたが、配列LRをスタックメモリに確保していたのが原因でした。再帰だからあっという間にスタックを食い尽くすんですね。

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

using namespace std;

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

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

static int compared = 0;

// ヒープメモリに確保すること.
static vector<uint32_t> L(250000);
static vector<uint32_t> R(250000);

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

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

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

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

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

  vector<uint32_t> A(n);
  inputArray(&A[0], n);
  
  mergeSort(&A[0], 0, n);
  
  printArray(&A[0], n);
  
  cout << compared << endl;
  
  return 0;
}

６．３ コッホ曲線

なかなか再帰脳になれず。。なお座標計算は本書を参照しました。プログラミングコンテストって、ここまで数学の知識を問われるんですかね？

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct P {
  double x;
  double y;
  P(double x, double y) : x(x) , y(y) {
  };
};

static inline void printP(const P& p) {
  cout << fixed << p.x << " " << p.y << endl; 
}

static inline double toRadian(double degree) {
  return degree / 180 * M_PI;
}

static inline void koch(int d, const P& p1, const P& p2) {
  if (d == 0) {
    return;
  }
  
  P s(p1.x + (p2.x - p1.x) / 3, p1.y + (p2.y - p1.y) / 3);
  P t(p1.x + 2 * ((p2.x - p1.x) / 3), p1.y + 2 * ((p2.y - p1.y) / 3));
  P u(
    (t.x - s.x) * cos(toRadian(60.0)) - (t.y - s.y) * sin(toRadian(60.0)) + s.x,
    (t.x - s.x) * sin(toRadian(60.0)) + (t.y - s.y) * cos(toRadian(60.0)) + s.y);
 
  koch(d - 1, p1, s);
  printP(s);
  koch(d - 1, s, u);
  printP(u);
  koch(d - 1, u, t);
  printP(t);
  koch(d - 1, t, p2);
}

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

  P p1(0.0, 0.0), p2(100.0, 0);

  printP(p1);
  koch(n, p1, p2);
  printP(p2);
  
  return 0;
}