tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

まとめ

とりあえず、ジャッジで正解を確認したものが増えました。なので適当にソースと解法の概要を上げておきます。

2011 Bookshelf
いろいろ考えると重みつき最長増加部分列になります。適当にSegtreeに入れて処理。

#include<stdio.h>
#include<algorithm>
using namespace std;
int b[100000];
int c[100000];
long long dp[100000];
long long segtree[262144];
void set(int a,long long b){
	a+=131072;
	while(a){
		segtree[a]=max(segtree[a],b);
		a/=2;
	}
}
long long query(int a,int b,int c,int d,int e){
	if(b<c||d<a)return 0;
	if(c<=a&&b<=d)return segtree[e];
	return max(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
pair<int,int> dat[100000];
int m[100000];
int main(){
	int a;
	scanf("%d",&a);
	long long sum=0;
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
		sum+=b[i];
	}
	for(int i=0;i<a;i++){
		scanf("%d",c+i);
	}
	for(int i=0;i<a;i++)dat[i]=make_pair(c[i],i);
	std::sort(dat,dat+a);
	for(int i=0;i<a;i++){
		long long val=query(0,131071,0,dat[i].second,1);
		dp[dat[i].second]=val+b[i];
		set(dat[i].second,dp[dat[i].second]);
	}
	printf("%lld\n",(sum-query(0,131071,0,131071,1))*2);
}

2008 Fraction
適当にpriority_queueで処理。

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
bool so(int a,int b){
	while(a){
		b%=a;
		int c=b;
		b=a;
		a=c;
	}
	if(b-1)return false;
	else return true;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	priority_queue<pair<double, pair<int,int> > >Q;
	for(int i=2;i<=a;i++)Q.push(make_pair(-(double)1/(double)i,make_pair(1,i)));
	for(int i=0;i<b-1;i++){
		if(Q.size()==0){
			printf("-1\n");
			return 0;
		}
		int bunshi=Q.top().second.first;
		int bunbo=Q.top().second.second;
		Q.pop();
		bunshi++;
		while(!so(bunshi,bunbo))bunshi++;
		if(bunshi<bunbo)Q.push(make_pair(-(double)bunshi/(double)bunbo,make_pair(bunshi,bunbo)));
	}
	if(Q.size())
		printf("%d %d\n",Q.top().second.first,Q.top().second.second);
	else printf("-1\n");
}

2009 Abduction
縦と横に分けて考えて後はかけるだけ。オーバーフローとかそういう難しさ。

#include<stdio.h>
char str[10010];
int dpX[1010];
int dpY[1010];
int MOD=10000000;
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	a++;
	b++;
	
	scanf("%s",str);
	int dir=0;
	if(str[0]=='L'){
		dir=1;
		for(int i=1;i<a;i++){
			dpX[i]=1;
		}
		dpY[0]=1;
	}else{
		for(int i=1;i<b;i++)dpY[i]=1;
		dpX[0]=1;
	}
	for(int i=0;i<c;i++){
		if(str[i]=='L')dir+=3;
		else dir++;
		if(dir%4==0){
			int now=0;
			for(int j=0;j<b;j++){
				int m=dpY[j];
				dpY[j]=now;
				now=(now+m)%MOD;
			}
		}
		if(dir%4==1){
			int now=0;
			for(int j=0;j<a;j++){
				int m=dpX[j];
				dpX[j]=now;
				now=(now+m)%MOD;
			}
		}
		if(dir%4==2){
			int now=0;
			for(int j=b-1;j>=0;j--){
				int m=dpY[j];
				dpY[j]=now;
				now=(now+m)%MOD;
			}
		}
		if(dir%4==3){
			int now=0;
			for(int j=a-1;j>=0;j--){
				int m=dpX[j];
				dpX[j]=now;
				now=(now+m)%MOD;
			}
		}
	}
	printf("%lld\n",(long long)dpX[a-1]*dpY[b-1]%MOD);
}

2008 Typhoon
座標圧縮してイベントもソートしてそれからSegTree。こういうのはどうでもいいところを間違えやすい。(今回はSegTreeのサイズを誤った)

#include<stdio.h>
#include<algorithm>
using namespace std;
int SEGTREE[1048576];
pair<pair<int,int>,pair<int,int> > q[200000];
pair<int,int> taihuu[100000];
pair<int,pair<int,int> >Qval[100000];
pair<int,int> pressed[100000];
int ans[100000];
int zahyou[300000];
int V[300000];
int pd[200000];
void query(int begin,int end,int a,int b,int index){
	if(begin<=a&&end>=b){
		SEGTREE[index]++;
		//printf("%d %d\n",index,SEGTREE[index]);
	}
	else if(begin>b||end<a);
	else {
		query(begin,end,a,(a+b)/2,index*2);
		query(begin,end,(a+b)/2+1,b,index*2+1);
	}
	return ;
}
int search(int at){
	int ret=0;
	at+=524288;
	while(at){
		ret+=SEGTREE[at];
		at/=2;
	}
	//printf("%d\n",ret);
	return ret;
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++){
		scanf("%d%d",&taihuu[i].first,&taihuu[i].second);
		V[i*2]=taihuu[i].first;
		V[i*2+1]=taihuu[i].second;
	}
	for(int i=0;i<b;i++){
		int d,e,f;
		scanf("%d%d%d",&d,&e,&f);
		V[a*2+i]=d;
		Qval[i]=make_pair(d,make_pair(e-1,f));
	}
	std::sort(V,V+a*2+b);
	int wolf=0;
	zahyou[wolf++]=V[0];
	for(int i=1;i<a*2+b;i++){
		if(V[i]!=V[i-1])zahyou[wolf++]=V[i];
	}
	std::sort(zahyou,zahyou+wolf);
	//for(int i=0;i<a*2+b;i++)printf("%d ",zahyou[i]);
	//printf("\n");
	for(int i=0;i<a;i++){
		pressed[i]=make_pair(lower_bound(zahyou,zahyou+wolf,taihuu[i].first)-zahyou,lower_bound(zahyou,zahyou+wolf,taihuu[i].second)-zahyou);
	}
	for(int i=0;i<b;i++){
		pd[i]=lower_bound(zahyou,zahyou+wolf,Qval[i].first)-zahyou;
	}
	for(int i=0;i<b;i++){
		q[i*2]=make_pair(make_pair(Qval[i].second.first,1),make_pair(pd[i],i));
		q[i*2+1]=make_pair(make_pair(Qval[i].second.second,2),make_pair(pd[i],i));
	}
	std::sort(q,q+b*2);
	int now=0;
	for(int i=0;i<b*2;i++){
		int go=q[i].first.first;
		while(now<go){
			//printf("%d %d\n",pressed[now].first,pressed[now].second);
			query(pressed[now].first,pressed[now].second,0,524287,1);
			now++;
			//for(int j=0;j<10;j++)printf("%d ",search(j));
		}
		if(q[i].first.second==1){
			ans[q[i].second.second]-=search(q[i].second.first);
		}else{
			ans[q[i].second.second]+=search(q[i].second.first);
		}
	}
	//for(int i=0;i<32;i++)printf("%d ",search(i));
	for(int i=0;i<b;i++)printf("%d\n",ans[i]);
}

2008 Committee
それっぽい木DPで通る。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> t[100000];
int v[100000];
bool visited[100000];
int dp[100000];
int solve(int a){
	if(visited[a])return dp[a];
	int ret=v[a];
	for(int i=0;i<t[a].size();i++)if(solve(t[a][i])>0)ret+=solve(t[a][i]);
	visited[a]=true;
	return dp[a]=ret;
}
int main(){
	int a;
	for(int i=0;i<100000;i++){
		visited[i]=false;
		v[i]=0;
		dp[i]=0;
	}
	scanf("%d",&a);
	int s=0;
	int m=-99999999;
	for(int i=0;i<a;i++){
		int b,c;
		scanf("%d%d",&b,&c);
		if(b!=0)t[b-1].push_back(i);
		else s=i;
		v[i]=c;
		m=max(m,c);
	}
	int ret=m;
	for(int i=0;i<a;i++)ret=max(ret,solve(i));
	printf("%d\n",ret);
}

2009 Pyramid
よくみんな変な4方向からDPと言うけど、BFSするだけでも解ける。イベントを持っておく。

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
pair<int,pair<int,int> > dat[10000];
int bfs[3000][3000];
int dx[]={1,0,0,-1,1,1,-1,-1};
int dy[]={0,1,-1,0,1,-1,1,-1};
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++)
		for(int j=0;j<b;j++)
			bfs[i][j]=-1;
	for(int i=0;i<c;i++){
		int d,e,f;
		scanf("%d%d%d",&d,&e,&f);
		dat[i]=make_pair(-f,make_pair(d,e));
	}
	std::sort(dat,dat+c);
	queue<pair<int,int> >Q;
	bfs[dat[0].second.first][dat[0].second.second]=-dat[0].first;
	Q.push(make_pair(dat[0].second.first,dat[0].second.second));
	int now=1;
	while(Q.size()){
		int row=Q.front().first;
		int col=Q.front().second;
		Q.pop();
		while(-dat[now].first==bfs[row][col]){
			if(bfs[dat[now].second.first][dat[now].second.second]==-1){
				bfs[dat[now].second.first][dat[now].second.second]=-dat[now].first;
				Q.push(make_pair(dat[now].second.first,dat[now].second.second));
			}
			now++;
		}
		for(int i=0;i<8;i++){
			if(0<=row+dx[i]&&row+dx[i]<a&&0<=col+dy[i]&&col+dy[i]<b&&bfs[row+dx[i]][col+dy[i]]==-1&&bfs[row][col]>0){
				bfs[row+dx[i]][col+dy[i]]=bfs[row][col]-1;
				Q.push(make_pair(row+dx[i],col+dy[i]));
			}
		}
	}
	long long ret=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			ret+=(bfs[i][j]==-1)?0:bfs[i][j];
		//	printf("%d ",bfs[i][j]);
		}
		//printf("\n");
	}
	printf("%lld\n",ret);
}

2010 Stairs
累積和をもちつつDP。

#include<stdio.h>
int dat[500001];
int dp1[500001];
int dp2[500001];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=1;i<=a;i++)scanf("%d",dat+i);
	for(int i=1;i<=a;i++)dat[i]+=dat[i-1];
	dp1[0]=1;
	dp2[0]=1;
	int at=0;
	for(int i=1;i<=a;i++){
		while(dat[i]-dat[at]>b)at++;
		dp1[i]=(dp2[i-1]-((at>0)?dp2[at-1]:0)+1234567)%1234567;
		dp2[i]=(dp2[i-1]+dp1[i])%1234567;
	}
	printf("%d\n",dp1[a]);
}

2011 Orienteering
トポロジカルソートとDPとDijkstraを使った印象がある。実際は複合するだけ。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<int> ts;
int dist[1001][1001];
int ans[1001][1001];
int ijk[1001][1001];
bool v[1001][1001];
int check[1001];
int color[1001];
int list[1001];
vector<pair<int,int> > g[1001];
void dfs(int a){
	color[a]=1;
	for(int i=0;i<g[a].size();i++){
		if(!color[g[a][i].first]){
			dfs(g[a][i].first);
		}
	}
	ts.push_back(a);
	color[a]=2;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",check+i);
	for(int i=0;i<b;i++){
		int c,d,e;
		scanf("%d%d%d",&c,&d,&e);
		c--;
		d--;
		g[c].push_back(make_pair(d,e));
	}
	for(int i=0;i<a;i++){
		if(!color[i]){
			dfs(i);
		}
	}
	reverse(ts.begin(),ts.end());
	for(int i=0;i<a;i++)
		for(int j=0;j<a;j++)
			dist[i][j]=999999999;
	for(int i=0;i<a;i++){
		dist[ts[i]][ts[i]]=0;
		for(int j=i;j<a;j++){
			for(int k=0;k<g[ts[j]].size();k++)
				dist[ts[i]][g[ts[j]][k].first]=min(dist[ts[i]][g[ts[j]][k].first],dist[ts[i]][ts[j]]+g[ts[j]][k].second);
		}
	}
	int now=1;
	for(int i=0;i<a;i++){
		if(check[ts[i]])list[now++]=ts[i];
	}
	list[now++]=a-1;
	for(int i=0;i<a;i++)
		for(int j=0;j<a;j++)
			ans[i][j]=999999999;
	ans[0][0]=0;
	for(int i=0;i<now;i++){
		for(int j=0;j<now;j++){
			ans[i][max(i,j)+1]=min(ans[i][max(i,j)+1],ans[i][j]+dist[list[j]][list[max(i,j)+1]]);
			ans[max(i,j)+1][j]=min(ans[max(i,j)+1][j],ans[i][j]+dist[list[i]][list[max(i,j)+1]]);
		}
	}
	int ret=999999999;
	for(int i=0;i<now;i++)
		ret=min(ret,min(ans[i][now-1]+dist[list[i]][list[now-1]],ans[now-1][i]+dist[list[i]][list[now-1]]));
	printf("%d\n",ret);
}

2011 Report
うまくDFSするとよくある問題になる。BIT使っていたらしい。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int bit[131072];
vector<int> rev[131072];
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<131072;a|=a+1)bit[a]+=b;
}
int c[100000];
int v[100000];
int num[100000];
int now;
int left[100000];
int right[100000];
int at;
vector<int> g[100000];
void dfs(int a){
	v[a]=1;
	if(v[c[a]]<0)dfs(c[a]);
	num[now++]=a;
}
void DFS(int a){
	v[a]=now;
	for(int i=0;i<rev[a].size();i++){
		if(v[rev[a][i]]==-1)DFS(rev[a][i]);
	}
}
void dfs2(int a){
	left[a]=at++;
	for(int i=0;i<g[a].size();i++){
		dfs2(g[a][i]);
	}
	right[a]=at-1;
}
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	for(int i=0;i<a;i++){
		c[i]--;
		rev[c[i]].push_back(i);
	}
	for(int i=0;i<a;i++)v[i]=-1;
	for(int i=0;i<a;i++){
		if(v[i]<0){
			dfs(i);
		}
	}
	for(int i=0;i<a;i++)v[i]=-1;
	now=0;
	for(int i=a-1;i>=0;i--){
		if(v[num[i]]<0){
			DFS(num[i]);
			now++;
		}
	}
	for(int i=0;i<a;i++){
		if(v[i]!=v[c[i]]){
			g[v[c[i]]].push_back(v[i]);
			num[v[i]]=-1;
		}
	}
	for(int i=0;i<now;i++){
		if(~num[i]){
			dfs2(i);
		}
	}
	for(int i=0;i<a;i++){
	//	printf("%d %d %d ",v[i],left[v[i]],right[v[i]]);
		printf("%d\n",sum(left[v[i]],right[v[i]]));
		add(left[v[i]],1);
	}
}

2011 Keycards
数学する。適当にコンビネーションの計算をがんばる。逆元は拡張ほげを導き出すのに時間がかかるのでp-2乗した。ちなみにこれは毎回同じ定数1つになるので正直言ってTLE気にするならマジックナンバー化してしまったほうが安心できる。O(N)でいけることがわかる。オーバーフローに注意

#include<stdio.h>
long long mod=1000000007;
long long left[1000002];
long long right[1000002];
long long rj[1000002];
long long C[1000002];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	left[0]=1;
	for(int i=1;i<1000002;i++){
		left[i]=(left[i-1]*i)%mod;
	}
	right[1000001]=1000001;
	for(int i=1000000;i>0;i--){
		right[i]=(right[i+1]*i)%mod;
	}
	long long s=left[1000001];
	long long t=1;
	int c=mod-2;
	while(c){
		if(c&1)t=t*s%mod;
		c/=2;
		s=s*s%mod;
	}
	long long at=1;
	long long val=1;
	for(int i=0;i<=a-b;i++){
		C[i]=at;
	//	printf("%lld\n",C[i]);
		at=at*(a-b-i)%mod;
		at=at*left[i]%mod*right[i+2]%mod*t%mod;
	}
	for(int i=1;i<=b;i++){
		val=val*(1+a-i)%mod;
		val=val*(left[i-1])%mod*right[i+1]%mod*t%mod;
	}
	rj[0]=2;
	for(int i=1;i<1000001;i++)rj[i]=rj[i-1]*rj[i-1]%mod;
	long long ret=0;
	for(int i=0;i<=(a-b);i++){
		ret=(ret+rj[i]*C[i]*(((a-b-i)&1)?-1:1))%mod;
		while(ret<0)ret+=mod;
	}
	if(a==b)ret=(ret+mod-1)%mod;
	printf("%lld\n",ret*val%mod);
}

2010 Plugs
いもす法してから1つ1つ決めていく。

#include<stdio.h>
#include<algorithm>
using namespace std;
int dat[3001][3001];
int p[3001];
int ans[3001];
bool use[3001];
bool v[3001];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int c,d,e,f;
		scanf("%d%d%d%d",&c,&e,&d,&f);
		dat[c-1][d-1]++;
		dat[c-1][f]--;
		dat[e][d-1]--;
		dat[e][f]++;
	}
	for(int i=0;i<a;i++){
		int val=0;
		for(int j=0;j<a;j++){
			dat[i][j]=(val+=dat[i][j]);
		}
	}
	for(int i=0;i<a;i++){
		int val=0;
		for(int j=0;j<a;j++){
			dat[j][i]=(val+=dat[j][i]);
		}
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			if(dat[i][j])p[i]++;
		}
	}
	//for(int i=0;i<a;printf("\n"),i++)
	//	for(int j=0;j<a;printf("%d ",dat[i][j++]));
	int now=a;
	for(int i=0;i<a;i++){
		int at=0;
		for(int j=0;j<a;j++){
			if(!v[j]&&p[j]==now-1){
				for(int k=0;k<a;k++){
					if(!use[k]&&!dat[j][k]){
						at=k;
						break;
					}
				}
				ans[j]=at;
			//	printf("%d\n",at);
				v[j]=true;
				break;
			}
		}
		use[at]=true;
		for(int j=0;j<a;j++)if(dat[j][at])p[j]--;
		now--;
	}
	for(int i=0;i<a;i++)printf("%d\n",ans[i]+1);
}

2010 Lake
DP。複雑なDPを書いていたが絶対もっと簡単に書ける。こういう座標の管理苦手。

#include<stdio.h>
#include<algorithm>
using namespace std;
int x[4000];
pair<int,int>b[2000];
int dp[4000][4000];
int other[4000];
int n;
int solve(int a,int b){
	if(a>=n)a-=n;
	if(b>=n)b-=n;
	if(a<0)a+=n;
	if(b<0)b+=n;
//	printf("%d %d\n",a,b);
	if(a==b)return 0;
	if(~dp[a][b])return dp[a][b];
	int p=other[a];
	int ret=0;
	ret=solve(a+1,b);
	if(a<b){
		if(a<p&&p<=b){
			int s=a+1;
			int t=p-1;
			int u=p+1;
			int v=b;
			if(s>=n)s-=n;
			if(u>=n)u-=n;
			if(t<0)t+=n;
			if((a+1)%n==p)s=t;
			if(p==b)u=v;
			ret=max(ret,solve(s,t)+solve(u,v)+1);
		}
	}else{
		if((!(b+1<=p&&p<=a-1))&&(a<p||p<=b)){
			int s=a+1;
			int t=p-1;
			int u=p+1;
			int v=b;
			if(s>=n)s-=n;
			if(u>=n)u-=n;
			if(t<0)t+=n;
			if((a+1)%n==p)s=t;
			if(p==b)u=v;
			ret=max(ret,solve(s,t)+solve(u,v)+1);
		}
	}
	return dp[a][b]=ret;
}
int main(){
	int a;
	scanf("%d",&a);
	n=a*2;
	for(int i=0;i<a;i++)scanf("%d%d",&b[i].first,&b[i].second);
	for(int i=0;i<a;i++){
		x[i*2]=b[i].first;
		x[i*2+1]=b[i].second;
	}
	std::sort(x,x+a*2);
	for(int i=0;i<a;i++){
		b[i].first=lower_bound(x,x+a*2,b[i].first)-x;
		b[i].second=lower_bound(x,x+a*2,b[i].second)-x;
		if(b[i].first>b[i].second)swap(b[i].first,b[i].second);
	}
	for(int i=0;i<a;i++){
		other[b[i].first]=b[i].second;
		other[b[i].second]=b[i].first;
	}
	for(int i=0;i<a*2;i++)
		for(int j=0;j<a*2;j++)
			dp[i][j]=-1;
	int ret=0;
	for(int i=0;i<a;i++){
		ret=max(ret,(b[i].first+1>b[i].second-1)?0:solve(b[i].first+1,b[i].second-1)+(b[i].first+n-b[i].second<2)?0:solve(b[i].second+1,b[i].first-1)+1);
	//	printf("\n");
	}
	printf("%d\n",ret);
}

2010 Highway
ずいぶん昔に書いたらしく。本気を出して解いている。今やったらもっとまともなソースになりそうである。LCAとBITを使う。今ならLCAは10分ちょいでかけるようになってるので合宿の中では楽なほう?

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int st1[262144];//木の下から上に行くのにかかる時間(dfs順は大→小)
int st2[262144];//木の上から下に行くのにかかる時間(dfs順は小→大)
int lca[1048576];//SEGTREE.nearest common共通祖先
int node[100000];//DFS順 なかに点のもとの番号を入れる
int nodeleft[100000];//↑を使うために必要な各ノードの左側のnowlca順 いれるものは点の番号(DFS順ではないらしい!)
bool visited[100000];//DFS用
vector<int> g[100000];//グラフ。途中からいらない
int right[100000];//直上のノードまでの変更があったとき、どこまで影響するか (n)./(1) この/のノードの話である。DFS順
int nowlca;//LCA用
int Count;//DFS順
pair<int,int> edge[100000];//辺の両端
int cost1[100000];//↑のDFS順大→小
int cost2[100000];//↑↑のDFS順小→大
char str[2];
int S;
int LCA(int a,int b,int s,int t,int u){
	if(a>t||s>b)return 99999999;
	if(a<=s&&t<=b)return lca[u];
	return min(LCA(a,b,s,(s+t)/2,2*u),LCA(a,b,(s+t)/2+1,t,2*u+1));
}
void INIT_LCA(int a,int b){
	a+=524288;
	lca[a]=b;
	a/=2;
	while(a){
		lca[a]=min(lca[a*2],lca[a*2+1]);
		a/=2;
	}
}
void CHG(int a,int b,int c,int d,int e,int f,int g){
	if(a==1){
		if(b>e||c<d)return;
		if(b<=d&&e<=c){
			st1[f]+=g;
			return;
		}
		CHG(a,b,c,d,(d+e)/2,f*2,g);
		CHG(a,b,c,(d+e)/2+1,e,f*2+1,g);
	}else{
		if(b>e||c<d)return;
		if(b<=d&&e<=c){
			st2[f]+=g;
			return;
		}
		CHG(a,b,c,d,(d+e)/2,f*2,g);
		CHG(a,b,c,(d+e)/2+1,e,f*2+1,g);
	}
}
int query(int a,int b){
	int ret=0;
	b+=131072;
	while(b){
		if(a==1)ret+=st1[b];
		if(a==2)ret+=st2[b];
		b/=2;
	}
	return ret;
}
int dfs(int a){
	int p=Count++;
	visited[a]=true;
	node[a]=p;
	INIT_LCA(nowlca++,p);
	st1[node[a]+131072]=st2[node[a]+131072]=S;
	nodeleft[a]=nowlca-1;
	for(int i=0;i<g[a].size();i++){
		if(!visited[g[a][i]]){
			S++;
			dfs(g[a][i]);
			S--;
			INIT_LCA(nowlca++,p);
		}
	}
	right[p]=Count-1;
}
int main(){
	int a,b;
	for(int i=0;i<1048576;i++)lca[i]=99999999;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a-1;i++){
		int c,d;
		scanf("%d%d",&c,&d);
		edge[i]=make_pair(c-1,d-1);
		g[c-1].push_back(d-1);
		g[d-1].push_back(c-1);
		cost1[i]=cost2[i]=1;
	}
	INIT_LCA(nowlca++,0);
	dfs(0);
//	for(int i=0;i<a;i++)printf("%d ",node[i]);
//	printf("\n");
//	for(int i=0;i<nowlca;i++)printf("%d ",lca[i+524288]);
//	printf("\n");
	for(int i=0;i<b;i++){
		scanf("%s",str);
		if(str[0]=='I'){
			int c,d,e;
			scanf("%d%d%d",&c,&d,&e);
			if((edge[c-1].first<edge[c-1].second&&node[edge[c-1].first]<node[edge[c-1].second])||(edge[c-1].first>edge[c-1].second&&node[edge[c-1].first]>node[edge[c-1].second])){
				//のぼりが下向き
		//		printf("%d %d\n",max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])]);
				CHG(1,max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])],0,131071,1,e-cost1[c-1]);
				CHG(2,max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])],0,131071,1,d-cost2[c-1]);
				cost1[c-1]=e;
				cost2[c-1]=d;
			}
			else{
				//のぼりが上向き
		//		printf("%d %d\n",max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])]);
				CHG(1,max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])],0,131071,1,d-cost1[c-1]);
				CHG(2,max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])],0,131071,1,e-cost2[c-1]);
				cost1[c-1]=d;
				cost2[c-1]=e;
			}
		}else{
			int c,d;
			scanf("%d%d",&c,&d);
			int root=LCA(min(nodeleft[c-1],nodeleft[d-1]),max(nodeleft[c-1],nodeleft[d-1]),0,524287,1);
			int rootdist=query(1,root)+query(2,root);
	//		printf("%d\n",root);
		//	printf("%d %d %d\n",query(1,node[c-1]),query(2,node[d-1]),rootdist);
			printf("%d\n",query(1,node[c-1])+query(2,node[d-1])-rootdist);
		}
	}
}

2010 Contest
くそげ〜

#include<stdio.h>
#include<algorithm>
using namespace std;
int score[10];
char type[20];
int res[1000];
int time[1000][10];
int wa[1000][10];
int main(){
	int a,b,c,d,e;
	scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
	for(int i=0;i<b;i++)scanf("%d",score+i);
	for(int i=0;i<e;i++){
		int f,g,h;
		scanf("%d%d%d%s",&f,&g,&h,type);
		if(type[0]=='o'){
			time[g-1][h-1]=f;
		}else if(type[0]=='i'){
			wa[g-1][h-1]++;
		}else{
			res[g-1]+=max(d,score[h-1]-(f-time[g-1][h-1])-120*wa[g-1][h-1]);
		}
	}
	for(int i=0;i<a;i++)printf("%d\n",res[i]);
	return 0;
}

2010 Hide and seek
Starry Sky Treeをやる。イベント処理するだけ。

#include<stdio.h>
#include<algorithm>
using namespace std;
int segtree[262144];
int query(int a,int b,int c,int d,int e){
	if(d==e)return d;
	if(b+segtree[a*2]>=c){
		return query(a*2,b+segtree[a*2],c,d,(d+e)/2);
	}else return query(a*2+1,b+segtree[a*2+1],c,(d+e)/2,e);
}
void add(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		segtree[e]+=f;
	}else{
		add(a,(a+b)/2,c,d,e*2,f);
		add((a+b)/2+1,b,c,d,e*2+1,f);
	}
	if(e!=1){
		if(segtree[e]>0||segtree[e^1]>0){
			int P=max(segtree[e],segtree[e^1]);
			segtree[e]-=P;
			segtree[e^1]-=P;
			segtree[e/2]+=P;
		}
	}
}
pair<int,pair<int,int> > p[50000];
pair<int,int>event[50000];
int x[50000];
int y[50000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d%d%d",&p[i].second.first,&p[i].first,&p[i].second.second);
		p[i].second.second+=p[i].second.first-1;
	}
	for(int i=0;i<b;i++){
		scanf("%d",&event[i].first);
		event[i].first++;
		event[i].second=i;
	}
	std::sort(p,p+a);
	std::sort(event,event+b);
	int at=0;
	for(int i=0;i<b;i++){
		bool dame=false;
		while(segtree[1]<event[i].first){
			if(at<a){
				add(0,131071,p[at].second.first,p[at].second.second,1,1);
				at++;
			}else{
				dame=true;
				break;
			}
		}
		if(dame){
			x[event[i].second]=-2;
			y[event[i].second]=-1;
		}else{
			y[event[i].second]=p[at-1].first;
			x[event[i].second]=query(1,segtree[1],event[i].first,0,131071);
		}
	}
	for(int i=0;i<b;i++)printf("%d %d\n",x[i]+1,y[i]);
}

2010 Finals
誰でも解けると思う。

#include<stdio.h>
#include<algorithm>
using namespace std;
int UF[100000];
pair<int,pair<int,int> > e[100000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);
	b=FIND(b);
	if(a==b)return;
	UF[a]+=UF[b];
	UF[b]=a;
	return;
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++)UF[i]=-1;
	for(int i=0;i<b;i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);
		e[i]=make_pair(r,make_pair(p-1,q-1));
	}
	std::sort(e,e+b);
	int nokori=a-c;
	int ret=0;
	int at=0;
	while(nokori){
		int s=e[at].second.first;
		int t=e[at].second.second;
		if(FIND(s)!=FIND(t)){
			UNION(s,t);
			ret+=e[at].first;
			nokori--;
		}
		at++;
	}
	printf("%d\n",ret);
}

2010 Regions
二分探索して葉からどんどん切っていく。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int,int> > G[30000];
vector<pair<int,int> > g[30000];
int size[30000];
int t[30000];
int M;
int now;
void cut(int a){
	for(int i=0;i<g[a].size();i++)cut(g[a][i].first);
	if(g[a].size()==0){
		size[a]=0;
		return;
	}
	if(g[a].size()==1){
		int R=size[g[a][0].first]+g[a][0].second;
		if(R>M){
			size[a]=0;
			now++;
			return;
		}else{
			size[a]=R;
			return;
		}
	}
	if(g[a].size()>1){
		for(int i=0;i<g[a].size();i++){
			t[i]=size[g[a][i].first]+g[a][i].second;
		}
		std::sort(t,t+g[a].size());
		if(t[0]>M){
			size[a]=0;
			now+=g[a].size();
			return;
		}
		for(int i=1;i<g[a].size();i++){
			if(t[i]+t[i-1]>M){
				size[a]=t[i-1];
				now+=(g[a].size()-i);
				return;
			}
		}
		size[a]=t[g[a].size()-1];
	}
}
void init(int a,int b){
	for(int i=0;i<G[a].size();i++){
		if(b!=G[a][i].first){
			g[a].push_back(G[a][i]);
			init(G[a][i].first,a);
		}
	}
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a-1;i++){
		int c,d,e;
		scanf("%d%d%d",&c,&d,&e);
		c--;
		d--;
		G[c].push_back(make_pair(d,e));
		G[d].push_back(make_pair(c,e));
	}
	init(0,-1);
	int left=-1;
	int right=99999999;
	while(left+1<right){
		M=(left+right)/2;
		now=0;
		cut(0);
		now++;
	//	printf("%d %d\n",M,now);
		if(now<=b){
			right=M;
		}else left=M;
	}
	printf("%d\n",right);
}

2010 DNA Synthesizer
Trieすれば簡単な問題になる。Aho-Corasickでもいける。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
char goal[150001];
char sa[50000][21];
int dp[150021];
struct Trie{
	bool mark;
	int A;
	int T;
	int G;
	int C;
	Trie(){
		mark=false;
		A=-1;
		T=-1;
		G=-1;
		C=-1;
	}
};
vector<Trie> v;
int main(){
	int a;
	scanf("%d",&a);
	scanf("%s",goal);
	v.push_back(Trie());
	for(int i=0;i<a;i++)scanf("%s",sa[i]);
	for(int i=0;i<a;i++){
		int now=0;
		int len=strlen(sa[i]);
		for(int j=0;j<len;j++){
			switch(sa[i][j]){
				case 'A':
					if(v[now].A==-1){
						v[now].A=v.size();
						v.push_back(Trie());
						now=v[now].A;
					}else now=v[now].A;
					break;
				case 'T':
					if(v[now].T==-1){
						v[now].T=v.size();
						v.push_back(Trie());
						now=v[now].T;
					}else now=v[now].T;
					break;
				case 'G':
					if(v[now].G==-1){
						v[now].G=v.size();
						v.push_back(Trie());
						now=v[now].G;
					}else now=v[now].G;
					break;
				case 'C':
					if(v[now].C==-1){
						v[now].C=v.size();
						v.push_back(Trie());
						now=v[now].C;
					}else now=v[now].C;
			}
			if(j==len-1)v[now].mark=true;
		}
	}
	for(int i=1;i<150021;i++)dp[i]=99999999;
	int length=strlen(goal);
	for(int i=0;i<length;i++){
		int now=0;
		for(int j=0;j<20;j++){
			if(i+j>length)break;
			switch(goal[i+j]){
				case 'A':
					now=v[now].A;
					break;
				case 'T':
					now=v[now].T;
					break;
				case 'G':
					now=v[now].G;
					break;
				case 'C':
					now=v[now].C;
			}
			if(now==-1)break;
			if(v[now].mark){
				for(int k=i+j;k>i;k--)
					dp[k]=min(dp[k],dp[i]+1);
			}
		}
	}
	printf("%d\n",dp[length-1]);
}

2010 A+B Problem
座標圧縮してうめていって足し算した。みんなどうやってやってるのだろう

#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int>A[20001];
pair<int,int>B[20001];
long long temp[200000];
long long zahyou[200000];
int val[200000];
int S[200000];
int T[200000];
int U[200000];
pair<int,long long> out[200000];
int main(){
	int a;
	scanf("%d",&a);
	long long p=0,q=0;
	for(int i=0;i<a;i++){
		scanf("%d%d",&A[i].first,&A[i].second);
		p+=A[i].second;
	}
	int b;
	scanf("%d",&b);
	for(int i=0;i<b;i++){
		scanf("%d%d",&B[i].first,&B[i].second);
		q+=B[i].second;
	}
	int at=0;
	for(int i=0;i<a;i++){
		temp[at++]=p+1;
		temp[at++]=p;
		p-=A[i].second;
	}
	for(int i=0;i<b;i++){
		temp[at++]=q+1;
		temp[at++]=q;
		q-=B[i].second;
	}
	temp[at++]=1;
	std::sort(temp,temp+at);
	int now=0;
	zahyou[now++]=temp[0];
	for(int i=1;i<at;i++){
		if(temp[i]!=temp[i-1])zahyou[now++]=temp[i];
	}
	int K=a-1;
	long long V=A[K].second;
	for(int i=0;i<now;i++){
		while(K>0&&V<zahyou[i]){
			V+=A[K-1].second;
			K--;
		}
		if(K==0&&V<zahyou[i])K--;
		if(K>=0)S[i]=A[K].first;
	}
	K=b-1;
	V=B[K].second;
	for(int i=0;i<now;i++){
		while(K>0&&V<zahyou[i]){
			V+=B[K-1].second;
			K--;
		}
		if(K==0&&V<zahyou[i])K--;
		if(K>=0)T[i]=B[K].first;
	}
	bool up=false;
	for(int i=0;i<now;i++){
		int m=S[i]+T[i];
		if(up)m++;
		if(m>9){
			up=true;
			m-=10;
		}else up=false;
		U[i]=m;
	}
	int ret=0;
	int P=0;
	long long ren=0;
	for(int i=now-1;i>=0;i--){
		if(P!=U[i]){
			if(ret==0&&P==0);
			else out[ret++]=make_pair(P,ren);
			P=U[i];
			ren=zahyou[i]-(i?zahyou[i-1]:0);
		}else ren+=zahyou[i]-(i?zahyou[i-1]:0);;
	}
	out[ret++]=make_pair(P,ren);
	printf("%d\n",ret);
	for(int i=0;i<ret;i++)printf("%d %lld\n",out[i].first,out[i].second);
}

2010 Sengoku
うまいぐあいに二分探索する。

#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
pair<int,int> A[100000];
int ay[100000];
pair<int,int> B[100000];
int by[100000];
int sy[100000];
int a;
int b;
set<int> Y;
int main(){
	int c,n;
	scanf("%d%d",&c,&n);
	for(int i=0;i<n;i++){
		int d,e;
		scanf("%d%d",&d,&e);
		if((d+e)%2)A[a++]=make_pair(d+e,d-e);
		else B[b++]=make_pair(d+e,d-e);
	}
	std::sort(A,A+a);
	std::sort(B,B+b);
	long long ret=0;
	int p=0;
	int q=0;
	for(int i=0;i<a;i++)sy[i]=A[i].second;
	std::sort(sy,sy+a);
	for(int i=0;i<a;i++){
		if(i==0||sy[i]!=sy[i-1])ay[p++]=sy[i];
	}
	for(int i=0;i<b;i++)sy[i]=B[i].second;
	std::sort(sy,sy+b);
	for(int i=0;i<b;i++){
		if(i==0||sy[i]!=sy[i-1])by[q++]=sy[i];
	}
	std::sort(ay,ay+p);
	std::sort(by,by+q);
//	for(int i=0;i<q;i++)printf("%d ",by[i]);
	for(int i=0;i<a;i++){
		int yoko=min(A[i].first+1,c+c-A[i].first-1);
		int tate=min(c-A[i].second,c+A[i].second);
		if(i==0||A[i].first!=A[i-1].first)ret+=yoko;
		if(!Y.count(A[i].second)){
			ret+=tate;
			Y.insert(A[i].second);
		}
		if(i==0||A[i].first!=A[i-1].first)ret-=upper_bound(ay,ay+p,yoko)-lower_bound(ay,ay+p,-yoko);
	//	printf("%d %d %d\n",(yoko+2)/2,(-yoko-2)/2,upper_bound(ay,ay+p,(yoko+2)/2)-lower_bound(ay,ay+p,(-yoko-2)/2));
	//	printf("%lld\n",ret);
	}
//	printf("\n");
	Y.clear();
	for(int i=0;i<b;i++){
		int yoko=min(B[i].first+1,c+c-B[i].first-1);
		int tate=min(c-B[i].second,c+B[i].second);
		if(i==0||B[i].first!=B[i-1].first)ret+=yoko;
		if(!Y.count(B[i].second)){
			ret+=tate;
			Y.insert(B[i].second);
		}
		if(i==0||B[i].first!=B[i-1].first)ret-=upper_bound(by,by+q,yoko)-lower_bound(by,by+q,-yoko);
	//	printf("%d %d %d\n",(yoko+3)/2,(-yoko-3)/2,upper_bound(by,by+q,(yoko+3)/2)-lower_bound(by,by+q,(-yoko-3)/2));
	//	printf("%lld\n",ret);
	}
	printf("%lld\n",ret);
}

2009 Distribution
Greedyっぽいことをなんどもやるだけで解ける。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> g[10000];
int rev[10000];
int dat[10000];
int val[10000];
void dfs(int a,int b){
	val[a]=b+dat[a];
	for(int i=0;i<g[a].size();i++){
		dfs(g[a][i],b+dat[a]);
	}
}
void del(int a){
	if(a<0)return;
	dat[a]=0;
	del(rev[a]);
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	int par=0;
	for(int i=0;i<a;i++){
		int c,d;
		scanf("%d%d",&c,&d);
		if(c==0)
			par=i;
		else{
			g[c-1].push_back(i);
		}
		rev[i]=c-1;
		dat[i]=d;
	}
	int ret=0;
	for(int i=0;i<b;i++){
		dfs(par,0);
		int at=0;
		int M=0;
		for(int j=0;j<a;j++){
			if(val[j]>M){
				M=val[j];
				at=j;
			}
		}
		ret+=M;
		del(at);
	}
	printf("%d\n",ret);
}

2009 Ski
二分探索とDPをした

#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
struct wolf{
	int to,spd,dist;
	wolf(){}
	wolf(int a,int b,int c){
		to=a;
		spd=c;
		dist=b;
	}
};
vector<wolf>g[10000];
bool start[10000];
double dp[10000];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<b;i++){
		int d;
		scanf("%d",&d);
		start[d-1]=true;
	}
	for(int i=0;i<c;i++){
		int p,q,r,s;
		scanf("%d%d%d%d",&p,&q,&r,&s);
		g[p-1].push_back(wolf(q-1,r,s));
	}
	double left=0;
	double right=100000;
	for(int i=0;i<50;i++){
		double M=(left+right)/2;
		for(int j=0;j<a;j++){
			if(start[j])dp[j]=0;
			else dp[j]=99999999;
		}
		for(int j=0;j<a;j++){
			for(int k=0;k<g[j].size();k++){
				dp[g[j][k].to]=min(dp[g[j][k].to],dp[j]+((double)g[j][k].dist-M*g[j][k].dist/g[j][k].spd));
			}
		}
		if(dp[a-1]<0)right=M;
		else left=M;
	}
	printf("%.0f\n",left);
}

2009 Advertisement
昔強連結成分分解知らないときに書いたソース。今はみんな書けるらしい。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
vector<int> g[100000];
vector<vector<int> > scc;
int num[100000];
int low[100000];
int ireji[100000];
stack<int> S;
bool inS[100000];
int time;
int type[100000];
void visit(int v){
	time++;
	low[v]=time;
	num[v]=time;
	S.push(v);
	inS[v]=true;
	for(int i=0;i<g[v].size();i++){
		int w=g[v][i];
		if(num[w]==0){
			visit(w);
			low[v]=min(low[v],low[w]);
		}else if(inS[w]){
			low[v]=min(low[v],num[w]);
		}
	}
	if(low[v]==num[v]){
		scc.push_back(vector<int>());
		while(1){
			int w=S.top();
			S.pop();
			inS[w]=false;
			scc.back().push_back(w);
			if(v==w)break;
		}
	}
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int c,d;
		scanf("%d%d",&c,&d);
		g[c-1].push_back(d-1);
	}
	for(int i=0;i<a;i++){
		if(num[i]==0)visit(i);
	}
	for(int i=0;i<scc.size();i++){
		for(int j=0;j<scc[i].size();j++){
			type[scc[i][j]]=i;
		}
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<g[i].size();j++){
			if(type[i]!=type[g[i][j]]){
				ireji[type[g[i][j]]]++;
			}
		}
	}
	int ret=0;
	for(int i=0;i<scc.size();i++)if(ireji[i]==0)ret++;
	printf("%d\n",ret);
}

2009 Stamps
あぶなっかしいDPで通った。

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[1048576];
pair<int,int> dp1[1048576];
pair<int,int> dp2[1048576];
int main(){
	int a;
	scanf("%d%s",&a,str);
	for(int i=0;i<a;i++){
		dp1[i]=make_pair(999999999,999999999);
		dp2[i]=make_pair(999999999,999999999);
	}
	if(str[0]=='I'){
		dp1[0]=make_pair(0,1);
		dp2[0]=make_pair(1,0);
	}else{
		dp1[0]=make_pair(1,1);
		dp2[0]=make_pair(1,0);
	}
	for(int i=1;i<a;i++){
		dp1[i]=make_pair(dp1[i-1].first+1,dp1[i-1].second);
		dp2[i]=make_pair(dp2[i-1].first+1,dp2[i-1].second);
		if(str[i]=='I'){
			dp1[i]=min(dp1[i],make_pair(dp2[i-1].first,dp2[i-1].second+1));
			dp2[i]=min(dp2[i],make_pair(dp1[i-1].first+1,dp1[i-1].second+1));
		}else{
			dp1[i]=min(dp1[i],make_pair(dp2[i-1].first+1,dp2[i-1].second+1));
			dp2[i]=min(dp2[i],make_pair(dp1[i-1].first,dp1[i-1].second+1));
		}
//		printf("%d %d %d %d\n",dp1[i].first,dp1[i].second,dp2[i].first,dp2[i].second);
	}
	int ans=dp1[a-1].first;
	int p=dp1[a-1].second;
	if(ans>dp2[a-1].first+1||(ans==dp2[a-1].first+1&&p>dp2[a-1].second+1)){
		ans=dp2[a-1].first+1;
		p=dp2[a-1].second+1;
	}
	if(p==0)p=1;
	printf("%d\n%d\n",ans,p);
}

2009 Sequence
メモリ制限をみてソースを長くした。24個だし見た感じビット演算っぽいよね。

#include<stdio.h>
bool mark[1<<24];
int dat[25];
int main(){
	int a;
	long long b,c;
	scanf("%d%lld%lld",&a,&b,&c);
	int val=0;
	for(int i=0;i<a;i++){
		scanf("%d",dat+i);
		dat[i]%=2;
		val+=dat[i]*(1<<i);
	}
	int S=val;
	int T=val;
	int at=val;
	int now=a;
	mark[val]=true;
	int C=0;
	int D=0;
	while(1){
		now++;
		if(((val&1)^(val>>(a-1))))C++;
		val=val/2+(((val&1)^(val>>(a-1)))<<(a-1));
	//	printf("%d\n",val);
		if(mark[val]){
			break;
		}else mark[val]=true;
	}
	int begin=a;
	while(1){
		if(val==at){
			break;
		}
		if(((at&1)^(at>>(a-1))))D++;
		at=at/2+(((at&1)^(at>>(a-1)))<<(a-1));
		begin++;
	}
	b--;
	long long P=0;
	long long Q=0;
	if(b>=now){
		P+=(b-begin)/(now-begin)*(C-D);
		b=begin+(b-begin)%(now-begin);
	}
	if(c>=now){
		Q+=(c-begin)/(now-begin)*(C-D);
		c=begin+(c-begin)%(now-begin);
	}
	for(int i=0;i<b;i++){
		if(i<a)P+=dat[i];
		else{
			if(((S&1)^(S>>(a-1))))P++;
			S=S/2+(((S&1)^(S>>(a-1)))<<(a-1));
		}
	}
	S=T;
	for(int i=0;i<c;i++){
		if(i<a)Q+=dat[i];
		else{
			if(((S&1)^(S>>(a-1))))Q++;
			S=S/2+(((S&1)^(S>>(a-1)))<<(a-1));
		}
	}
	printf("%lld\n",Q-P);
}

2008 Origami
別に平面走査とかしなくても解ける。

#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int> dat[4000000];
int main(){
	int now=0;
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++){
		int d,e,f,g;
		scanf("%d%d%d%d",&d,&e,&f,&g);
		for(int j=d;j<=f;j++)
			for(int k=e;k<=g;k++)
				dat[now++]=make_pair(j,k);
	}
	std::sort(dat,dat+now);
	int ans=1;
	int val=1;
	for(int i=1;i<now;i++){
		if(dat[i].first==dat[i-1].first&&dat[i].second==dat[i-1].second){
			val++;
		}else val=1;
		ans=max(ans,val);
	}
	printf("%d\n",ans);
	int ret=0;
	if(ans==1)ret++;
	val=1;
	for(int i=1;i<now;i++){
		if(dat[i].first==dat[i-1].first&&dat[i].second==dat[i-1].second){
			val++;
		}else val=1;
		if(val==ans)ret++;
	}
	printf("%d\n",ret);
}

2008 Cheeting
二分探査した。

#include<stdio.h>
#include<algorithm>
using namespace std;
int x[100000];
int y[100000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		scanf("%d%d",x+i,y+i);
	}
	std::sort(x,x+b);
	std::sort(y,y+b);
	int left=0;
	int right=1000000000;
	while(left-right){
		int M=(left+right)/2;
		int first=0;
		int use=2;
		for(int i=0;i<b;i++){
			if(x[i]-x[first]>M){
				use++;
				first=i;
			}
		}
		first=0;
		for(int i=0;i<b;i++){
			if(y[i]-y[first]>M){
				use++;
				first=i;
			}
		}
		if(use<=a){
			right=M;
		}else{
			if(left+1==right)break;
			left=M;
		}
	}
	printf("%d\n",right);
}

2008 Nile.com
DPやるだけ

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp1[3000][365];
int dp2[3000][365];
int dp3[3000][365];
int dat[3000][365];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		for(int j=0;j<a;j++){
			scanf("%d",&dat[j][i]);
		}
	}
	for(int i=0;i<3000;i++)
		for(int j=0;j<365;j++)
			dp1[i][j]=dp2[i][j]=dp3[i][j]=99999999;
	for(int i=0;i<a;i++){
		dp1[i][0]=dat[i][0];
	}
	for(int i=1;i<b;i++){
		int nowmin=99999999;
		for(int j=0;j<a;j++){
			nowmin=min(nowmin,dp1[j][i-1]);
			nowmin=min(nowmin,dp2[j][i-1]);
			nowmin=min(nowmin,dp3[j][i-1]);
		}
		for(int j=0;j<a;j++){
			dp1[j][i]=nowmin+dat[j][i];
		}
		for(int j=0;j<a;j++){
			dp2[j][i]=dp1[j][i-1]+dat[j][i]/10*9;
		}
		for(int j=0;j<a;j++){
			dp3[j][i]=min(dp2[j][i-1],dp3[j][i-1])+dat[j][i]/10*7;
		}
	}
	int ret=999999999;
	for(int i=0;i<a;i++){
		ret=min(ret,dp1[i][b-1]);
		ret=min(ret,dp2[i][b-1]);
		ret=min(ret,dp3[i][b-1]);
	}
	printf("%d\n",ret);
}

2008 Flu
バケット法。こういうのは計算量に自信がもてない。

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
pair<int,int> p[100000];
vector<int>w[1000][1000];
int bfs[100000];
int dx[]={1,1,1,0,0,-1,-1,-1,0};
int dy[]={1,0,-1,1,-1,1,0,-1,0};
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	for(int i=0;i<a;i++)scanf("%d%d",&p[i].first,&p[i].second);
	for(int i=0;i<a;i++){
		w[p[i].first/c][p[i].second/c].push_back(i);
	}
	for(int i=0;i<a;i++){
		bfs[i]=99999999;
	}
	bfs[0]=0;
	queue<int> Q;
	Q.push(0);
	while(Q.size()){
		int at=Q.front();
		Q.pop();
		int row=p[at].first/c;
		int col=p[at].second/c;
		for(int i=0;i<9;i++){
			if(0<=row+dx[i]&&row+dx[i]<1000&&0<=col+dy[i]&&col+dy[i]<1000){
				for(int j=0;j<w[row+dx[i]][col+dy[i]].size();j++){
					int q=w[row+dx[i]][col+dy[i]][j];
					if(bfs[q]==99999999&&(p[q].first-p[at].first)*(p[q].first-p[at].first)+(p[q].second-p[at].second)*(p[q].second-p[at].second)<=c*c){
						bfs[q]=bfs[at]+1;
						Q.push(q);
					}
				}
			}
		}
	}
	int ret=0;
	for(int i=0;i<a;i++){
		if(d-b<bfs[i]&&bfs[i]<=d)ret++;
	//	printf("%d ",bfs[i]);
	}
	printf("%d\n",ret);
}

2008 Committee
木DPするだけ

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> t[100000];
int v[100000];
bool visited[100000];
int dp[100000];
int solve(int a){
	if(visited[a])return dp[a];
	int ret=v[a];
	for(int i=0;i<t[a].size();i++)if(solve(t[a][i])>0)ret+=solve(t[a][i]);
	visited[a]=true;
	return dp[a]=ret;
}
int main(){
	int a;
	for(int i=0;i<100000;i++){
		visited[i]=false;
		v[i]=0;
		dp[i]=0;
	}
	scanf("%d",&a);
	int s=0;
	int m=-99999999;
	for(int i=0;i<a;i++){
		int b,c;
		scanf("%d%d",&b,&c);
		if(b!=0)t[b-1].push_back(i);
		else s=i;
		v[i]=c;
		m=max(m,c);
	}
	int ret=m;
	for(int i=0;i<a;i++)ret=max(ret,solve(i));
	printf("%d\n",ret);
}

2007 Lines
幾何と規則性

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int X1[1000],Y1[1000],X2[1000],Y2[1000];
bool v[1000];
double A[1000];
double B[1000];
double C[1000];
pair<double,double>P[1000000];
pair<long long,long long >Q[1000000];
double Abs(double a){return a<0.0?-a:a;}
//ax+by=c
//y=-(a/b)x+(c/b)
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d%d%d",X1+i,Y1+i,X2+i,Y2+i);
		A[i]=Y1[i]-Y2[i];
		B[i]=X2[i]-X1[i];
		C[i]=A[i]*X1[i]+B[i]*Y1[i];
	}
	int n=a;
	for(int i=0;i<a;i++){
		for(int j=i+1;j<a;j++){
			if(v[i]||v[j])continue;
			if((Y2[i]-Y1[i])*(X2[j]-X1[j])==(Y2[j]-Y1[j])*(X2[i]-X1[i])){
				if(X1[i]==X2[i]){
					if(X1[i]==X1[j]){
						v[j]=true;
						n--;
					}
				}else if((Y1[j]-Y1[i])*(X2[i]-X1[i])==(Y2[i]-Y1[i])*(X1[j]-X1[i])){
					v[j]=true;
					n--;
				}
			}
		}
	}
	//printf("%d\n",n);
	int ret=n+1;
	int now=0;
	for(int i=0;i<a;i++){
		for(int j=i+1;j<a;j++){
			if(!v[i]&&!v[j]){
				if((Y2[i]-Y1[i])*(X2[j]-X1[j])==(Y2[j]-Y1[j])*(X2[i]-X1[i]));
				else{
					double X=(double)(C[i]*B[j]-B[i]*C[j])/(A[i]*B[j]-B[i]*A[j]);
					if(Abs(B[i])>0.00001)P[now++]=make_pair(X,(double)(C[i]-X*A[i])/B[i]);
					else P[now++]=make_pair(X,(double)(C[j]-X*A[j])/B[j]);
					Q[now-1].first=(long long)(P[now-1].first*1000000000LL+0.000001);
					Q[now-1].second=(long long)(P[now-1].second*1000000000LL+0.000001);
				}
			}
		}
	}
	std::sort(Q,Q+now);
//	printf("%d\n",ret);
	int val=1;
	for(int i=1;i<now;i++){
	//	printf("%lld %lld\n",Q[i].first,Q[i].second);
		if(Q[i].first==Q[i-1].first&&Q[i].second==Q[i-1].second)val++;
		else{
			int k=(int)sqrt(val*2)+1;
			ret+=k-1;
			val=1;
		}
	}
	if(now==0)val=0;
	int k=(int)sqrt(val*2)+1;
	ret+=k-1;
	val=1;
	printf("%d\n",ret);
}

2007 Fiber
どうかんがえてもUnionFindするだけ。

#include<stdio.h>
int UF[10000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);
	b=FIND(b);
	if(a==b)return;
	UF[a]+=UF[b];
	UF[b]=a;
	return;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)UF[i]=-1;
	for(int i=0;i<b;i++){
		int c,d;
		scanf("%d%d",&c,&d);
		UNION(c-1,d-1);
	}
	int ret=0;
	for(int i=0;i<a;i++)ret+=UF[i]<0?1:0;
	printf("%d\n",ret-1);
}

2007 Route
ここからここまで〜みたいなものを頂点だとおもってDijkstra

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int x[100];
int y[100];
vector<pair<int,int> > g[100];
int ijk[100][100];
bool v[100][100];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d%d",x+i,y+i);
	for(int i=0;i<b;i++){
		int c,d,e;
		scanf("%d%d%d",&c,&d,&e);
		c--;
		d--;
		g[c].push_back(make_pair(d,e));
		g[d].push_back(make_pair(c,e));
	}
	priority_queue<pair<int,pair<int,int> > >Q;
	for(int i=0;i<100;i++)
		for(int j=0;j<100;j++)
			ijk[i][j]=-1;
	for(int i=0;i<g[0].size();i++){
		ijk[0][g[0][i].first]=g[0][i].second;
		Q.push(make_pair(-ijk[0][g[0][i].first],make_pair(0,g[0][i].first)));
	}
	while(Q.size()){
		int cost=-Q.top().first;
		int at1=Q.top().second.first;
		int at2=Q.top().second.second;
		Q.pop();
		if(v[at1][at2])continue;
		v[at1][at2]=true;
		for(int i=0;i<g[at2].size();i++){
			if(!v[at2][g[at2][i].first]&&!(~ijk[at2][g[at2][i].first]&&ijk[at2][g[at2][i].first]<=cost+g[at2][i].second)&&(x[at1]-x[at2])*(x[g[at2][i].first]-x[at2])+(y[at1]-y[at2])*(y[g[at2][i].first]-y[at2])<=0){
				ijk[at2][g[at2][i].first]=cost+g[at2][i].second;
				Q.push(make_pair(-ijk[at2][g[at2][i].first],make_pair(at2,g[at2][i].first)));
			}
		}
	}
	int ret=999999999;
	for(int i=0;i<a;i++){
		if(~ijk[i][1])ret=min(ret,ijk[i][1]);
	}
	if(ret!=999999999)printf("%d\n",ret);
	else printf("-1\n");
}

2007 Anagram
very simple 数学

#include<stdio.h>
char str[21];
int use[26];
long long C(int a,int b){
	long long ret=1;
	for(int i=0;i<b;i++){
		ret*=a-i;
		ret/=(i+1);
	}
	return ret;
}
long long calc(){
	long long ret=1;
	int sum=0;
	for(int i=0;i<26;i++){
		sum+=use[i];
	}
	for(int i=0;i<26;i++){
		ret*=C(sum,use[i]);
		sum-=use[i];
	}
	return ret;
}
int main(){
	scanf("%s",str);
	for(int i=0;str[i];i++)use[str[i]-'A']++;
	long long ret=0;
	for(int i=0;str[i];i++){
		for(int j=0;j+'A'<str[i];j++){
			if(use[j]){
				use[j]--;
				ret+=calc();
				use[j]++;
			}
		}
		use[str[i]-'A']--;
	}
	printf("%lld\n",ret+1);
}

2007 Fermat
数学

#include<stdio.h>
int rj[10000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		int now=1;
		int val=i;
		int c=b;
		while(c){
			if(c%2)now=now*val%a;
			val=val*val%a;
			c/=2;
		}
	//	printf("%d ",now);
		rj[now]++;
	}
	long long ret=0;
	for(int i=0;i<a;i++){
		ret+=rj[i]*rj[(i+1)%a];
	}
	ret*=a-1;
	for(int i=0;i<a;i++){
		ret+=rj[i]*rj[i];
	}
	printf("%lld\n",ret);
}

2007 Building
いまや常識レベルのDP

#include<stdio.h>
#include<algorithm>
using namespace std;
int dat[1000];
int dp[1000];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",dat+i);
	dp[0]=1;
	int ret=1;
	for(int i=1;i<a;i++){
		dp[i]=1;
		for(int j=0;j<i;j++){
			if(dat[j]<dat[i])dp[i]=max(dp[i],dp[j]+1);
		}
		ret=max(ret,dp[i]);
	}
	printf("%d\n",ret);
}

2007 Mall
よくある問題 解法を忘れるレベルの昔といた

#include<stdio.h>
long long t[1000][1000];
long long p[1001][1001];
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&b,&a,&d,&c);
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			scanf("%lld",&t[i][j]);
			if(t[i][j]==-1)t[i][j]=100000000LL;
		}
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			p[i+1][j+1]=p[i][j+1]+p[i+1][j]-p[i][j]+t[i][j];
		}
	}
	long long ret=1000000000LL;
	for(int i=c-1;i<a;i++){
		for(int j=d-1;j<b;j++){
			if(ret>p[i+1][j+1]-p[i+1][j+1-d]-p[i+1-c][j+1]+p[i+1-c][j+1-d])ret=p[i+1][j+1]-p[i+1][j+1-d]-p[i+1-c][j+1]+p[i+1-c][j+1-d];
		}
	}
	printf("%lld\n",ret);
}

2007 Factorial
数学ってほどでもない

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
	int a;
	scanf("%d",&a);
	int b=a;
	int now=2;
	int ret=0;
	while(a-1&&now*now<=a){
		int val=0;
		while(a%now==0){
			a/=now;
			val++;
		}
		if(val)ret=max(ret,val*now);
		now++;
	}
	if(a==1)printf("%d\n",ret);
	else printf("%d\n",max(ret,a));
}

2007 Score
クソゲー

#include<stdio.h>
#include<algorithm>
#include<functional>
using namespace std;
int score[100000];
int val[100000];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",score+i);
		val[i]=score[i];
	}
	std::sort(val,val+a,greater<int>());
	for(int i=0;i<a;i++){
		int t=lower_bound(val,val+a,score[i],greater<int>())-val;
		printf("%d\n",t+1);
	}
}

途中からブログの編集窓がどんどん重くなっていった。こわすぎる