JOI予選参加記

JOI 2015/2016 予選 問題文・採点用入出力・解説
こことのdiffを取ってみたら520だった
適当な解説とソースコードだけ貼ります
問1
やるだけ

int main(){
	int a[4],b[2];
	REP(i,4)cin>>a[i];
	REP(i,2)cin>>b[i];
	sort(a,a+4);
	sort(b,b+2);
	cout<<a[3]+a[2]+a[1]+b[1]<<endl;
	return 0;
}

問2
swapでゴリ押し

int a[110];
int main(){
	int n,m;
	cin>>n>>m;
	REP(i,n)cin>>a[i];
	for(int k=1;k<=m;k++){
		REP(i,n-1){
			if(a[i]%k>a[i+1]%k){
				swap(a[i],a[i+1]);
			}
		}
	}
	REP(i,n)cout<<a[i]<<endl;
	return 0;
}

問3

dp解もあるらしいけど全探索しました
char fld[55][55];
int h,w;
int rec(int r,int l){
	int cnt=0;
	for(int i=0;i<=r;i++)REP(j,w)if(fld[j][i]!='W')cnt++;
	for(int i=r+1;i<=l;i++)REP(j,w)if(fld[j][i]!='B')cnt++;
	for(int i=l+1;i<h;i++)REP(j,w)if(fld[j][i]!='R')cnt++;
	return cnt;
}
int main(){
	cin>>h>>w;
	REP(i,h)REP(j,w)cin>>fld[j][i];
	int ans=INF;
	for(int i=0;i<h;i++){
		for(int j=i+1;j<h-1;j++){
			ans=min(ans,rec(i,j));
		}
	}
	cout<<ans<<endl;
	return 0;
}

問4
隣同士で左側が東、右側が西になっている（反対側にすすんでいく）場所を保存してほげ

int n,q,d[100100];
ll t,a[100100];
ll dist[100100];
vector<int> dat;
int main(){
	scanf("%d%lld%d",&n,&t,&q);
	REP(i,n){
		scanf("%lld%d",&a[i],&d[i]);
	}
	if(d[0]==1)dat.PB(0);
	REP(i,n-1){
		if(d[i]==2&&d[i+1]==1)dat.PB(i+1);
	}
	if(d[n-1]==2)dat.PB(n);
	for(int i=0;i<dat[0];i++){
		dist[i]=a[i]-t;
	}
	for(int i=0;i<dat.size()-1;i++){
		ll btw;
		for(int j=dat[i];j<dat[i+1]-1;j++){
			if(d[j]==1&&d[j+1]==2){
				btw=(a[j]+a[j+1])/2LL;
			}
		}
		for(int j=dat[i];j<dat[i+1];j++){
			if(d[j]==1){
				dist[j]=min(a[j]+t,btw);
			}else{
				dist[j]=max(a[j]-t,btw);
			}
		}
	}
	for(int i=dat[dat.size()-1];i<n;i++){
		dist[i]=a[i]+t;
	}
	int x;
	REP(i,q){
		scanf("%d",&x);x--;
		cout<<dist[x]<<endl;
	}
	return 0;
}

問5
幅とダイクストラゴリ押し
計算量考えてなかったけどなんかできた

int n,m,k,s,p,q,c[100100];
ll d[100100];
bool ok[100100];
bool no[100100];
bool used[100100];
vector<int> G[100100];
ll INF =(1<<29)-1;
void dijkstra(int s){
	priority_queue<P,vector<P>,greater<P> > Q;
	fill(d,d+n,LLONG_MAX);
	d[s]=0;
	Q.push(P(0,s));
	while(!Q.empty()){
		P pp=Q.top();Q.pop();
		int v=pp.second;
		if(d[v]<pp.first)continue;
		if(no[v])continue;
		for(int i=0;i<G[v].size();i++){
			int to=G[v][i];
			int cost=(ok[to]?q:p);
			if(d[to]>d[v]+cost){
				d[to]=d[v]+cost;
				Q.push(P(d[to],to));
			}
		}
	}
}
int main(){
	memset(ok,false,sizeof(ok));
	memset(no,false,sizeof(no));
	scanf("%d%d%d%d",&n,&m,&k,&s);
	scanf("%d%d",&p,&q);
	REP(i,k)scanf("%d",&c[i]);
	REP(i,m){
		int a,b;
		scanf("%d%d",&a,&b);a--;b--;
		G[a].PB(b);G[b].PB(a);
	}
	REP(i,k){
		c[i]--;
		memset(used,false,sizeof(used));
		no[c[i]]=ok[c[i]]=true;
		queue<P> Q;
		Q.push(P(c[i],0));
		while(!Q.empty()){
			P pp=Q.front();Q.pop();
			if(pp.second>=s)break;
			int v=pp.first;
			REP(i,G[v].size()){
				int to=G[v][i];
				if(!used[to]){
					used[to]=true;
					ok[to]=true;
					Q.push(P(to,pp.second+1));
				}
			}
		}
	}
	dijkstra(0);
	if(ok[n-1])cout<<d[n-1]-q<<endl;
	else cout<<d[n-1]-p<<endl;
	return 0;
}

問6
bitDPだなーと思って実装してたらわけわからなくなって死
6-1だけ紙で解いた

問6に1時間半以上も残したのに解けなかったのが痛かった
ボーダーは全完って聞いてるので予選落ちです