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; }
AGC011_A Airport Bus
- 方針
やるだけなのにやけに時間がかかった。自分はアルゴリズム云々の前に、こういう基本的なプログラムの挙動に対する直感がかけているのかも？
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; int main() { ll n, c, k; cin >> n >> c >> k; vector<ll> t(n); for(int i=0;i<n;i++) cin >> t[i]; sort(t.begin(), t.end()); int j = 0, ans = 1; for(int i=0;i<n;i++) { if(t[i] > t[j] + k || i == j + c) { ans++; j = i; } } cout << ans << endl; }
Codeforces #401 C. Alyona and Spreadsheet
概要
n ✕ mの整数テーブルが与えられる。加えて整数kとk個のl[i],r[i]が与えられる。 テーブルのうち、l[i]からr[i]が単調増加(a[i][j] <= a[i][j+1])ならYes, そうでなければNoを出力する。方針 a[i][j] <= a[i+1][j] かつi<n-1のとき dp[i] = dp[i+1] + 1 それ以外のとき dp[i] = 1 とする。 列ごとにdp[i]を作成し、ans[i] = max(ans[i], dp[i])とする。 l[i] - r[i] +1 <= ans[l[i]-1] のときYes, そうでないときNoを出力
#include <iostream> #include <vector> using namespace std; typedef long long ll; int main() { int n, m; cin >> n >> m; ll a[n][m]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin >> a[i][j]; } } vector<int> ans(n, 0); for(int i=0;i<m;i++) { vector<ll> v(n); for(int j=n-1;j>=0;j--) { if(j == n-1) v[j] = 1; else if(a[j][i] > a[j+1][i]) v[j] = 1; else v[j] = v[j+1] + 1; ans[j] = max<ll>(ans[j], v[j]); } } int k; cin >> k; for(int i=0;i<k;i++) { int l, r; cin >> l >> r; if(ans[l-1] >= r - l + 1) cout << "Yes" << endl; else cout << "No" << endl; } }
AGC008B Contiguous Repainting
- 概要
N個の整数列が与えられる。連続するK(<=N)個を選び、全てを白で塗るか全てを黒で塗る（この操作は何回でもおこなうことができる）。色は上書きされる。 黒く塗られた整数の総和の最大値をもとめよ
- 方針
操作順を逆に考える。
そのまま）何回かK個を塗る操作をおこなったあと、最後にK個を白or黒で塗る操作を行う。
逆）最後の操作で塗ったK個の色が確定させ、次の最後から二番目の操作で塗った色を確定させる。（色は上書きされない）
K区間以外は自由な色に確定させることが可能。のでKの区間を探索し、区間の和が>0なら黒、そうでなければ白とする。それ以外の区間はai > 0なら黒、そうでなければ白とする。
単純にやると計算量がO(N2)でアウト。そこで、単純な累積和(=ai)と、0より大きい要素のみの累積和(=bi)を予め求めておく。すると、Kの区間が決まると、K区間の和はaiを使ってO(1)、それ以外の区間の和もbiを使ってO(1)で求まる。よって計算量O(N)でいける。
#include <iostream> #include <vector> using namespace std; typedef long long ll; int main() { int n, k; cin >> n >> k; vector<ll> v(n+1), a(n+1, 0), b(n+1, 0); for(int i=1;i<n+1;i++) cin >> v[i]; for(int i=1;i<n+1;i++) { a[i] += v[i] + a[i-1]; } for(int i=1;i<n+1;i++) { if(v[i] > 0) b[i] += v[i] + b[i-1]; else b[i] = b[i-1]; } ll ans = -1e15; for(int i=1;i <= n - k + 1;i++) { ll ans_i = 0; ll k_range_sum = a[i+k-1] - a[i-1]; ans_i += max<ll>(k_range_sum, 0); ans_i += b[i-1]; ans_i += (b[n] - b[i+k-1]); ans = max<ll>(ans, ans_i); } cout << ans << endl; }
