Codeforces #134 Div.2Only
3完、レートが+100ぐらいした
まぁこどふぉでは誤差なのかな…
A
Reading Hard
#include <cstdio> int n, k; int r[202]; int main() { scanf("%d%d",&n,&k); for (int i=0; i<2*n+1; i++) scanf("%d",&r[i]); int cnt=0; for (int i=1; cnt<k&&i<2*n+1; i+=2) { if (r[i-1]==r[i]-1||r[i+1]==r[i]-1) continue; r[i]--; cnt++; } for (int i=0; i<2*n+1; i++) printf("%d%c",r[i],i==2*n?'\n':' '); }
B
やるだけ
#include <cstdio> #include <climits> #include <algorithm> using namespace std; int n, m; int a[1000], b[1000]; int main() { scanf("%d%d",&n,&m); for (int i=0; i<m; i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(a, a+m); sort(b, b+m); int maxi=0, mini=0; for (int i=0; i<n; i++) { maxi+=a[m-1]; a[m-1]--; sort(a, a+m); } int c=0; for (int i=0; i<n; i++) { while (b[c]==0) c++; mini+=b[c]; b[c]--; sort(b, b+m); } printf("%d %d\n",maxi, mini); }
C
Union-find
#include <cstdio> #include <map> #include <set> using namespace std; typedef pair<int, int> P; struct uf { int par[10000], rank[10000]; uf(int n) { for (int i=0; i<n; i++) { par[i]=i; rank[i]=0; } } int find(int x) { if (x==par[x]) { return x; } else { return par[x]=find(par[x]); } } void unite(int x, int y) { x=find(x); y=find(y); if (x==y) return; if (rank[x]<rank[y]) { par[x]=y; } else { par[y]=x; if (rank[x]==rank[y]) rank[x]++; } } bool same(int x, int y) { return find(x)==find(y); } }; int n; P xy[1000]; int main() { scanf("%d",&n); for (int i=0; i<n; i++) scanf("%d%d",&xy[i].first,&xy[i].second); uf u(n); for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) { if (xy[i].first==xy[j].first||xy[i].second==xy[j].second) u.unite(i,j); } } set<int> ret; for (int i=0; i<n; i++) ret.insert(u.find(i)); printf("%d\n",ret.size()-1); }
D
逆に考えると実はただの互除法らしい。やばい。