10/20(土) に開催された 九州大学プログラミングコンテスト2018 (QUPC2018) の EGJ 問題の writer でした。
各問題の解説は既に公開しているので、問題についての適当なコメントとコードを載せていこうと思います。
E 問題
原案は木の場合(重心分解をする) だったので問題名がTreeone なんですが, こどふぉではないことに気づいて列になった.
変更後の値の制約書いたほうが良くない? ってなったので適当につけたら破滅した.
testerやってたんですが、一番の仕事はEの原案にあった「絶対値1e9以下の整数に変更できる」を消させたことで、これがあるとN^2ですら解けるか怪しい
— くりんぺっと (@climpet) October 20, 2018
くりんぺっとさんに感謝.
#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 問題
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 問題
直前に用意していた最終問題が炎上してしまったらしく, 悲しい気持ちになりながら生やした問題. 炎上しない.
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; }