AOJ 1204

• 解法

最後のnクロックの状態と次にpipelineに入れられる仕事の番号を使って拡張ダイクストラをする。int dist[21][1<<20]とかやるとMLEするのでsetを使う。

//AOJ1204
#include <stdio.h>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <set>
#define INF (1<<20)
#define W 10
using namespace std;
struct State{
	int time,next,line;
};
State makeS(int t,int nn,int l){
	State s;
	s.time=t,s.next=nn,s.line=l;
	return s;
}
bool operator < (const State &s,const State &t){
	return s.time>t.time;
}
int n;
int used[5];
char as[5][30];
int pi[30];
int check(int line){
	memset(used,0,sizeof(used));
	for(int i=n-1;0<=i;i--)
		if(line&(1<<i))
			used[pi[n-1-i]]++;
	for(int i=0;i<5;i++)
		if(1<used[i])
			return 0;
	return 1;
}
int main(){
	while(1){
		scanf("%d",&n);
		if(n==0)	break;
		for(int i=0;i<5;i++)scanf("%s",as[i]);
		for(int i=0;i<n;i++)for(int j=0;j<5;j++)if(as[j][i]=='X')pi[i]=j;
		int ans;
		priority_queue<State> que;
		set<pair<int,int> > se;
		que.push(makeS(0,0,0));
		se.insert(make_pair(0,0));
		while(!que.empty()){
			State s=que.top();que.pop();
			if(s.next==10&&s.line==1){ans=s.time;break;}
			int l=s.line>>1,ok=check(l);
			if(!ok)	continue;
			if(s.next==W){
				if(se.find(make_pair(W,l))==se.end()){
					se.insert(make_pair(W,l));
					que.push(makeS(s.time+1,W,l));
				}
			}else{
				int ll=l|(1<<(n-1));
				if(check(ll)){
					if(se.find(make_pair(s.next+1,ll))==se.end()){
						se.insert(make_pair(s.next+1,ll));
						que.push(makeS(s.time+1,s.next+1,ll));
					}
				}
				if(se.find(make_pair(s.next,l))==se.end()){
					se.insert(make_pair(s.next,l));
					que.push(makeS(s.time+1,s.next,l));
				}
			}
		}
		printf("%d\n",ans);
	}
}

JOI2012本選5番

ダイクストラして最大全域木求めてLCAする全部入り問題。

#include <vector>
#include <queue>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
#define MAX_V 100000+10
#define MAX_Q 100000+10
#define INF (1<<28)
#define ROOT 1
using namespace std;
struct Edge{
	int to,cost;
};
Edge makeE(int t,int c){
	Edge e;e.to=t,e.cost=c;
	return e;
}
bool operator < (const Edge &e,const Edge &f){
	return e.cost>f.cost;
}
struct Biedge{
	int a,b,cost;
};
Biedge makeB(int aa,int bb,int c){
	Biedge e;e.a=aa,e.b=bb,e.cost=c;
	return e;
}
bool operator < (const Biedge &e,const Biedge &f){
	return e.cost>f.cost;
}
class Unionfind{
	public:
		vector<int> data;
		Unionfind(int n){
			for(int i=0;i<n;i++)
				data.push_back(i);
		}
		int root(int a){
			//printf("root(%d)\n",a);
			if(data[a]==a)	return a;
			else		return data[a]=root(data[a]);
		}
		void set(int a,int b){
			if(root(a)==root(b))
				return;
			else
				data[root(a)]=root(b);
		}
};
int fest[MAX_V],dist[MAX_V],qa[MAX_Q],qb[MAX_Q],qr[MAX_Q],depth[MAX_V],score[32][MAX_V],parent[32][MAX_V];
vector<Biedge> biedge;
vector<Edge> G[MAX_V];
vector<Edge> MG[MAX_V];
void dfs(int v,int p,int s,int d){
	parent[0][v]=p;
	score[0][v]=s;
	depth[v]=d;
	for(int i=0;i<(int)MG[v].size();i++)
		if(MG[v][i].to!=p)
			dfs(MG[v][i].to,v,MG[v][i].cost,d+1);
}
void init(int n){
	dfs(ROOT,-1,dist[ROOT],0);
	for(int k=0;k+1<32;k++)
		for(int i=0;i<n;i++){
			if(parent[k][i]<0)	parent[k+1][i]=-1;
			else{
				score[k+1][i]=min(score[k][parent[k][i]],score[k][i]);
				parent[k+1][i]=parent[k][parent[k][i]];
			}
		}
}
int lca(int u,int v){
	int res=INF;
	if(depth[u]>depth[v])	swap(u,v);
	for(int k=0;k<32;k++)
		if((depth[v]-depth[u])>>k&1){
			res=min(res,score[k][v]);
			v=parent[k][v];
		}
	//printf("lca-m\n");fflush(stdout);
	if(u==v)	return res;
	for(int k=31;0<=k;k--)
		if(parent[k][u]!=parent[k][v]){
			res=min(res,score[k][u]);
			u=parent[k][u];
			res=min(res,score[k][v]);
			v=parent[k][v];
		}
	res=min(res,score[0][u]);
	res=min(res,score[0][v]);
	return res;
}
int main(){
	int n,m,k,q;
	scanf("%d%d%d%d",&n,&m,&k,&q);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		G[a].push_back(makeE(b,c));
		G[b].push_back(makeE(a,c));
		biedge.push_back(makeB(a,b,0));
	}
	for(int i=0;i<k;i++)
		scanf("%d",fest+i);
	for(int i=0;i<q;i++)
		scanf("%d%d",qa+i,qb+i);
	for(int i=0;i<MAX_V;i++)
		dist[i]=INF;
	priority_queue<Edge> que;
	for(int i=0;i<k;i++){
		que.push(makeE(fest[i],0));
		dist[fest[i]]=0;
	}
	while(!que.empty()){
		int t=que.top().to,c=que.top().cost;
		que.pop();
		if(dist[t]<c)
			continue;
		for(int i=0;i<(int)G[t].size();i++){
			int tt=G[t][i].to,cc=c+G[t][i].cost;
			if(cc<dist[tt]){
				que.push(makeE(tt,cc));
				dist[tt]=cc;
			}
		}
	}
	for(int i=0;i<m;i++)
		biedge[i].cost=min(dist[biedge[i].a],dist[biedge[i].b]);
	sort(biedge.begin(),biedge.end());
	memset(qr,-1,sizeof(qr));
	Unionfind un(n+1);
	for(int i=0;i<m;i++){
		if(un.root(biedge[i].a)!=un.root(biedge[i].b)){
			un.set(biedge[i].a,biedge[i].b);
			MG[biedge[i].a].push_back(makeE(biedge[i].b,biedge[i].cost));
			MG[biedge[i].b].push_back(makeE(biedge[i].a,biedge[i].cost));
		}
	}
	init(n+1);
	for(int i=0;i<q;i++)
		printf("%d\n",lca(qa[i],qb[i]));
	return 0;
}

JOI2012本選４番

講義資料 - いもす研 (imos laboratory)
↑参照。
累積和を使ったコード

#include <stdio.h>
int nails[5010][5010];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b,x;
		scanf("%d%d%d",&a,&b,&x);
		nails[a][b]++,nails[a][b+1]--;
		nails[a+x+1][b]--,nails[a+x+2][b+1]++;
		nails[a+x+1][b+x+2]++,nails[a+x+2][b+x+2]--;
	}
	for(int i=0;i<5010;i++){
		int a=0;
		for(int j=0;j<5010;j++){
			a+=nails[i][j];
			nails[i][j]=a;
		}
	}
	for(int i=0;i<5010;i++){
		int a=0;
		for(int j=0;j<5010;j++){
			a+=nails[j][i];
			nails[j][i]=a;
		}
	}
	for(int i=0;i<5010;i++){
		int a=0;
		for(int j=0;i+j<5010;j++){
			a+=nails[i+j][j];
			nails[i+j][j]=a;
		}
	}
	int ans=0;
	for(int i=0;i<5010;i++)
		for(int j=0;j<5010;j++)
			if(0<nails[i][j])
				ans++;
	printf("%d\n",ans);
	return 0;
}

最大値の伝搬を使ったコード（ただし後ろから）。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int nails[5010][5010];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	memset(nails,0,sizeof(nails));
	for(int i=0;i<m;i++){
		int a,b,x;
		scanf("%d%d%d",&a,&b,&x);
		nails[a+x][b+x]=max(nails[a+x][b+x],x+1);
	}
	int ans=0;
	for(int y=n;0<=y;y--)
		for(int x=n;0<=x;x--){
			if(0<nails[y][x])
				ans++;
			if(0<x)
				nails[y][x-1]=max(nails[y][x-1],nails[y][x]-1);
			if(0<x&&0<y)
				nails[y-1][x-1]=max(nails[y-1][x-1],nails[y][x]-1);
		}
	printf("%d\n",ans);
	return 0;
}

JOI2012本選3番

時間がSにかぶるときだけ気をつけてdpすればOK。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n,S,T;
int A[3010],B[3010];
int dp[3010][3010];
int rec(int store,int time){
	if(store==n)
		return 0;
	else if(dp[store][time]!=-1)
		return dp[store][time];
	else{
		int res=rec(store+1,time);
		if(time<S&&S<time+B[store]){
			if(S+B[store]<=T){
				res=max(res,rec(store+1,S+B[store])+A[store]);
			}
		}else{
			if(time+B[store]<=T){
				res=max(res,rec(store+1,time+B[store])+A[store]);
			}
		}
		return dp[store][time]=res;
	}
}
int main(){
	scanf("%d%d%d",&n,&T,&S);
	for(int i=0;i<n;i++)
		scanf("%d%d",A+i,B+i);
	memset(dp,-1,sizeof(dp));
	int ans=rec(0,0);
	printf("%d\n",ans);
	return 0;
}

JOI2012本選2番

dp[ap=Aの何枚目か][bp=Bの何枚目か]でDPした。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[5010][5010];
int ac[5010],bc[5010];
int rec(int ap,int bp){
	if(ap<0||bp<0)
		return 0;
	else if(dp[ap][bp]!=-1)
		return dp[ap][bp];
	else{
		int r=rec(ap-1,bp);
		if(ac[ap]==bc[bp])
			r=max(r,rec(ap-1,bp-1)+1);
		return dp[ap][bp]=r;
	}
}
int main(){
	int an,bn;
	scanf("%d%d",&an,&bn);
	for(int i=0;i<an;i++)
		scanf("%d",ac+i);
	for(int i=0;i<bn;i++)
		scanf("%d",bc+i);
	memset(dp,-1,sizeof(dp));
	int ans=0;
	for(int i=0;i<an;i++)
		for(int j=0;j<bn;j++)
			ans=max(ans,rec(i,j));
	printf("%d\n",ans);
	return 0;
}

JOI2012本選1番

解説を聞いてから自分のやっていたことがRunLength圧縮と同じであると気づいた。

#include <stdio.h>
#include <vector>
using namespace std;
char in[10000000+10];
int main(){
	scanf("%s",in);
	vector<int> ch,sq;
	int c=in[0],s=1;
	for(int i=1;in[i]!=0&&in[i]!='\n';i++){
		if(c!=in[i]){
			ch.push_back(c);
			sq.push_back(s);
			c=in[i];
			s=1;
		}else{
			s++;
		}
	}
	ch.push_back(c);
	sq.push_back(s);
	int ans=0;
	for(int i=0;i+2<(int)ch.size();i++){
		if(ch[i]=='J'&&ch[i+1]=='O'&&ch[i+2]=='I'&&sq[i+1]<=min(sq[i],sq[i+2]))
			ans=max(ans,min(sq[i],sq[i+1]));
	}
	printf("%d\n",ans);
	return 0;
}

JOI2012本選まとめ

↑の大会に参加してきました。
実力を限界まで発揮できたと思います。
合宿は問題を楽しむだけにしようと思います。