読者です 読者をやめる 読者になる 読者になる

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

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

逆に考えると実はただの互除法らしい。やばい。

広告を非表示にする