codeforces #406 B. Not Afraid
方針
各グループについて、絶対値が等しい正負の値のペアが存在するか探索。 ペアが存在するグループは少なくとも全員がtraitorというわけではない。 ペアが存在しない場合は、グループ全員がtraitorの可能性がある。 一つのグループでも、グループ全員がtraitorの可能性がアレば"YES",そうでなければ"NO"と出力する。
#include <iostream> #include <vector> #include <algorithm> #include <set> using namespace std; typedef long long ll; int main() { int n, m; cin >> n >> m; string ans = "NO"; for(int i=0;i<m;i++) { int k; cin >> k; set<int> st; for(int j=0;j<k;j++) { int vi; cin >> vi; st.insert(vi); } bool traitor = true; for(auto itr=st.begin();itr!=st.end();itr++) { if(st.count(-*itr)) { traitor = false; break; } } if(traitor) { ans = "YES"; } } cout << ans << endl; }
codeforces #406 A. The Monster
方針
法則性とか考えないで総当りでいけるっぽい
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; int main() { int a, b, c, d; cin >> a >> b >> c >> d; int ans = -1; for(int i=0;i<1000;i++) { bool flag = false; for(int j=0;j<1000;j++) { if(b+a*i == d+c*j) { ans = b + a * i; flag = true; break; } } if(flag) break; } cout << ans << endl; }
ABC D - Maximum Average Sets
#include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <iomanip> typedef long long ll; using namespace std; int main() { int n, a, b; cin >> n >> a >> b; vector<ll> v(n); for(int i=0;i<n;i++) { cin >> v[i]; } sort(v.begin(), v.end(), greater<ll>()); int max_cnt = 0; int cnt_a = 0, idx_a; for(int i=0;i<n;i++) { if(v[0] == v[i]) max_cnt++; } for(int i=0;i<n;i++) { if(v[i] == v[a-1]) { cnt_a++; idx_a = i; } } idx_a++; ll dp[55][55]; dp[0][0] = 1; ll ans = 0; for(int i=1;i<=50;i++) { for(int j=0;j<=50;j++) { if(i>0 && j>0) dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; else dp[i][j] = dp[i-1][j]; } } if(max_cnt > a) { int lim = min(max_cnt, b); for(int i=a;i<=lim;i++) { ans += dp[max_cnt][i]; } } else { int lim = idx_a - cnt_a; ans += dp[cnt_a][a-lim]; } double ave = 0; for(int i=0;i<a;i++) { ave += v[i]; } cout << fixed << setprecision(6) << ave * 1.0 / a << endl; cout << ans << endl; }
Codeforces #405 C. Bear and Different Names
- 方針
まず、n個の異なる名前を用意。 i番目が"NO"なら、ans[i+k-1] = ans[i]とするとi番目以外のk個のグループには影響がない。
ここで、ans[i] = ans[i+k-1]とすると、ans[i+k-1]が後から更新された場合にこまる。
自分の回答
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; typedef long long ll; int main() { int n, k; cin >> n >> k; vector<string> ans(n); int cnt = 0; char suff = 'A', name = 'a'; for(int i=0;i<n;i++) { if(cnt > 25) { suff++; name = 'a'; } string a{suff}, b{name}; //ans[i] = suff + (char) name; ans[i] = a + b; //cout << suff + name << endl; cnt++; name++; } for(int i=0;i<n-k+1;i++) { string si; cin >> si; if(si == "NO") { ans[i+k-1] = ans[i]; } } for(int i=0;i<n;i++) { cout << ans[i] << " "; } cout << endl; }
模範解答
#include <bits/stdc++.h> using namespace std; string s[105]; int main() { int n, k; cin >> n >> k; // generate n different names for(int i = 1; i <= n; ++i) { s[i] = "Aa"; s[i][0] += i / 26; s[i][1] += i % 26; } for(int start = 1; start <= n - k + 1; ++start) { string should; cin >> should; if(should[0] == 'N') // not effective group s[start+k-1] = s[start]; // make two names equal } for(int i = 1; i <= n; ++i) cout << s[i] << " "; cout << "\n"; }
Codeforces #405 B. Bear and Friendship Condition
- 方針
グラフ中の全ての部分グラフ?で
(辺の数)= (頂点の数)*(頂点の数-1) / 2
を満たしていれば “YES"、そうでなければ "NO"と出力。
全探索するために配列 vis[頂点の数] を用意。 dfsでは一つの辺に対して二回ずつカウントしている。 つまり、cnt_eには本来の辺の二倍の数が格納されることになる。
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<bool> vis(150010, false); vector<ll> g[150010]; void dfs(int a, int & cnt_v, int & cnt_e) { if(vis[a]) return; vis[a] = true; cnt_v++; cnt_e += g[a].size(); for(int i=0;i<g[a].size();i++) { if(!vis[g[a][i]]) { dfs(g[a][i], cnt_v, cnt_e); } } } int main() { ll n, m; cin >> n >> m; for(int i=0;i<m;i++) { int ai, bi; cin >> ai >> bi; ai--; bi--; g[ai].push_back(bi); g[bi].push_back(ai); } for(int i=0;i<n;i++) { if(!vis[i]) { int cnt_v = 0, cnt_e = 0; dfs(i, cnt_v, cnt_e); if(cnt_e != (ll) cnt_v * (cnt_v - 1)) { cout << "NO" << endl; //cout << cnt_e << " "<< cnt_v << endl; return 0; } } } cout << "YES" << endl; }
Codeforces #403 C. Andryusha and Colored Balloons
- 方針
解けなかったので他の人の解答をみた。
#include <iostream> #include <vector> #include <set> using namespace std; set<int> c[200010]; vector<int> g[200010], p(200010, 0), a(200010, 0); void dfs(int cur, int pre) { if(pre != -1) { while(c[pre].count(p[pre])) p[pre]++; a[cur] = p[pre]; c[pre].insert(a[cur]); c[cur].insert(a[pre]); } c[cur].insert(a[cur]); for(int i=0;i<g[cur].size();i++) { if(g[cur][i] != pre) { dfs(g[cur][i], cur); } } } int main() { int n; cin >> n; for(int i=0;i<n-1;i++) { int a, b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } dfs(0, -1); int ans = 0; for(int i=0;i<n;i++) { ans = max(ans, a[i]); } cout << ans + 1 << endl; for(int i=0;i<n;i++) { cout << a[i] + 1 << " "; } cout << endl; }
AGC011_B Colorful Creatures
- 方針
昇順にソートして、それぞれの累積和を計算しておく。すると、i番目の生き物が他のすべての生き物と合体するためには、0<=i<=n-2について(0から始まるインデックス基準)、(i番目の累積和)*2 >= (i+1番目の生物の大きさ)を満たしている必要がある。逆に言うと、これを満たさない生物iがあった場合、それ以下の生物も同様に条件をみたすことができない。
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; int main() { ll n; cin >> n; vector<ll> a(n); for(int i=0;i<n;i++) cin >> a[i]; sort(a.begin(), a.end()); vector<ll> sum(n); for(int i=0;i<n;i++) { if(i==0) sum[i] = a[i]; else { sum[i] = sum[i-1] + a[i]; } } int ans=n; for(int i = n-2;i>=0;i--) { if(sum[i] * 2 < a[i+1]) { ans -= (i + 1); break; } } cout << ans << endl; }