6/17 21:00〜22:30 に有志コンを開催します!https://t.co/NXLuvbyZyQ
— null🍆🌥️ (@null_0124) June 13, 2020
writer: @null_0124
tester: @butsurizuki (Thanks!)
言語選択に関してはリンク先を読んでください。
配点: 100-200-300-350-400-600
高校の偏差値が高すぎる。
1:13:16(コンテスト時間1:30:00)で7問全問正解。
- A やるだけ。
- B やるだけ。
- C やるだけ。
- D 累積和。
- E mod p上で四則演算。
- F 累積和。
- G 最小共通祖先。
典型問題が多い。 AtCoderのABCであれば6完水パフォ、7完青バフォがでるはず。 Gは私の実力では解くことは難しいがライブラリを貼って解いた。
A - A+B Problem
やるだけ。
// https://www.hackerrank.com/ysf1 #include <algorithm> #include <array> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> using namespace std; #define int long long signed main() { cin.tie(0); ios::sync_with_stdio(0); int n, m; cin >> n >> m; cout << n + m << endl; } }
B - 三変数方程式
N<3000なのでx, y, zすべてを全通り試すとTLEしそう。 なのでx, yだけを全探索する。
- n-x-y>=0ならばc=n-x-y。
- n-x-y<0ならばcは存在しない。
#include <algorithm> #include <array> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> using namespace std; #define int long long signed main() { cin.tie(0); ios::sync_with_stdio(0); int n; cin >> n; int ans = 0; for (int a = 0; a <= n; a++) { for (int b = 0; b <= n; b++) { const int c = n - a - b; if (c >= 0) ans++; } } cout << ans << endl; }
C - ソーシャルディスタンス / Social Distance
やるだけ。読解ミスして1WAした。
#include <algorithm> #include <array> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> using namespace std; #define int long long signed main() { cin.tie(0); ios::sync_with_stdio(0); int n, d; cin >> n >> d; vector<int> a(n); a[0] = 0; for (int i = 1; i < n; i++) { int ai; cin >> ai; a[i] = a[i - 1] + ai; } for (int i = 1; i < n; i++) { if (a[i] - a[i - 1] < d) a[i] = a[i - 1] + d; } for (int i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl; }
D - Range Xor Query
XOR演算子は交換可能で逆元が存在する。 そのため累積XORを事前に計算しておけば、配列の区間の総XORはO(1)で求められる。
#include <iostream> #include <vector> using namespace std; signed main() { cin.tie(0); ios::sync_with_stdio(0); int n, q; cin >> n >> q; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; // cumulative XOR vector<int> csa(n + 1); csa[0] = 0; for (int i = 0; i < n; i++) csa[i + 1] = csa[i] ^ a[i]; for (int qi = 0; qi < q; qi++) { int l, r; cin >> l >> r; const int ans = csa[r] ^ csa[l - 1]; cout << ans << endl; } }
E - modular arithmetic
mod p上で四則演算ができますか? 私はできます。 答えは0以上p未満なので、引き算するときはpを足してpの余剰を取ってそうします。 割り算するときは逆元を掛けます。
「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜
#include <algorithm> #include <array> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> using namespace std; #define int long long // this code is copied from drken's blog. // https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a long long modinv(long long a, long long m) { long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } // end of copied code signed main() { cin.tie(0); ios::sync_with_stdio(0); int p, n; cin >> p >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; string s; cin >> s; int x = a[0]; for (int i = 0; i < (int)s.size(); i++) { switch (s[i]) { case '+': x = (x + a[i + 1]) % p; break; case '-': x = (x - a[i + 1] + p) % p; break; case '*': x = (x * a[i + 1]) % p; break; case '/': x = (x * modinv(a[i + 1], p)) % p; break; } } cout << x % p << endl; }
F - 区間の和 / Sum of Range
Sを計算します。 Sは愚直に計算すればO(NK-KK)で求められますが、累積和を用いる方法ではO(N+N-K)で求められます。 Sをソートしておけば、クエリは二分探索でO(log(N-K))で求められます。 ソートがボトルネックとなります。
#include <algorithm> #include <array> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> using namespace std; #define int long long signed main() { cin.tie(0); ios::sync_with_stdio(0); int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<int> csa(n + 1); csa[0] = 0; for (int i = 0; i < n; i++) csa[i + 1] = csa[i] + a[i]; vector<int> s(n - k + 1); for (int i = 0; i <= n - k; i++) { s[i] = csa[i + k] - csa[i]; } sort(s.begin(), s.end()); int q; cin >> q; for (int qi = 0; qi < q; qi++) { int x; cin >> x; auto itr = upper_bound(s.begin(), s.end(), x); int count = distance(s.begin(), itr); cout << count << endl; } }
G - 木登り / Climbing Tree
2つの頂点s,t間の距離を高速で求めたいです。 クエリに答える前にすべての頂点の根からの距離と、最小共通祖先uを計算しておきます。 (根からsへの距離) + (根からtへの距離) - 2*(根からuへの距離)と答えることで、高速に答えられます。
うしライブラリ🐮を貼ります。
#include <algorithm> #include <array> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> using namespace std; constexpr int INF = 1000000000 + 8; // https://ei1333.github.io/luzhiled/snippets/graph/template.html template <typename T> struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template <typename T> using Edges = vector<edge<T>>; template <typename T> using WeightedGraph = vector<Edges<T>>; using UnWeightedGraph = vector<vector<int>>; template <typename T> using Matrix = vector<vector<T>>; // https://ei1333.github.io/luzhiled/snippets/tree/doubling-lowest-common-ancestor.html template <typename G> struct DoublingLowestCommonAncestor { const int LOG; vector<int> dep; const G &g; vector<vector<int>> table; DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) { table.assign(LOG, vector<int>(g.size(), -1)); } void dfs(int idx, int par, int d) { table[0][idx] = par; dep[idx] = d; for (auto &to : g[idx]) { if (to != par) dfs(to, idx, d + 1); } } void build() { dfs(0, -1, 0); for (int k = 0; k + 1 < LOG; k++) { for (int i = 0; i < table[k].size(); i++) { if (table[k][i] == -1) table[k + 1][i] = -1; else table[k + 1][i] = table[k][table[k][i]]; } } } int query(int u, int v) { if (dep[u] > dep[v]) swap(u, v); for (int i = LOG - 1; i >= 0; i--) { if (((dep[v] - dep[u]) >> i) & 1) v = table[i][v]; } if (u == v) return u; for (int i = LOG - 1; i >= 0; i--) { if (table[i][u] != table[i][v]) { u = table[i][u]; v = table[i][v]; } } return table[0][u]; } }; void search(WeightedGraph<int> &g, vector<int> &dists, int p = 0) { for (auto &&edge : g[p]) { int np = edge.to; if (dists[np] != INF) continue; int ndist = dists[p] + edge.cost; dists[np] = ndist; search(g, dists, np); } } signed main() { cin.tie(0); ios::sync_with_stdio(0); int n; cin >> n; WeightedGraph<int> g(n); vector<int> dists(n, INF); dists[0] = 0; for (int i = 0; i < n - 1; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; g[a].emplace_back(b, c); g[b].emplace_back(a, c); } search(g, dists, 0); DoublingLowestCommonAncestor<WeightedGraph<int>> lca(g); lca.build(); int q; cin >> q; for (int i = 0; i < q; i++) { int s, t; cin >> s >> t; s--, t--; const int ca = lca.query(s, t); const int ans = dists[s] + dists[t] - 2 * dists[ca]; cout << ans << endl; } }