HackerRank Journey to the Moon
気持ちが良い問題だった
問題リンク
問題概要
N人の宇宙飛行士がいます
P個のペアが渡されます
ペアは同じ国籍同士の宇宙飛行士の番号です
N人の中から,国籍が違う宇宙飛行士のペアはいくつあるか
解説
同じ国籍どうしの宇宙飛行士をDFSやUnionFindでグループを作ります
例えばAグループに3人,Bグループに4人いるとすると,Aグループ3人それぞれに対しBグループの4人がペアになりうるので生成できるペア数は12となります
愚直に二重for分でペア数を掛けていくと,時間がかかるのは予想できます
そこで,ひとまずN人から2人を選ぶ組み合わせの総数を出します
そこから同じグループから2人を選ぶ組み合わせの数をグループごとに見ていき引いていけば,答えが求まります
イメージは余事象的な感じですかね?
コード(C++14)
#include <bits/stdc++.h> using namespace std; struct UnionFind{ vector<long long> par; UnionFind(long long N) : par(N){ for(long long i = 0; i < N; i++){ par[i] = -1; } } long long root(long long x){ if(par[x] < 0) return x; else return par[x] = root(par[x]); } void unite(long long x, long long y){ long long rx = root(x); long long ry = root(y); if(rx == ry) return; else{ if(par[rx] > par[ry]) swap(rx, ry); par[rx] += par[ry]; par[ry] = rx; } } bool same(long long x, long long y){ return root(x) == root(y); } void check(){ for(auto x : par){ cout << x << " "; } cout << endl; } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); long long n, p; cin >> n >> p; UnionFind uf(n); while(p--){ long long a, b; cin >> a >> b; uf.unite(a, b); } map<long long, long long> mp; for(long long i = 0; i < n; i++){ long long r = uf.root(i); mp[r] = -uf.par[r]; } vector<long long> B; for(auto x : mp){ B.push_back(x.second); } long long bs = B.size(); long long ans = n * (n - 1) / 2; for(long long i = 0; i < bs; i++){ ans -= B[i] * (B[i] - 1) / 2; } cout << ans << endl; return 0; }
ABC134
結果
3完(10:10)
Rated 2109/4713
所感
A: 問題文の通りに実装を行う
B: 一人の監視員で (d * 2 + 1) の範囲をカバーするので、Nを(d * 2 + 1) で割る(切り上げ)
C: 数列Aの最大値が2以上含む場合はすべて最大値,そうでないなら最大値の箇所だけ2番目の最大値を出力
D: 解けなかった…
2019/07/21解いた
提出URL
#include <bits/stdc++.h> using namespace std; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector<int> A(n + 1); for(int i = 0; i < n; i++){ cin >> A[i + 1]; } int m = 0; for(int i = n; i > 0; i--){ for(int j = i + i; j <= n; j += i){ A[i] ^= A[j]; } if(A[i]) m++; } cout << m << endl; for(int i = 1; i <= n; i++){ if(A[i]) cout << i << ' '; } return 0; }
xorが使えるところ,前から後ろに見ていくのが大事
エラトステネスの篩みたいにn * 対数時間な感じでいい感じになる
まとめ
う〜ん…
ABC126-D: Even Relation
問題概要
N頂点の木がある。頂点ui, vi間の辺の長さはwiとする
同じ色に塗られた任意の2頂点間について、その距離が偶数になることを満たすように各頂点に色を塗る
そのような塗り分け方を1つ見つけて出力せよ
考察
偶数同士、奇数同士の辺でつながっている頂点をそれぞれ別の色で塗りたいが偶数同士だからといって一意に色が定まるわけではない
なんとなく根から各頂点までの距離の累積和の偶奇を取ることにした
以下のような入力を考える
8 1 2 1 1 3 3 3 4 2 3 5 2 5 6 6 5 7 7 7 8 5
図にすると以下のようになる
頂点1を根とし、各頂点までの距離の累積和を取ると以下のようになる
各頂点までの距離の累積和が直前までの累積和と偶奇が同じだったら今までの色、違ったら別の色で塗る
コード
dfsの引数preは前回訪れた頂点で、後戻りさせないようにしている
#include <bits/stdc++.h> using namespace std; typedef pair<int, long long> P; // {to, cost} int n; const int N = 100010; vector<P> G[N]; vector<int> Color(N); void dfs(int now, int pre, int color, long long acost){ // accumulate_cost Color[now] = color; for(int i = 0; i < G[now].size(); i++){ P p = G[now][i]; if(p.first == pre) continue; long long to_acost = p.second + acost; if(to_acost % 2 == acost % 2 ) dfs(p.first, now, color, to_acost); else dfs(p.first, now, (color == 1 ? 0 : 1), to_acost); } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n; for(int i = 0; i < n - 1; i++){ int a, b; long long c; cin >> a >> b >> c; a--; b--; G[a].push_back({b, c}); G[b].push_back({a, c}); } Color.resize(n); dfs(0, -1, 1, 0); for(int i = 0; i < n; i++){ cout << Color[i] << endl; } return 0; }
ABC126-D: Even Relation 供養
Dに一時間以上費やすも解けず蒸発
とりあえずめっちゃ書いたので供養
ACコードではない
#include <bits/stdc++.h> using namespace std; long long const N = 100010; long long n; struct edge { long long cost, to; }; vector<edge> G[N]; vector<bool> F(N); // true: even vector<bool> Check(N); void dfs(long long now, bool fst, int od){ // syokai?, odd? Check[now] = true; if(fst){ for(long long i = 0; i < G[now].size(); i++){ } }else for(long long i = 0; i < G[now].size(); i++){ } } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n; for(long long i = 0; i < n - 1; i++){ long long u, v, w; cin >> u >> v >> w; u--; v--; G[u].push_back({w, v}); G[v].push_back({w, u}); } for(long long i = 0; i < n; i++){ if(Check[i]) continue; dfs(i, true, -1); } return 0; }
#include <bits/stdc++.h> using namespace std; long long const N = 100010; long long n; struct edge { long long cost, to; }; vector<edge> G[N]; vector<bool> BF(N); vector<bool> Check(N); struct UnionFind{ vector<long long> par; UnionFind(int NN) : par(NN){ for(long long i = 0; i < NN; i++){ par[i] = -1; } } long long root(int x){ if(par[x] < 0) return x; else return par[x] = root(par[x]); } void unite(long long x, long long y){ long long rx = root(x); long long ry = root(y); if(rx == ry) return; else{ if(par[rx] > par[ry]) swap(rx, ry); par[rx] += par[ry]; par[ry] = rx; } } bool same(int x, int y){ return root(x) == root(y); } void check(){ for(auto x : par){ cout << x << " "; } cout << endl; } }; void dfs_first(long long now){ // BF[now] = true; Check[now] = true; long long gs = 0; // gusu_count for(long long i = 0; i < G[now].size(); i++){ edge e = G[now][i]; if(e.cost % 2 == 0) gs++; } if(gs * 2 == (long long)G[now].size()){ for(long long i = 0; i < G[now].size(); i++){ edge e = G[now][i]; BF[e.to] = false; Check[e.to] = true; } }else{ if(gs > (long long)G[now].size() / 2){ BF[now] = true; for(long long i = 0; i < G[now].size(); i++){ edge e = G[now][i]; if(e.cost % 2 == 0){ BF[e.to] = true; }else{ BF[e.to] = false; } Check[e.to] = true; } }else{ BF[now] = false; for(long long i = 0; i < G[now].size(); i++){ edge e = G[now][i]; if(e.cost % 2 == 0){ BF[e.to] = true; }else{ BF[e.to] = false; } Check[e.to] = true; } } } } void dfs_second(long long now){ long long bc = 0; // brack_count long long wc = 0; // white_count for(long long i = 0; i < G[now].size(); i++){ edge e = G[now][i]; if(Check[e.to]){ if(BF[e.to]) bc++; else wc++; } } if(bc > 0 and wc == 0){ for(long long i = 0; i < G[now].size(); i++){ if() } }else{ } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n; for(long long i = 0; i < n - 1; i++){ long long u, v, w; cin >> u >> v >> w; u--; v--; G[u].push_back({w, v}); G[v].push_back({w, u}); } bool fff = true; // first? for(long long i = 0; i < n; i++){ if(Check[i]) continue; if(G[i].size() >= 2){ if(fff){ dfs_first(i); fff = false; }else{ // dfs_other? } } } return 0; }
#include <bits/stdc++.h> using namespace std; long long const N = 100010; long long n; struct edge { long long cost, to; }; vector<edge> G[N]; vector<bool> BF(N); vector<bool> C(N); vector<bool> Color(N); struct UnionFind{ vector<long long> par; UnionFind(int NN) : par(NN){ for(long long i = 0; i < NN; i++){ par[i] = -1; } } long long root(int x){ if(par[x] < 0) return x; else return par[x] = root(par[x]); } void unite(long long x, long long y){ long long rx = root(x); long long ry = root(y); if(rx == ry) return; else{ if(par[rx] > par[ry]) swap(rx, ry); par[rx] += par[ry]; par[ry] = rx; } } bool same(int x, int y){ return root(x) == root(y); } void check(){ for(auto x : par){ cout << x << " "; } cout << endl; } }; void dfs1(long long now, UnionFind &uf, map<long long, bool> &mp){ C[now] = true; long long gc = 0; // gusu_count for(long long i = 0; i < G[now].size(); i++){ edge e = G[now][i]; if(e.to % 2 == 0) gc++; } if(gc >= (long long)G[now].size() / 2){ for(long long i = 0; i < G[now].size(); i++){ edge e = G[now][i]; if(e.cost % 2 == 0){ uf.unite(now, e.to); C[e.to] = true; } } mp[uf.root(now)] = true; }else{ for(long long i = 0; i < G[now].size(); i++){ edge e = G[now][i]; if(e.cost % 2 != 0){ uf.unite(now, e.to); C[e.to] = true; } } mp[uf.root(now)] = false; } } void dfs2(long long now, UnionFind &uf, map<long long, bool> &mp){ // long long gc1 = 0, oc1 = 0; // guusuu_counst C[now] = true; long long cnt = 0; for(long long i = 0; i < G[now].size(); i++){ edge e = G[now][i]; if(C[e.to]){ if(mp[uf.root(e.to)]){ if(e.cost % 2 == 0){ uf.unite(now, e.to); C[e.to] = true; }else{ mp[e.to] = false; C[e.to] = true; } }else{ if(e.cost % 2 != 0){ uf.unite(now, e.to); C[e.to] = true; }else{ mp[e.to] = true; C[e.to] = true; } } }else{ cnt++; } } if(cnt == G[now].size()){ dfs1(now, uf, mp); } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n; for(long long i = 0; i < n - 1; i++){ long long u, v, w; cin >> u >> v >> w; u--; v--; G[u].push_back({w, v}); G[v].push_back({w, u}); } map<long long, bool> mp; // true -> gusu UnionFind uf(n); bool ff = true; for(long long i = 0; i < n; i++){ if(G[i].size() >= 2){ if(ff){ dfs1(i, uf, mp); ff = false; }else{ if(C[i]) continue; dfs2(i, uf, mp); } } } for(auto x : mp){ cout << x.first << ' ' << x.second << endl; } return 0; }
CPSCO2019 Session1-C: Coins
問題概要
1, 10, 100, ..., 109, 5, 50, 500, ..., 5 * 109円硬貨がある
スーパーでN種類の果物が1つずつ、それぞれA0,A1, ..., An-1円で売られている
N種類の果物のうち、K個買う時の合計金額をちょうど支払うために必要な硬貨の枚数の最小値を求めよ
ただし、硬貨の数は限りなく多いとする
考察
たくさんの硬貨…? Strange Bankか? と思ったが、大きい硬貨から順番に払っていけば最小の硬貨枚数となるので別問題であると分かった(Strange Bankだと13円の場合、12円以下で大きい値の硬貨から貪欲に削っていくと、9円と1円と1円と1 円の硬貨の4枚となる。しかし6円と6円と1円の3枚が最小の硬貨枚数となる)
硬貨の最小枚数を考える前に、K個の果物を選ぶ方法を考える
nCkを列挙してやれば良いのは分かるが実装方法が分からない…
例えば N = 5, K = 3の場合,{A[0], A[1], A[2]}, {A[0], A[1], A[3]}, {A[0], A[1], A[4]}, ...と順々に列挙する必要がある
順々…?列挙…? …深さ優先探索!!!!!!!!!
AOJ-整数の和が頭に浮かんだ
↑こんなイメージで探索していき、遷移数がKになったときの合計金額を、持っている合計金額以下の硬貨で徐々に減らしていき、硬貨枚数をカウントしてすべての遷移後の硬貨枚数の最小値が答え
うまく説明できなくてアレですが、いけるとこまでいくぜ〜感で探索するイメージです
コード
#include <bits/stdc++.h> using namespace std; long long n, k, ans = 1e9; long long A[35]; vector<long long> Coin; void dfs(long long now, long long cnt, long long total){ if(cnt == k){ long long cc = 0; // coin_count for(long long i = 0; i < Coin.size(); i++){ if(Coin[i] > total) continue; while(total - Coin[i] >= 0){ cc++; total -= Coin[i]; } } ans = min(ans, cc); }else{ for(long long i = 0; i < n; i++){ if(now + 1 + i < n){ dfs(now + 1 + i, cnt + 1, total + A[now + i + 1]); } } } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> k; for(long long i = 0; i < n; i++){ cin >> A[i]; } for(long long i = 0; i < 9; i++){ Coin.push_back((long long)pow(10, i)); Coin.push_back((long long)(5 * pow(10, i))); } sort(Coin.rbegin(), Coin.rend()); for(long long i = 0; i < n; i++){ dfs(i, 1, A[i]); } cout << ans << endl; return 0; }
宣伝
cp-categorizeというサイトに自分で解いた競プロの問題を勝手にジャンル分けしています。深さ優先探索の問題は地道に解いているのでそこそこの問題量があります。ぜひサイトを覗いてみてください!