A. Ichihime and Triangle
問題文
正の整数a, b, c, dが与えられる
次の条件を満たす正の整数x, y, zのうち、三角形となるような3つ組を出力せよ
解法
難しすぎる
三角不等式を考えるとb, c, cなどを出力すればいい
提出コード
void solve(){ ll a, b, c, d; cin >> a >> b >> c >> d; cout << b << " " << c << " " << c << endl; }
B. Kana and Dragon Quest game
問題文
正の整数x, n, mが与えられる
以下の2つの操作が行える
1. をにする
2. をにする
1の操作を最大n回まで、2の操作を最大m回まで行える時hを0以下に出来るかどうかを判定せよ
解法
hが20以上の時、1の操作を行っても意味がなく、10未満だとむしろ悪くなる
そのためhが20以上の時に1の操作を行い、その後2の操作を行って0以下に出来るかを判定する
提出コード
void solve(){ int x, n, m; cin >> x >> n >> m; while(n > 0 && x >= 20){ x /= 2; x += 10; n--; } if(x <= 10 * m) cout << "YES" << endl; else cout << "NO" << endl; }
C. Two Teams Composing
問題文
n頂点からなる木が与えられる
n頂点のうち、k個の頂点を選ぶことを考える
この時、選んだ頂点から頂点1までのパスのうち、選んだk個の頂点以外の頂点の総和を最大化したい
この最大値を答えよ
解法
葉から見ていくことを考える
この時、頂点までの距離が加算される
全ての葉が埋まった状態で、次に頂点を追加する時、その頂点は葉からのパスに含まれるため、子のサイズ分引いてあげる必要がある
そのため、予め各頂点の部分木の大きさをとその深さを求めておき、その差分が大きい順に取っていけばいい
本番では葉からbfsしたけど最初にpriority_queueに入れて大丈夫そう
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int n, k; cin >> n >> k; sz.resize(n); G.resize(n); vector<int> deg(n); REP(i,n-1){ int u, v; cin >> u >> v; --u, --v; G[u].push_back(v); G[v].push_back(u); deg[v]++, deg[u]++; } LCA<vector<vector<int>>> lca(G); lca.build(); priority_queue<tuple<int,int,int>> pq; ll ans = 0; dfs(0, -1); // REP(i,n) cout << sz[i] << " "; // cout << endl; vector<bool> used(n); for(int i=1;i<n;i++) if(deg[i] == 1) pq.emplace(lca.dist(0,i)-(sz[i] - 1), i, -1); while(k > 0 && !pq.empty()){ auto [dist, cur, par] = pq.top(); pq.pop(); if(used[cur]) continue; ans += dist; k--; used[cur] = true; for(auto nv : G[cur]){ if(nv == par) continue; pq.emplace(lca.dist(0, nv)-(sz[nv] - 1), nv, cur); } } cout << endl; cout << ans << endl; }
D. Xenia and Colorful Gems
問題文
赤、緑、青のgemがそれぞれ個あり、それぞれの重さはである
各gemを一つずつ選び次の式を最小化することを考える
この時、得られる値のうち最小のものを出力せよ
解法
こういうのはとりあえず1個固定することを考える
その後、式を見ると最小化にするためにはに近づける必要があるのでlower_boundなどで探索すればいい
本番では赤を固定して、左右を探索してたんだけど、これだけだと不足っぽい
よく考えると3色の並べ方はしかないので全部のパターンを試せばいい
提出コード
void solve(){ int nr, ng, nb; cin >> nr >> ng >> nb; vector<ll> R(nr), G(ng), B(nb); REP(i,nr) cin >> R[i]; REP(i,ng) cin >> G[i]; REP(i,nb) cin >> B[i]; sort(R.begin(), R.end()); sort(G.begin(), G.end()); sort(B.begin(), B.end()); ll ans = 3 * LINF; auto f = [&](ll a, vector<ll> &b, vector<ll> & c) -> void{ auto itr1 = upper_bound(b.begin(), b.end(), a); auto itr2 = lower_bound(c.begin(), c.end(), a); if(itr1 == b.begin() || itr2 == c.end()) return; itr1--; ll tmp = (a - *itr1) * (a - *itr1) + (a - *itr2) * (a - *itr2) + (*itr1 - *itr2) * (*itr1 - *itr2); chmin(ans, tmp); }; REP(i,nr){ f(R[i], G, B); f(R[i], B, G); } REP(i,ng){ f(G[i], R, B); f(G[i], B, R); } REP(i,nb){ f(B[i], R, G); f(B[i], G, R); } cout << ans << endl; }
おわりに
最近のdiv2 Aほんとむずかしい