ei1333の日記

ぺこい

九州大学プログラミングコンテスト2018 (QUPC2018) EGJ問題

10/20(土) に開催された 九州大学プログラミングコンテスト2018 (QUPC2018) の EGJ 問題の writer でした。

beta.atcoder.jp

各問題の解説は既に公開しているので、問題についての適当なコメントとコードを載せていこうと思います。

QUPC2018解説.pdf - Google ドライブ

treeone.hatenablog.com

E 問題

beta.atcoder.jp

原案は木の場合(重心分解をする) だったので問題名がTreeone なんですが, こどふぉではないことに気づいて列になった.

変更後の値の制約書いたほうが良くない? ってなったので適当につけたら破滅した.

くりんぺっとさんに感謝.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int main() {
 int N, K;
 int64 A[200001] = {}, rev[200002] = {};
 map< int64, int > sum1, sum2;
 int64 ret = 0, all = 0;

 cin >> N;
 for(int i = 1; i <= N; i++) {
   cin >> A[i];
   A[i] += A[i - 1];
 }
 for(int i = N; i >= 0; i--) {
   rev[i + 1] = sum1[A[i]]++;
 }
 for(int i = 0; i <= N; i++) {
   rev[i + 1] += rev[i];
   ret = max(ret, rev[i] - all);
   all += sum2[A[i]]++;
 }
 cout << all - ret << endl;
}

G 問題

beta.atcoder.jp

FはFのFlowなのでフローを出したいねという気持ちになって, 無向グラフで制約小さいverのやつ(最小カットするだけ)が原案.

部分点を考えてたら木の場合はどうなるねんという話になって, おもしろかったので木の場合で出すことになった. シンプルな木DP.

1 億人に解かれると思っていたけど, 18 人にしか解かれなかった.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 INF = 1LL << 60;

struct edge { int to, cost; };

int N, X, Y;
vector< edge > g[500000];
int t[500000];

pair< int64, int64 > dfs(int idx, int par) {
  int64 latte = 0, malta = 0;
  for(auto &e : g[idx]) {
    if(e.to == par) continue;
    auto get = dfs(e.to, idx);
    latte += min(get.first, get.second + e.cost);
    malta += min(get.first + e.cost, get.second);
  }
  if(t[idx] == 1) latte = INF;
  else if(t[idx] == 2) malta = INF;
  return make_pair(latte, malta);
}

int main() {
  scanf("%d %d %d", &N, &X, &Y);
  for(int i = 1; i < N; i++) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    --x, --y;
    g[x].emplace_back((edge){y, z});
    g[y].emplace_back((edge){x, z});
  }
  for(int i = 0; i < X; i++) {
    int x;
    scanf("%d", &x);
    --x;
    t[x] = 1;
  }
  for(int i = 0; i < Y; i++) {
    int x;
    scanf("%d", &x);
    --x;
    t[x] = 2;
  }
  auto ret = dfs(0, -1);
  printf("%lld\n", min(ret.first, ret.second));
}

J 問題

beta.atcoder.jp

直前に用意していた最終問題が炎上してしまったらしく, 悲しい気持ちになりながら生やした問題. 炎上しない.

Painting | Aizu Online Judge を参考に作問した.

最後くらい 実 家 い つ も の を置いてもいいよね. いつものだったので結構解かれた.

#include <bits/stdc++.h>

using namespace std;

int main() {
  string S, T[200000];
  vector< int > que[200001];
  int Q;

  cin >> S >> Q;
  int N = (int) S.size();
  for(int i = 0; i < Q; i++) {
    cin >> T[i];
    que[T[i].size()].push_back(i);
  }

  bool beet[200000];
  for(int i = 1; i < N; i++) beet[i] = S[i - 1] != S[i];

  int ans[200000] = {};
  for(int i = 1; i < 200001; i++) {
    if(que[i].empty()) continue;
    vector< vector< int > > sum(2, vector< int >(i));
    for(int j = 1; j < N; j++) sum[beet[j]][j % i]++;
    for(auto _ : que[i]) {
      const string &t = T[_];
      char pv = t.back();
      for(int j = 0; j < i; pv = t[j++]) ans[_] += sum[pv == t[j]][j];
      ans[_] += (t[0] != S[0]);
    }
  }

  for(int i = 0; i < Q; i++) cout << (ans[i] + 1) / 2 << endl;
}