パソコン甲子園2018 プログラミング部門 解答例

pre_q1.cpp

// (華氏 - 30) ÷ 2 の計算
int to_celsius(int fahrenheit) { return (fahrenheit - 30) / 2; }

#include <iostream>

int main() {
  // この 3 行は高速化テンプレ
  using namespace std;
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

　// 入出力
  int F;
  cin >> F;
  cout << to_celsius(F) << "\n";
}
// 以下もこんな感じで書いていくね

pre_q2.cpp

int distance(int x1, int x2) {
  // 距離の差を求めて、
  int dist = x1 - x2;
  // 絶対値を返すだけ
  if (dist < 0) {
    return -dist;
  }
  return dist;
}


#include <iostream>

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

  int x1, x2;
  cin >> x1 >> x2;
  cout << distance(x1, x2) << "\n";
}

pre_q3.cpp

#include <cmath>

int cake_per_1(int people, int cake) {
  // ケーキを人数ぶんに分けて、小数点以下は切り上げる
  return std::ceil(static_cast<double>(cake) / people);
}

#include <iostream>
#include <numeric>

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

  int N, C;
  cin >> N >> C;
  int P = 0;
  for (int i = 0; i < C; ++i) {
    int pi;
    cin >> pi;
    P += pi;
  }
  // N + 1 で全員の人数になるので注意
  cout << cake_per_1(N + 1, P) << "\n";
}

pre_q4.cpp

int water_cost(int liter_price, int half_liter_price, int needed) {
  // 1 リットルより 0.5 リットルのほうが割安 (liter_price >= half_price * 2)
  // であれば、すべて 0.5 リットルを買うだけでいい
  if (liter_price >= half_liter_price * 2) {
    int cost = needed / 500 * half_liter_price; // mL / 500 * 円/0.5L
    // 0.5 リットルを足す必要があればその値段を足す
    if (0 < needed % 500) {
      cost += half_liter_price;
    }
    return cost;
  }

  // そうでなければ、1 リットル以上をすべて 1 リットルにする
  int cost = needed / 1000 * liter_price; // mL / 1000 * 円/L
  // 0.5 リットルを足す必要があればその値段を足す
  if (0 < needed % 500) {
    cost += half_liter_price;
  }
  return cost;
}

#include <iostream>

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

  int A, B, X;
  cin >> A >> B >> X;
  cout << water_cost(A, B, X) << "\n";
}

pre_q5.cpp

int sum_digit(int n) {
  int sum = 0;
  for (int k = 100000000; 0 < k; k /= 10) {
    sum += n / k;
    n %= k;
  }
  return sum;
}

#include <cmath>

int count_dudeney(int a, int n, int max) {
  int count = 0;
  // 8 秒もあるので全パターンを調べても間に合う
  for (int x = 1; x <= max; ++x) {
    int y = sum_digit(x);
    if (x == std::pow(y + a, n)) {
      ++count;
    }
  }
  return count;
}

#include <iostream>

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

  int a, n, m;
  cin >> a >> n >> m;
  cout << count_dudeney(a, n, m) << "\n";
}

pre_q6.cpp

#include <algorithm>
#include <numeric>
#include <vector>

int bozo_sort(std::vector<int> &data,
              std::vector<std::pair<size_t, size_t>> ops) {
  std::vector<int> sorted(data);
  std::sort(sorted.begin(), sorted.end());

  // ソート済みと位置が同じ要素の個数を数える
  int same_nums = std::inner_product(data.begin(), data.end(), sorted.begin(),
                                     0, [](int a, int b) { return a + b; },
                                     [](int a, int b) {
                                       if (a == b) {
                                         return 1;
                                       }
                                       return 0;
                                     });

  if (same_nums == data.size()) {
    return 0;
  }

  // same_nums の変化でソートできているか判別する
  // std::is_sorted の判定では O(NQ) なので間に合わない
  for (int op_i = 0; op_i < ops.size(); ++op_i) {
    auto [x, y] = ops[op_i]; // 構造化束縛
    --x;                     // 1 始まりを 0 始まりに
    --y;                     // 1 始まりを 0 始まりに

    if (data[x] == sorted[x]) {
      --same_nums;
    }
    if (data[y] == sorted[y]) {
      --same_nums;
    }

    std::swap(data[x], data[y]);

    if (data[x] == sorted[x]) {
      ++same_nums;
    }
    if (data[y] == sorted[y]) {
      ++same_nums;
    }

    if (same_nums == data.size()) {
      return op_i + 1;
    }
  }

  return -1;
}

#include <iostream>

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

  int N;
  cin >> N;
  std::vector<int> a(N);
  for (auto &e : a) {
    cin >> e;
  }

  int Q;
  cin >> Q;
  std::vector<std::pair<size_t, size_t>> xy(Q);
  for (auto &e : xy) {
    cin >> e.first >> e.second;
  }
  cout << bozo_sort(a, xy) << "\n";
}

pre_q7.cpp

#include <vector>

long portal_ways(std::vector<std::vector<size_t>> const &portals) {
  std::vector<long> dp(portals.size());
  dp[0] = 1; // 最初の星に行けるのは 1 通り

  for (auto now = 0; now < portals.size(); ++now) {
    for (auto next : portals[now]) {
      dp[next] += dp[now]; // 行ける星すべてに場合の数を伝播
      dp[next] %= 1'000'000'007; // ここで剰余を取らないと爆発する
    }
  }

  return dp.back() % 1'000'000'007;
}

#include <iostream>

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

  int N;
  cin >> N;
  string S, T;
  cin >> S >> T;
  
  // portals[planet - 1] が planet 番目から行ける星のリストになるようにする
  vector<vector<size_t>> portals(N);
  for (size_t entrance_i = 0; entrance_i < portals.size(); ++entrance_i) {
    auto entrance = S[entrance_i];
    for (size_t exit_i = entrance_i + 1; exit_i < portals.size(); ++exit_i) {
      auto exit = T[exit_i];
      if (entrance == exit) {
        portals[entrance_i].push_back(exit_i);
      }
    }
  }
  cout << portal_ways(portals) << "\n";
}

pre_q8.cpp

#include <algorithm>
#include <numeric>
#include <vector>

long max_tax(std::vector<std::vector<long>> &customers) {
  std::vector<long> targets;
  for (auto line_i = 0; line_i < customers.size(); ++line_i) {
    // 各列の車は任意の客を取れるので
    // 各列を降順ソート
    std::sort(customers[line_i].begin(), customers[line_i].end(),
              [](long a, long b) { return a > b; });
    // 前の列の車も考えると、列の番号と同じ数だけ取れば最大になる
    targets.insert(targets.end(), customers[line_i].begin(),
                   customers[line_i].begin() + line_i + 1);
  }

  // 各列から取れるものをまとめて降順ソート
  std::sort(targets.begin(), targets.end(),
            [](long a, long b) { return a > b; });

  // 大きい順に N 個を合計する
  return std::accumulate(targets.begin(), targets.begin() + customers.size(),
                         0L);
}

#include <iostream>

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

  int N;
  cin >> N;
  std::vector<std::vector<long>> customers(N);
  for (auto &line : customers) {
    int M;
    cin >> M;
    for (int i = 0; i < M; ++i) {
      long customer;
      cin >> customer;
      line.push_back(customer);
    }
  }

  cout << max_tax(customers) << "\n";
}

pre_q9.cpp

#include <algorithm>
#include <map>
#include <numeric>
#include <set>
#include <vector>

std::vector<std::pair<double, double>>
points_to_lines(std::vector<std::pair<int, int>> const &points) {
  std::vector<std::pair<double, double>> lines;
  lines.reserve(points.size() * (points.size() - 1) / 2);
  for (auto a_i = 0; a_i < points.size(); ++a_i) {
    for (auto b_i = a_i + 1; b_i < points.size(); ++b_i) {
      auto [ax, ay] = points[a_i];
      auto [bx, by] = points[b_i];
      double dX = ax - bx;
      if (dX == 0) { // 傾きが ∞ なやつは無視
        continue;
      }
      lines.push_back({(ay - by) / dX, (ax * by - ay * bx) / dX});
    }
  }
  return lines;
}

void to_max(long &target, long value) {
  if (target < value) {
    target = value;
  }
}

// 参考: https://www.hamayanhamayan.com/entry/2018/09/30/203639
bool exists_k_point_on_same_line(
    int K, std::vector<std::pair<int, int>> const &points) {
  // 点をそれぞれの間の線 (傾き, 切片) に変換
  auto lines = points_to_lines(points);
  std::sort(lines.begin(), lines.end());

  // 線の std::set を用意
  std::set<std::pair<double, double>> distinct(lines.begin(), lines.end());

  // 同じ線の数を最大化する
  long count = std::accumulate(
      distinct.begin(), distinct.end(), 0L,
      [&lines](long const &e, std::pair<double, double> const &point) {
        return std::max(e, std::count(lines.begin(), lines.end(), point));
      });

  // 条件を頂点から線にする必要がある
  // K 個の頂点に対して、頂点間の線の数は K(K - 1) / 2
  if (K * (K - 1) / 2 <= count) {
    return true;
  }

  // ここからは同じ X 座標の点の数を調べる
  std::map<int, int> x_count;
  for (auto point : points) {
    ++x_count[point.first];
  }
  for (auto x : x_count) {
    if (K <= x.second) {
      return true;
    }
  }

  return false;
}

#include <iostream>

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

  int N, K;
  cin >> N >> K;
  vector<pair<int, int>> points(N);
  for (auto &point : points) {
    cin >> point.first >> point.second;
  }

  if (exists_k_point_on_same_line(K, points)) {
    cout << "1\n";
  } else {
    cout << "0\n";
  }
}