「第3回 RCO日本橋ハーフマラソン 予選」の復習

C++ マラソン 競技プログラミング

atcoder.jp

このコンテストに出たのですが、散々な結果だった。ただ、終わった後に流れてきた解法を見ると結構シンプルなものが多かったので、復習した。

A - ツーリストXの旅行計画

A - ツーリストXの旅行計画


分散が出てきてややこしい気持ちになるが、平均値を決め打ちすると、各辺のコストが固定の値になり、純粋な巡回セールスマン問題 (TSP) になる。

画像検索した感じだと 2-opt が初心者でも実装しやすそうに見えるので、実装してみた。

方針

  • 平均値を乱数で決め打ちする。
  • 最初は貪欲にとりあえず解を作る。スタート地点が決まっているので、スタート地点から、その都度、最もコストの低い辺を選びながら、移動していく。
  • 解に含まれている辺から 2 本選び、 2-opt 的に組み換える。これを全ての辺の組について試し、最もコストが減る組み合わせについて組み換える。これの組み換えは300回くらいやる。
  • これらを時間の限り繰り返し、最終的に一番良かった解を出力する。

最初の貪欲解

全くひねりなく、今いる頂点から一番低コストで行ける頂点に行く。

tuple<vector<size_t>, double> greedy() {
  double total_cost = 0.0;
  vector<size_t> res;
  vector<bool> vis(N, false);

  size_t cur = 0;
  vis[cur] = true;
  res.push_back(cur);

  REP(i, (N - 1)) {
    double cur_min = INF;
    size_t cur_next = N;
    REP(next, N) {
      if (vis[next]) {
        continue;
      }
      if (dist[cur][next] < cur_min) {
        cur_next = next;
        cur_min = dist[cur][next];
      }
    }

    total_cost += dist[cur][cur_next];
    res.push_back(cur_next);
    vis[cur_next] = true;
    cur = cur_next;
  }

  res.push_back(0);
  total_cost += dist[cur][0];

  return make_tuple(res, total_cost);
}

2-opt

Wikipedia を見ながら雰囲気で実装した。これも全くひねらず、全ての辺の組について組み換えてみて、一番コストを減らせる組について実際に組み換える。

double improve_2opt(vector<size_t>& path) {
  double cur_improvement = 0.0;
  size_t index_from = 0;
  size_t index_to = 0;

  REP(i, N) {
    auto from1 = path[i];
    auto to1 = path[i + 1];
    auto cost1 = dist[from1][to1];
    for (size_t j = i + 1; j < N; j++) {
      auto from2 = path[j];
      auto to2 = path[j + 1];
      auto cost2 = dist[from2][to2];

      auto prev_cost = cost1 + cost2;
      auto next_cost = dist[from1][from2] + dist[to1][to2];
      if (prev_cost > next_cost && prev_cost - next_cost > cur_improvement) {
        cur_improvement = prev_cost - next_cost;
        index_from = i + 1;
        index_to = j + 1;
      }
    }
  }
  if (index_from == index_to) {
    return 0.0;
  }

  reverse(path.begin() + index_from, path.begin() + index_to);
  return cur_improvement;
}

全体

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <iostream>
#include <iterator>
#include <tuple>
#include <vector>

using namespace std;

#define REP(i, n) for (size_t(i) = 0; (i) < (n); (i)++)

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
  out << "[" << p.first << ", " << p.second << "]";
  return out;
}

uint64_t xor_shift64(uint64_t* state) {
  uint64_t x = *state;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  *state = x;
  return x;
}

/* ここまでテンプレート */

const double INF = 1e18;

size_t N;
double X[200], Y[200];
double dist[200][200];

double calc_distance(double x1, double y1, double x2, double y2) {
  double dx = x1 - x2;
  double dy = y1 - y2;
  return sqrt(dx * dx + dy * dy);
}

double improve_2opt(vector<size_t>& path) {
  double cur_improvement = 0.0;
  size_t index_from = 0;
  size_t index_to = 0;

  REP(i, N) {
    auto from1 = path[i];
    auto to1 = path[i + 1];
    auto cost1 = dist[from1][to1];
    for (size_t j = i + 1; j < N; j++) {
      auto from2 = path[j];
      auto to2 = path[j + 1];
      auto cost2 = dist[from2][to2];

      auto prev_cost = cost1 + cost2;
      auto next_cost = dist[from1][from2] + dist[to1][to2];
      if (prev_cost > next_cost && prev_cost - next_cost > cur_improvement) {
        cur_improvement = prev_cost - next_cost;
        index_from = i + 1;
        index_to = j + 1;
      }
    }
  }
  if (index_from == index_to) {
    return 0.0;
  }

  reverse(path.begin() + index_from, path.begin() + index_to);
  return cur_improvement;
}

tuple<vector<size_t>, double> greedy() {
  double total_cost = 0.0;
  vector<size_t> res;
  vector<bool> vis(N, false);

  size_t cur = 0;
  vis[cur] = true;
  res.push_back(cur);

  REP(i, (N - 1)) {
    double cur_min = INF;
    size_t cur_next = N;
    REP(next, N) {
      if (vis[next]) {
        continue;
      }
      if (dist[cur][next] < cur_min) {
        cur_next = next;
        cur_min = dist[cur][next];
      }
    }

    total_cost += dist[cur][cur_next];
    res.push_back(cur_next);
    vis[cur_next] = true;
    cur = cur_next;
  }

  res.push_back(0);
  total_cost += dist[cur][0];

  return make_tuple(res, total_cost);
}

tuple<vector<size_t>, double> solve(double average) {
  REP(i, N) REP(j, N) {
    auto d = calc_distance(X[i], Y[i], X[j], Y[j]);
    dist[i][j] = (d - average) * (d - average);
    dist[j][i] = dist[i][j];
  }

  vector<size_t> path;
  double total_cost;
  tie(path, total_cost) = greedy();

  REP(i, 300) {
    double improvement = improve_2opt(path);
    if (improvement < 1e-9) {
      break;
    }
    assert(total_cost >= improvement);
    total_cost -= improvement;
  }
  return make_tuple(path, total_cost);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  auto start = chrono::system_clock::now();

  cin >> N;
  REP(i, N) { cin >> X[i] >> Y[i]; }

  uint64_t random_state = 71;

  vector<vector<size_t>> paths;
  vector<tuple<double, size_t>> costs;
  while (true) {
    double r = xor_shift64(&random_state);
    r /= numeric_limits<uint64_t>::max();

    double average = 200.0 + r * 200.0;
    vector<size_t> path;
    double cost;
    tie(path, cost) = solve(average);
    costs.emplace_back(cost, paths.size());
    paths.emplace_back(path);

    auto ms = chrono::duration_cast<chrono::milliseconds>(
                  chrono::system_clock::now() - start)
                  .count();
    if (ms > 1900) {
      break;
    }
  }
  sort(costs.begin(), costs.end());

  size_t min_cost_index = get<1>(costs[0]);

  const auto& path = paths[min_cost_index];
  REP(i, N) { cout << path[i] << endl; }
}

結果

Submission #4246661 - 第3回 RCO日本橋ハーフマラソン 予選

これで 3766621 点になる。コンテスト本番だと8位くらい。

B - ファーマーXの収穫計画

B - ファーマーXの収穫計画

各マスの数字は一様乱数で決まっているので 8, 7, 6 を思考停止で全部 9 にしてしまっても 1700 手くらいで済みそうという考察が出来るらしい（すごい）。9の島は9個以上の要素が連なっていないと回収できないので、小さい島は他の島と頑張って接続したい。

方針

  • 8, 7, 6 を全て 9 にしてしまう。
  • 小さい島からダイクストラでつなげていって大きい島になるようにする。
  • 一気に回収する。

コード

ビジュアライザを見た限り微妙にバグっているが、疲れたので解散。

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <iostream>
#include <iterator>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;

#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
  out << "[" << p.first << ", " << p.second << "]";
  return out;
}

uint64_t xor_shift64(uint64_t* state) {
  uint64_t x = *state;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  *state = x;
  return x;
}

// --- template ---

class UnionFind {
 private:
  struct nodeinfo {
    int par;
    int rank;
    int size;
    nodeinfo(int p) : par(p), rank(0), size(1) {}
  };
  std::vector<nodeinfo> node;

 public:
  UnionFind(int n) : node() {
    node.reserve(n);
    for (int i = 0; i < n; ++i) {
      node.push_back(nodeinfo(i));
    }
  }
  int root(int x) {
    if (node[x].par == x) {
      return x;
    }
    return node[x].par = root(node[x].par);
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      return;
    }
    if (node[x].rank < node[y].rank) {
      node[x].par = y;
      node[y].size += node[x].size;
      node[x].size = 0;
    } else {
      node[y].par = x;
      node[x].size += node[y].size;
      node[y].size = 0;
      if (node[x].rank == node[y].rank) {
        ++node[x].rank;
      }
    }
  }

  bool is_same_set(int x, int y) { return root(x) == root(y); }

  int size(int x) {
    x = root(x);
    return node[x].size;
  }
};

using State = tuple<double, int, int>;
const int DX[] = {0, 0, 1, -1};
const int DY[] = {1, -1, 0, 0};
const int INF = 1e9;

int N, M;
int A[50][50];

auto backward(vector<vector<double>>& dist, int i, int j) {
  vector<tuple<int, int>> ans;
  while (dist[i][j] > 0) {
    auto cur_min = dist[i][j];
    assert(cur_min < INF);
    tuple<int, int> next = make_tuple(i, j);

    REP(d, 4) {
      int ni = i + DX[d];
      int nj = j + DY[d];
      if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;

      if (dist[ni][nj] < cur_min) {
        next = make_tuple(ni, nj);
        cur_min = dist[ni][nj];
      }
    }

    int ni, nj;
    tie(ni, nj) = next;

    assert(ni != i || nj != j);
    dist[i][j] = INF;
    ans.emplace_back(ni, nj);
    i = ni;
    j = nj;
  }

  return ans;
}

vector<tuple<int, int>> dijkstra(int si, int sj, UnionFind& uf) {
  const int start_size = uf.size(si * N + sj);

  priority_queue<State, vector<State>, greater<State>> q;
  vector<vector<double>> dist(N, vector<double>(N, INF));
  dist[si][sj] = 0;
  q.emplace(0, si, sj);
  while (q.size() != 0) {
    int cost, i, j;
    tie(cost, i, j) = q.top();
    q.pop();

    if (A[i][j] == 9 && uf.size(i * N + j) + start_size >= 9) {
      return backward(dist, i, j);
    }

    REP(d, 4) {
      int ni = i + DX[d];
      int nj = j + DY[d];
      if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
      double w = 9.00001 - A[ni][nj];
      if (dist[ni][nj] > dist[i][j] + w) {
        dist[ni][nj] = dist[i][j] + w;
        q.emplace(dist[ni][nj], ni, nj);
      }
    }
  }

  return {};
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  vector<tuple<int, int, int>> ans;

  cin >> N >> M;
  REP(i, N) REP(j, N) {
    cin >> A[i][j];
    auto cost = 9 - A[i][j];
    if (cost <= 3 && cost + ans.size() <= M) {
      A[i][j] += cost;
      REP(z, cost) ans.emplace_back(1, i, j);
    }
  }

  UnionFind uf(N * N);
  REP(i, N) REP(j, N) REP(d, 4) {
    int ni = i + DX[d];
    int nj = j + DY[d];
    if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
    if (A[i][j] != A[ni][nj]) continue;
    int from = i * N + j;
    int to = ni * N + nj;
    uf.unite(from, to);
  }

  vector<bool> started(N * N, false);
  vector<vector<tuple<int, int>>> paths;
  vector<tuple<double, int, int>> costs;
  REP(i, N) REP(j, N) {
    if (A[i][j] != 9) continue;
    int x = i * N + j;
    x = uf.root(x);

    if (started[x]) continue;
    started[x] = true;

    int size = uf.size(i * N + j);
    if (size >= 9) continue;

    auto path = dijkstra(i, j, uf);
    int cost = 0;
    for (const auto& t : path) {
      int pi, pj;
      tie(pi, pj) = t;
      cost += 9 - A[pi][pj];
    }

    double cost_per_size = cost;
    cost_per_size /= size;
    costs.emplace_back(cost_per_size, cost, paths.size());
    paths.emplace_back(path);
  }

  sort(costs.begin(), costs.end());
  for (const auto& t : costs) {
    double cps;
    int cost;
    int index;
    tie(cps, cost, index) = t;
    const auto& path = paths[index];
    cost = 0;
    for (const auto& s : path) {
      int i, j;
      tie(i, j) = s;
      int turn = 9 - A[i][j];
      cost += turn;
    }

    if (cost + ans.size() >= M - 200) continue;
    for (const auto& s : path) {
      int i, j;
      tie(i, j) = s;
      int turn = 9 - A[i][j];
      REP(z, turn) ans.emplace_back(1, i, j);
      A[i][j] = 9;
    }
  }

  REP(i, N) REP(j, N) REP(d, 4) {
    int ni = i + DX[d];
    int nj = j + DY[d];
    if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
    if (A[i][j] != A[ni][nj]) continue;
    int from = i * N + j;
    int to = ni * N + nj;
    uf.unite(from, to);
  }

  vector<tuple<int, int, int>> candidates;
  vector<bool> done(N * N, false);
  REP(i, N) REP(j, N) {
    int x = i * N + j;
    x = uf.root(x);
    if (done[x]) continue;
    done[x] = true;
    if (uf.size(x) < A[i][j]) continue;
    int value = uf.size(x) * A[i][j];
    candidates.emplace_back(value, i, j);
  }

  sort(candidates.rbegin(), candidates.rend());
  for (const auto& t : candidates) {
    int v, i, j;
    tie(v, i, j) = t;
    ans.emplace_back(2, i, j);
    if (ans.size() == M) break;
  }

  for (const auto& t : ans) {
    int o, i, j;
    tie(o, i, j) = t;
    cout << o << " " << i << " " << j << "\n";
  }
}

結果

Submission #4247854 - 第3回 RCO日本橋ハーフマラソン 予選

503599点になる。本番100位くらい。僕は本番これの半分くらいしかとれなかったので、とりあえずよし。

6まで思考停止で9にしてしまうのはやりすぎ感はあるし、もう少し改善できそう。