JOI 予選

満点狙いで行ったけど多分バグって116点。

1:やる

#include<stdio.h>
#include "stdafx.h"
#include<algorithm>
using namespace std;
int main()
{
	FILE *fr=fopen("2013-yo-t1-in5.txt","r");
	FILE *fw=fopen("out5.txt","w");
	int res,pa,pb,sa,sb;
	fscanf(fr,"%d%d%d%d%d",&res,&pa,&pb,&sa,&sb);
	fprintf(fw,"%d\n",res-max((pa+sa-1)/sa,(pb+sb-1)/sb));
}

2:やる

#include<stdio.h>
#include "stdafx.h"
#include<vector>
#include<algorithm>
using namespace std;
int hai[3][101];
int main()
{
	FILE *fr=fopen("2013-yo-t2-in5.txt","r");
	FILE *fw=fopen("out5.txt","w");
	int num;
	fscanf(fr,"%d",&num);
	vector<int>vec[3];
	for(int i=0;i<num;i++)
	{
		int za,zb,zc;
		fscanf(fr,"%d%d%d",&za,&zb,&zc);
		hai[0][za]++;
		hai[1][zb]++;
		hai[2][zc]++;
		vec[0].push_back(za);
		vec[1].push_back(zb);
		vec[2].push_back(zc);
	}
	for(int i=0;i<num;i++)
	{
		int sum=0;
		for(int j=0;j<3;j++)
		{
			if(hai[j][vec[j][i]]<=1)
			{
				sum+=vec[j][i];
			}
		}
		fprintf(fw,"%d\n",sum);
	}
}

3:やる。ファイルからのcinが分からないのでつくった。

#include<stdio.h>
#include "stdafx.h"
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
FILE *fr;
FILE *fw;
string rea()
{
	string ret;
	for(;;)
	{
		char zan;
		fscanf(fr,"%c",&zan);
		if(zan=='\n')
		{
			break;
		}
		ret.push_back(zan);
	}
	return ret;
}
int main()
{
	fr=fopen("2013-yo-t3-in5.txt","r");
	fw=fopen("out5.txt","w");
	int num;
	char gomi;
	fscanf(fr,"%d%c",&num,&gomi);
	string mok=rea();
	int ret=0;
	for(int i=0;i<num;i++)
	{
		string zan=rea();
		bool han=false;
		for(int j=0;j<zan.size();j++)
		{
			for(int k=1;k<zan.size();k++)
			{
				if(j+k*(mok.size()-1)>=zan.size())
				{
					break;
				}
				bool jud=true;
				for(int l=0;l<mok.size();l++)
				{
					if(mok[l]!=zan[j+k*l])
					{
						jud=false;
					}
				}
				if(jud)
				{
					han=true;
				}
			}
		}
		if(han)
		{
			ret++;
		}
	}
	fprintf(fw,"%d\n",ret);
}

4:DP。

#include<stdio.h>
#include "stdafx.h"
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
typedef pair<int,int>pii;
typedef pair<int,pii>pi3;
int dp[200][200];
int main()
{
	FILE *fr=fopen("2013-yo-t4-in5.txt","r");
	FILE *fw=fopen("out5.txt","w");
	int num,clo;
	fscanf(fr,"%d%d",&num,&clo);
	vector<int>tem;
	for(int i=0;i<num;i++)
	{
		int zan;
		fscanf(fr,"%d",&zan);
		tem.push_back(zan);
	}
	vector<pi3>vec;
	for(int i=0;i<clo;i++)
	{
		int za,zb,zc;
		fscanf(fr,"%d%d%d",&za,&zb,&zc);
		vec.push_back(make_pair(zc,make_pair(za,zb)));
	}
	for(int i=0;i<200;i++)
	{
		for(int j=0;j<200;j++)
		{
			dp[i][j]=-1000000000;
		}
	}
	for(int i=0;i<clo;i++)
	{
		if(vec[i].second.first<=tem[0]&&tem[0]<=vec[i].second.second)
		{
			dp[0][i]=0;
		}
	}
	for(int i=1;i<num;i++)
	{
		for(int j=0;j<clo;j++)
		{
			if(vec[j].second.first<=tem[i]&&tem[i]<=vec[j].second.second)
			{
				for(int k=0;k<clo;k++)
				{
					dp[i][j]=max(dp[i][j],dp[i-1][k]+abs(vec[k].first-vec[j].first));
				}
			}
		}
	}
	int maxi=0;
	for(int i=0;i<clo;i++)
	{
		maxi=max(maxi,dp[num-1][i]);
	}
	fprintf(fw,"%d\n",maxi);
}

5:座圧。予選で座圧出るとはびっくり。いもす法したくなるけど予選なのでしなくてもよい。

#include<stdio.h>
#include "stdafx.h"
#include<vector>
#include<algorithm>
#define mp(A,B) make_pair(A,B)
#define mq(A,B,C,D) mp(mp(A,B),mp(C,D))
#define ms(A,B,C,D,E,F) mp(mp(A,B),mq(C,D,E,F))
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pii;
typedef pair<pii,pii>pi4;
typedef pair<pii,pi4>pi6;
vector<ll>uni(vector<ll>vec)
{
	vector<ll>ret;
	ll now=-1;
	for(int i=0;i<vec.size();i++)
	{
		if(now!=vec[i])
		{
			ret.push_back(vec[i]);
			now=vec[i];
		}
	}
	return ret;
}
int map[100][100][100];
int main()
{
	FILE *fr=fopen("2013-yo-t5-in5.txt","r");
	FILE *fw=fopen("out5.txt","w");
	int num,gen;
	fscanf(fr,"%d%d",&num,&gen);
	vector<pi6>vec;
	vector<ll>sx,sy,sd;
	for(int i=0;i<num;i++)
	{
		ll za,zb,zc,zd,ze,zf;
		fscanf(fr,"%lld%lld%lld%lld%lld%lld",&za,&zb,&zc,&zd,&ze,&zf);
		vec.push_back(ms(za,zd,zb,ze,zc,zf));
		sx.push_back(za);
		sx.push_back(zd);
		sy.push_back(zb);
		sy.push_back(ze);
		sd.push_back(zc);
		sd.push_back(zf);
	}
	sort(sx.begin(),sx.end());
	sort(sy.begin(),sy.end());
	sort(sd.begin(),sd.end());
	sx=uni(sx);
	sy=uni(sy);
	sd=uni(sd);
	for(int i=0;i<num;i++)
	{
		int low1=lower_bound(sx.begin(),sx.end(),vec[i].first.first)-sx.begin();
		int low2=lower_bound(sx.begin(),sx.end(),vec[i].first.second)-sx.begin();
		int low3=lower_bound(sy.begin(),sy.end(),vec[i].second.first.first)-sy.begin();
		int low4=lower_bound(sy.begin(),sy.end(),vec[i].second.first.second)-sy.begin();
		int low5=lower_bound(sd.begin(),sd.end(),vec[i].second.second.first)-sd.begin();
		int low6=lower_bound(sd.begin(),sd.end(),vec[i].second.second.second)-sd.begin();
		for(int j=low1;j<low2;j++)
		{
			for(int k=low3;k<low4;k++)
			{
				for(int l=low5;l<low6;l++)
				{
					map[j][k][l]++;
				}
			}
		}
	}
	ll ret=0;
	for(int i=0;i<sx.size()-1;i++)
	{
		for(int j=0;j<sy.size()-1;j++)
		{
			for(int k=0;k<sd.size()-1;k++)
			{
				if(map[i][j][k]>=gen)
				{
					ret+=(sx[i+1]-sx[i])*(sy[j+1]-sy[j])*(sd[k+1]-sd[k]);
				}
			}
		}
	}
	fprintf(fw,"%lld\n",ret);
}

6:難しかった。DP。直前5回分くらいを覚えておくと解ける。(testcase1でバグって16点なはず)
ソースコードは検算用に6個前まで持ったのを上げてる。

#include<stdio.h>
#include "stdafx.h"
#include<vector>
#include<algorithm>
using namespace std;
int dp[4][52][52][4096];
int map[53][53];
bool isused(int hash,int nx,int ny,int mx,int my)
{
	int ps[6];
	for(int q=0;q<6;q++)
	{
		ps[q]=hash%4;
		hash/=4;
	}
	bool han=false;
	for(int q=0;q<6;q++)
	{
		if(ps[q]==0)
		{
			nx++;
		}
		if(ps[q]==1)
		{
			ny++;
		}
		if(ps[q]==2)
		{
			nx--;
		}
		if(ps[q]==3)
		{
			ny--;
		}
		if(nx==mx&&ny==my)
		{
			return true;
		}
	}
	return false;
}
int main()
{
	FILE *fr=fopen("2013-yo-t6-in5.txt","r");
	FILE *fw=fopen("out5.txt","w");
	int mx,my,gen;
	fscanf(fr,"%d%d%d",&mx,&my,&gen);
	for(int i=0;i<53;i++)
	{
		for(int j=0;j<53;j++)
		{
			map[i][j]=-1;
		}
	}
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<52;j++)
		{
			for(int k=0;k<52;k++)
			{
				for(int l=0;l<4096;l++)
				{
					dp[i][j][k][l]=-1000000000;
				}
			}
		}
	}
	dp[0][1][1][4095]=0;
	for(int i=0;i<mx;i++)
	{
		for(int j=0;j<my;j++)
		{
			char zan;
			fscanf(fr," %c",&zan);
			if(zan=='.')
			{
				map[i][j]=0;
			}
			if('1'<=zan&&zan<='9')
			{
				map[i][j]=zan-'0';
			}
		}
	}
	for(int k=0;k<=gen;k++)
	{
		for(int i=0;i<mx;i++)
		{
			for(int j=0;j<my;j++)
			{
				if(map[i][j]==-1)
				{
					continue;
				}
				for(int p=0;p<4096;p++)
				{
					int zp=p;
					p%=1024;
					if(isused(zp,i+1-1,j+1,i+1,j+1))
					{
						dp[k][i+1][j+1][p*4+2]=max(dp[k][i+1][j+1][p*4+2],dp[k][i+1-1][j+1][zp]);
					}
					else
					{
						dp[k][i+1][j+1][p*4+2]=max(dp[k][i+1][j+1][p*4+2],dp[k][i+1-1][j+1][zp]+map[i][j]);
					}
					if(isused(zp,i+1,j+1-1,i+1,j+1))
					{
						dp[k][i+1][j+1][p*4+3]=max(dp[k][i+1][j+1][p*4+3],dp[k][i+1][j+1-1][zp]);
					}
					else
					{
						dp[k][i+1][j+1][p*4+3]=max(dp[k][i+1][j+1][p*4+3],dp[k][i+1][j+1-1][zp]+map[i][j]);
					}
					if(k!=0)
					{	
						if(!isused(zp,i+1+1,j+1,i+1,j+1))
						{
							dp[k][i+1][j+1][p*4]=max(dp[k][i+1][j+1][p*4],dp[k-1][i+1+1][j+1][zp]+map[i][j]);
						}
						if(!isused(zp,i+1,j+1+1,i+1,j+1))
						{
							dp[k][i+1][j+1][p*4+1]=max(dp[k][i+1][j+1][p*4+1],dp[k-1][i+1][j+1+1][zp]+map[i][j]);
						}
					}
					p=zp;
				}
				int m=0;
				for(int q=0;q<4096;q++)
				{
					m=max(m,dp[k][i+1][j+1][q]);
				}
			}
		}
	}
	int maxi=0;
	for(int i=0;i<=gen;i++)
	{
		for(int j=0;j<4096;j++)
		{
			maxi=max(maxi,dp[i][mx][my][j]);
		}
	}
	fprintf(fw,"%d\n",maxi);
}

http://gyazo.com/f09b304d3e0f2ec7c6c163205153f74f
これはすくしょとったのをあとからgyazoってるので不正ではないです