九州大学プログラミングコンテスト2018 (QUPC2018) ABCDFHI問題
10/20(土) に開催された 九州大学プログラミングコンテスト2018 (QUPC2018) の ABCDFHI 問題の writer でした。
各問題の解説は既に公開しているので、問題についての適当なコメントとコードを載せていこうと思います。
EGJ 問題はこっち
A問題
問題ページ : A - QUPC
0 完防止用の問題。正解者は 275 人。
#include <iostream> using namespace std; int main(){ int n; cin >> n; cout << 2010 + 4 * n << endl; }
B問題
問題ページ : B - Tapu & Tapi
これ好きだけど、Wrong Answer が大量発生していて申し訳ない気持ちになった。(ア)
正解者は 199 人。
#include <bits/stdc++.h> using namespace std; int main(){ int q; cin >> q; for(int i = 0; i < q; i++){ long long a, b, c; cin >> a >> b >> c; bool ans = true; long long s = a * 100 + b * 10 + c; if(s & 1) ans = false; s /= 2; s -= min(a * 100, s / 100 * 100); s -= min(b * 10, s / 10 * 10); s -= min(c, s); if(s) ans = false; cout << (ans ? "Yes" : "No") << endl; } }
C問題
問題ページ : C - Ito Campus
300 〜 400 点くらいの問題がなかなか生えなくて困った。簡単枠を生やすのが難しすぎる。
正解者は B 問題の約半分の 96 人で、予想していたよりも難しかったっぽい。
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> P; const int INF = 1e9; string s[1000]; queue<P> q; int h, w, x, sy, sx, gy, gx; int d[1000][1000], e[1000][1000]; int dy[4] = {1, 0, -1, 0}; int dx[4] = {0, 1, 0, -1}; int main(){ cin >> h >> w >> x; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) d[i][j] = e[i][j] = INF; for(int i = 0; i < h; i++){ cin >> s[i]; for(int j = 0; j < w; j++){ if(s[i][j] == 'S'){ sy = i; sx = j; }else if(s[i][j] == 'G'){ gy = i; gx = j; }else if(s[i][j] == '@'){ q.push({i, j}); d[i][j] = 0; } } } while(!q.empty()){ P p = q.front(); q.pop(); for(int i = 0; i < 4; i++){ int ny = p.first + dy[i]; int nx = p.second + dx[i]; if(s[ny][nx] == '#' || d[ny][nx] != INF) continue; d[ny][nx] = d[p.first][p.second] + 1; if(d[ny][nx] < x) q.push({ny, nx}); } } q.push({sy, sx}); e[sy][sx] = 0; while(!q.empty()){ P p = q.front(); q.pop(); if(p.first == gy && p.second == gx){ cout << e[gy][gx] << endl; return 0; } for(int i = 0; i < 4; i++){ int ny = p.first + dy[i]; int nx = p.second + dx[i]; if(e[ny][nx] != INF || d[ny][nx] <= x || s[ny][nx] == '#') continue; e[ny][nx] = e[p.first][p.second] + 1; q.push({ny, nx}); } } cout << -1 << endl; }
D問題
問題ページ : D - Novelist
想定は区間スケジューリングだけど、DP で解いた人多そう。
正解者は 62 人で、E 問題よりも少なかった。
水色くらいの人が 4 完できるつもりで作ったけど、実際 4 完できたのは青くらいか?
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> P; const int INF = 2e9; int n, m, l; vector<int> a[100000], b[100000]; vector<P> d; int main(){ cin >> n >> m >> l; vector<int> t(n); for(int i = 0; i < n; i++) cin >> t[i]; for(int i = 0; i < m + l; i++){ int city, day; cin >> city >> day; if(i < m) a[city - 1].push_back(day); else b[city - 1].push_back(day); } for(int i = 0; i < n; i++){ b[i].push_back(INF); sort(b[i].begin(), b[i].end()); for(int j = 0; j < a[i].size(); j++){ int tmp = *upper_bound(b[i].begin(), b[i].end(), a[i][j] + t[i]); if(tmp < INF) d.push_back({tmp + t[i], a[i][j]}); else d.push_back({INF, a[i][j]}); } } sort(d.begin(), d.end()); int ans = 0, last = 0; for(int i = 0; i < d.size(); i++){ if(last < d[i].second){ ans += 2; last = d[i].first; } } cout << ans - (last == INF) << endl; }
F問題
問題ページ : F - Team Making
直前に用意していた最終問題が炎上してしまい、急遽出題することになった問題。
制約に bitDP って書いてあるけど、E 問題の半分以下の 30 人にしか解かれなかった。
#include <bits/stdc++.h> using namespace std; int N, K, A[20]; long long dp[1 << 20]; int main(){ cin >> N >> K; for(int i = 0; i < N; i++) cin >> A[i]; dp[0] = 1; for(int bit = 0; bit < (1 << N); bit++){ int i; for(int j = 0; j < N; j++) if(!(bit & (1 << j))) i = j; dp[bit + (1 << i)] += dp[bit]; for(int j = 0; j < i; j++){ if(!(bit & (1 << j)) && A[i] + A[j] <= 2 * K){ dp[bit + (1 << i) + (1 << j)] += dp[bit]; } } for(int j = 0; j < i; j++){ if(bit & (1 << j)) continue; for(int k = j + 1; k < i; k++){ if(!(bit & (1 << k)) && A[i] + A[j] + A[k] <= 3 * K){ dp[bit + (1 << i) + (1 << j) + (1 << k)] += dp[bit]; } } } } cout << dp[(1 << N) - 1] << endl; }
H問題
問題ページ : H - ukuku
manacher の気持ちになると解ける?
1 億人に解かれると思っていたけど、7 人にしか解かれなかった。
#include <bits/stdc++.h> using namespace std; int n, r, idx; string s; bool f[200001][26]; int main(){ cin >> n; for(int i = 0; i < n; i++) s += "$"; for(int i = 0; i < n; i++){ cin >> r; r /= 2; if(s[i] == '$'){ for(int j = 0; j < 26; j++){ if(!f[i][j]){ s[i] = 'a' + j; break; } } idx++; } if(i - r - 1 >= 0) f[i + r + 1][s[i - r - 1] - 'a'] = true; while(idx <= i + r){ s[idx] = s[i - (idx - i)]; idx++; } } cout << s << endl; }
I問題
問題ページ : I - Buffalo
この問題の tester を引き受けてくれたことがきっかけでうしくんが QUPC に関わることになった。EGJ 問題の writer までやってくれた。
ありがとうしくん。たべるのは最後にしてやる。むしゃむしゃ
1 億人に解かれると思っていたけど、5 人にしか(以下略)
#include <bits/stdc++.h> using namespace std; const int MAX = 1000000; long long c[MAX + 1], d[MAX + 1], n, k, a, ans; int main(){ cin >> n >> k; for(int i = 0; i < n; i++){ cin >> a; c[a]++; } for(int i = 1; i <= MAX; i++){ long long r = MAX / i * i, sum = 0; for(int l = i; l <= MAX; l += i){ while(r > 0 && l + r >= k){ sum += c[r]; r -= i; } if(2 * l >= k) d[i] += c[l] * (sum - 1); else d[i] += c[l] * sum; } } for(int i = MAX; i >= 1; i--){ for(int j = i + i; j <= MAX; j += i){ d[i] -= d[j]; } } for(int i = 1; i <= k; i++){ if(k % i == 0) ans += d[i]; } cout << ans / 2 << endl; }
最後に
面白い問題を生やせるようになりたいね
次回の QUPC は 2022 年です (?)