AtCoder abc396 参加記
AtCoder Beginner Contest 396 - AtCoder
A - Triple Four
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) int main() { int n; cin >> n; vector<int> a(n); int ok = 0; REP(i,n) cin >> a[i]; REP(i,n-2) ok |= (a[i] == a[i+1] && a[i] == a[i+2]); cout << (ok ? "Yes" : "No") << endl; return 0; }
B - Card Pile
後入先出(LIFO) で管理すればよいので stack でカードの山を管理する
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' int main() { int q; cin >> q; vector<int> d(100); REP(i,q) { int t; cin >> t; if (t == 1) { int x; cin >> x; d.push_back(x); } if (t == 2) { cout << d.back() << endl; d.pop_back(); } } return 0; }
C - Buy Balls
黒色のボールの個数を固定したときに、白色のボールをどれだけ取るといいかを考える。 価値の大きいボールから順に取るのが最良のため、価値の大きいものから順に取っていく。 白色は黒色の個数以下で、価値が正のものを取れるだけ取ればいい
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' using ll = long long; int main() { int n,m; cin >> n >> m; vector<int> b(n),w(m); REP(i,n) cin >> b[i]; REP(i,m) cin >> w[i]; REP(i,n-m) w.push_back(0); sort(b.rbegin(),b.rend()); sort(w.rbegin(),w.rend()); ll ans = 0, now = 0; REP(i,n) { now += b[i] + max(0,w[i]); ans = max(ans,now); } cout << ans << endl; return 0; }
D - Minimum XOR Path
N <= 10 と小さいことから、1からNまでのパスを全探索できる
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' using ll = long long; using P = pair<int,ll>; const ll LINF = numeric_limits<ll>::max(); int main() { int n,m; cin >> n >> m; vector g(n,vector<P>()); REP(i,m) { int u,v; ll w; cin >> u >> v >> w; u--; v--; g[u].emplace_back(v,w); g[v].emplace_back(u,w); } vector<bool> visited(n); auto dfs = [&](auto& dfs, int i, ll cur) -> ll { if (i == n-1) return cur; ll res = LINF; for(auto [ni,w]: g[i]) if (!visited[ni]) { visited[ni] = true; res = min(res,dfs(dfs,ni,cur^w)); visited[ni] = false; } return res; }; visited[0] = true; cout << dfs(dfs,0,0) << endl; return 0; }
E - Min of Restricted Sum
頂点 Xi, Yi を Zi 値を持つ辺で結ぶグラフとして考える。 スタートする点の値を 0 として、連結成分ごとに BFS で Axi ^ Ayi = Zi に矛盾がないかを調べる。 矛盾がなければ総和が最小となる数を見つける。これは各ビットごとに見ていき、1 の数が半数より多い場合は反転させればよい。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' using ll = long long; int main() { int n,m; cin >> n >> m; vector g(n,vector<pair<int,int>>()); REP(i,m) { int x,y,z; cin >> x >> y >> z; x--; y--; g[x].emplace_back(y,z); g[y].emplace_back(x,z); } vector<ll> ans(n); vector<bool> visited(n); auto bfs = [&](int start) -> bool { queue<int> q; vector<int> comp; auto push = [&](int v) { q.push(v); comp.push_back(v); visited[v] = true; }; push(start); while(q.size()) { int from = q.front(); q.pop(); for (auto [to,z]: g[from]) { if (visited[to]) { if ((ans[from] ^ ans[to]) != z) return false; } else { ans[to] = ans[from] ^ z; push(to); } } } ll t = 0; REP(bit,31) { int one = 0; for (auto v: comp) one += (ans[v] >> bit) & 1; if (one > (int)comp.size() - one) t |= (1LL << bit); } for (auto v: comp) ans[v] ^= t; return true; }; REP(i,n) if (!visited[i] && !bfs(i)) { cout << -1 << endl; return 0; } for(auto v: ans) cout << v << " "; return 0; }
F - Rotated Inversions
まず BIT で k = 0 のときの転倒数を求めておく。 転倒数に変化が起こるのは、 (a[i] + k) % m == 0 となるときのみなので、差分を計算できないか考える。 (a[i] + k) % m == 0 となるときに寄与する転倒数は、増える分が i, 減る分が n-i-1 なのでこれをイベントとして持っておく。 あとは k = 1 から k = m-1 までに発生するイベントを処理しながら答えを求めていけばよい。
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' using ll = long long; int main() { int n,m; cin >> n >> m; vector<int> a(n); REP(i,n) cin >> a[i]; vector<ll> ans(m); fenwick_tree<int> fw(m); // k = 0 のときの転倒数を fenwich tree で求める REP(i,n) { ans[0] += i - fw.sum(0,a[i]+1); fw.add(a[i],1); } vector events(m,vector<ll>()); REP(i,n) if (a[i] > 0) { // m-1 -> m となるとき(時刻t = m-a[i])に転倒数にどれだけ寄与するか // 増える転倒数 i // 減る転倒数 n-i-1 events[m-a[i]].push_back(i-(n-i-1)); } ll now = ans[0]; for (int k = 1; k < m; k++){ for (auto v : events[k]) now += v; ans[k] = now; } for(auto v: ans) cout << v << endl; return 0; }
雑感
辛い戦いだ...
tic40さんのAtCoder Beginner Contest 396での成績:950位 パフォーマンス:1591相当 レーティング:1247→1286 (+39) :) #AtCoder #ABC396 https://atcoder.jp/users/tic40/history/share/abc396?lang=ja