JOI 2015 予選参加記

JOI

はい、というわけでもちろん今年も参加しました。
が、残念な結果に終わったので本選まで今まで以上に精進しようと思います。
適当な解説を書きます。テンプレはいつも通り省略してます

1.水道料金 (Water Rate)

やるだけ。

int A,B,C,D,p;
int main()
{
	cin >> A;
	cin >> B;
	cin >> C;
	cin >> D;
	cin >> p;
	int X=0,Y=0;
	X = A*p;
	Y = B;
	if(p>C)Y += (p-C)*D;
	cout << min(X,Y) << endl;
	return 0;
}
2.クリスマスパーティー (Christmas Party)

これもやるだけ。書いてあるとおりにシミュレーション

int N,M;
int A[105],B[105][105],score[105];
int main()
{
	cin >> N;
	cin >> M;
	for(int i=0;i<M;i++)
	{
		cin >> A[i];
		A[i]--;
	}
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			cin >> B[i][j];
			B[i][j]--;
		}
	}
	for(int i=0;i<M;i++)
	{
		int cnt = 0;
		for(int j=0;j<N;j++)
		{
			if(B[i][j]==A[i])score[j]++;
			else cnt++;
		}
		score[A[i]]+=cnt;
	}
	for(int i=0;i<N;i++)cout << score[i] << endl;
	return 0;
}
3.気象予報士 (Weather Forecaster)

これもやるだけ。

char f[105][105];
int H,W;
int solve(int x,int y)
{
	int res = -1;
	for(int i=0;i<=y;i++)if(f[x][i]=='c')res = i;
	if(res == -1)return -1;
	return y-res;
}
int main()
{
	cin >> H >> W;
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			cin >> f[i][j];
		}
	}
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			printf("%d%c",solve(i,j),((j==W-1)?'\n':' '));
		}
	}
	return 0;
}
4.シルクロード (Silk Road)

これもやるだけ。適当にDP。

int dp[1050][1050];
int N,M;
int C[1050],D[1050];
int main()
{
	for(int i=0;i<1050;i++)
	{
		for(int j=0;j<1050;j++)
		{
			dp[i][j]=INF;
		}
	}
	cin >> N >> M;
	for(int i=0;i<N;i++)cin >> D[i];
	for(int i=0;i<M;i++)cin >> C[i];
	dp[0][0]=0;
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			if(dp[i][j]==INF)continue;
			dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+C[i]*D[j]);
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
		}
	}
	int ans = INF;
	for(int i=0;i<=M;i++)ans = min(ans,dp[i][N]);
	cout << ans << endl;
	return 0;
}
5.砂の城 (Sandcastle)

これもやるだけ。8近傍を適当に探索。ここまで45分

int H,W;
char a[1050][1050];
int f[1050][1050];
int num[1050][1050];
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={1,0,-1,1,-1,1,0,-1};
vector<P> cur,tmp,next;
int update()
{
	int col = 0;
	for(int i=0;i<cur.size();i++)
	{
		int x = cur[i].fi,y = cur[i].sec;
		if(f[x][y]!=0&&f[x][y]<=num[x][y])
		{
			tmp.pb(P(x,y));
			col++;
		}
	}
	for(int i=0;i<col;i++)
	{
		int x=tmp[i].fi,y=tmp[i].sec;
		f[x][y]=0;
		for(int j=0;j<8;j++)
		{
			int nx=x+dx[j],ny=y+dy[j];
			num[nx][ny]++;
		}
	}
	for(int i=0;i<tmp.size();i++)
	{
		int x = tmp[i].fi,y = tmp[i].sec;
		for(int j=0;j<8;j++)
		{
			int nx = x+dx[j],ny=y+dy[j];
			if(nx<0||nx>=H||ny<0||ny>=W)continue;
			if(f[nx][ny]!=0)next.pb(P(nx,ny));
		}
	}
	sort(next.begin(),next.end());
	next.erase(unique(next.begin(),next.end()),next.end());
	tmp.clear();
	cur.clear();
	cur=next;
	next.clear();
	return col;
}
int main()
{
	cin >> H >> W;
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			cin >> a[i][j];
			if(a[i][j]!='.')f[i][j]=a[i][j]-'0';
		}
	}
	for(int i=1;i<H-1;i++)
	{
		for(int j=1;j<W-1;j++)
		{
			cur.pb(P(i,j));
			int cnt = 0;
			for(int k=0;k<8;k++)
			{
				int nx=i+dx[k],ny=j+dy[k];
				if(f[nx][ny]==0)cnt++;
			}
			num[i][j]=cnt;
		}
	}
	int ans = 0;
	while(1)
	{
		int n = update();
		if(n==0)break;
		ans++;
	}
	cout << ans << endl;
	return 0;
}
6.財宝 (Treasures)

これもやるだけ。半分全列挙+座標圧縮+SegmentTree

typedef long long ll;
typedef pair<ll,ll> P;
const int SIZE = 1<<24;
int N;
ll D,end,ind;
ll X[40],Y[40];
int l[SIZE],r[SIZE];
vector<P> v[2];
void rec(int x,ll s,ll k)
{
	if(x==end)
	{
		v[ind].pb(P(s,k));
		return;
	}
	rec(x+1,s+X[x],k-Y[x]);
	rec(x+1,s-X[x],k+Y[x]);
	rec(x+1,s,k);
}
struct segtree
{
	ll seg[SIZE*2];
	segtree()
	{
		for(int i=0;i<SIZE*2;i++)seg[i]=-LLINF;
	}
	void update(int k,ll x)
	{
		k += SIZE-1;
		seg[k]=x;
		while(k>0)
		{
			k = (k-1)/2;
			seg[k]=max(seg[k*2+1],seg[k*2+2]);
		}
	}
	ll query(int a,int b,int k,int l,int r)
	{
		if(r<=a||b<=l)return -LLINF;
		else if(a<=l&&r<=b)return seg[k];
		else return max(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
	}
}seg;
int main()
{
	cin >> N >> D;
	for(int i=0;i<N;i++)cin >> X[i] >> Y[i];
	ll ans = 0ll;
	int half = N/2;
	int rem = N - half;
	ind = 0,end = half;
	rec(0,0ll,0ll);
	ind = 1,end = N;
	rec(half,0ll,0ll);
	sort(v[1].begin(),v[1].end());
	for(int i=0;i<v[0].size();i++)
	{
		l[i] = lower_bound(v[1].begin(),v[1].end(),P(-D-v[0][i].fi,-LLINF))-v[1].begin();
		r[i] = upper_bound(v[1].begin(),v[1].end(),P(D-v[0][i].fi,LLINF))-v[1].begin();
	}
	for(int i=0;i<v[1].size();i++)seg.update(i,v[1][i].sec);
	for(int i=0;i<v[0].size();i++)ans = max(ans,v[0][i].sec + seg.query(l[i],r[i],0,0,SIZE));
	cout << ans << endl;
	return 0;
}
総括

全て自分の精進不足が招いた結果だと思うので本選まで問題を解きまくっていこうと思う