JOI 2013-2014 予選

JOI

12/15に初めてJOIの予選に参加しました。結果は520/600、2位、Aランクで予選通過でした。
嬉しい!!✌(’ω’✌ )三✌(’ω’)✌三( ✌’ω’)✌
今年の2月頃から頑張ってきた甲斐がありました…
本選のためにもこれからもジャンジャン解いて行きたいと思います。
問題ページはこちら。http://www.ioi-jp.org/joi/2013/2014-yo/index.html

問題1 平均点 (Average Score)

40点以下の者の点を40点にして、平均点を出せば良いです。
ooooo 100pts

ソースコード

#include <iostream>
using namespace std;
int main()
{
	int a,b,c,d,e;
	cin >> a;if(a<40)a=40;
	cin >> b;if(b<40)b=40;
	cin >> c;if(c<40)c=40;
	cin >> d;if(d<40)d=40;
	cin >> e;if(e<40)e=40;
	int sum=a+b+c+d+e;
	cout << sum/5 << endl;
	return 0;
}

問題2 投票 (Vote)

費用が審査基準以下で最も面白いものを探してシミュレート。
ooooo 100pts

ソースコード

#include <cstring>
#include <iostream>
using namespace std;
int a[1050],b[1050],p[1050];
int main()
{
	int n,m;
	cin >> n >> m;
	memset(p,0,sizeof(p));
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin >> b[i];
	}
	for(int i=1;i<=m;i++)
	{
		int c;
		for(int j=1;j<=n;j++)
		{
			if(a[j]>b[i])continue;
			c=j;
			break;
		}
		p[c]++;
	}
	int ans;
	int mx=-1;
	for(int i=1;i<=n;i++)
	{
		if(mx<p[i])
		{
			mx=p[i];
			ans=i;
		}
	}
	cout << ans << endl;
	return 0;
}

問題3 超都観光 (Super Metropolis)

2つの交差点(x1,y1),(y1,y2)間を最小本数の道を通って行く方法は
Ⅰ)2点の位置関係が右上or左下、すなわち(x1<=x2かつy1<=y2)または(x1>=x2かつy1>=y2)の時、max(|x1-x2|,|y1-y2|)
Ⅱ)それ以外の時、|x1-x2|+|y1+y2|
となります(簡単に証明できます)
なので、あとは与えられたN-1個の区間についてそれぞれ独立に考えて、足しあわせれば答えが得られます。
ooooo 100pts

ソースコード

#include <algorithm>
#include <iostream>
using namespace std;
int x[10500],y[10500];
int main()
{
	int w,h,n;
	cin >> w >> h >> n;
	for(int i=0;i<n;i++)
	{
		cin >> x[i] >> y[i];
	}
	int ans=0;
	for(int i=1;i<n;i++)
	{
		int dx=abs(x[i]-x[i-1]),dy=abs(y[i]-y[i-1]);
		if((x[i]>=x[i-1]&&y[i]>=y[i-1])||(x[i]<=x[i-1]&&y[i]<=y[i-1]))
		{
			ans+=max(dx,dy);
		}
		else
		{
			ans+=(dx+dy);
		}
	}
	cout << ans << endl;
	return 0;
}

問題4 部活のスケジュール表 (Schedule)

予選の4番はやはり今年もDPでした。
dp[i][j]:=i日目にjの人(jはbitに集合をエンコードしたもの)が活動する、条件を満たすスケジュール表の総数というテーブルで考えました。
dp[i][j]=Σdp[i-1][k(少なくとも一人jと重なっているもの)]、初期条件はdp[1][J君を含むもの]=1,その他0です。
ooooo 100pts

ソースコード

#include <cstring>
#include <string>
#include <iostream>
using namespace std;
#define MOD 10007
int dp[1050][10];
int m[1050];
int main()
{
	int n;
	cin >> n;
	memset(dp,0,sizeof(dp));
	string s;
	cin >> s;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='J')m[i+1]=0;
		else if(s[i]=='O')m[i+1]=1;
		else m[i+1]=2;
	}
	for(int i=0;i<8;i++)
	{
		if(((i>>m[1])&1)&&(i&1))dp[1][i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<8;j++)
		{
			if(!((j>>m[i])&1))continue;
			for(int k=0;k<8;k++)
			{
				if(j&k)
				{
					dp[i][j]+=dp[i-1][k];
					dp[i][j]%=MOD;
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<8;i++)
	{
		ans+=dp[n][i];
		ans%=MOD;
	}
	cout << ans << endl;
	return 0;
}

問題5 タクシー (Taxis)

まず、BFS(幅優先探索)で、各町同士の最短距離(通る道の最小本数)を計算します。この時dijkstraでも良いのですが、すべての道のコストが全て等しい時(今回の場合1)、priority_queueはqueueと同じ振る舞いをします(このことは蟻本に載っています)。なので、queueをつかってBFSしたほうが計算量が少なくて済みます(予選形式なのであまり関係ないかもしれませんが…)
次に、各町iからタクシーにのって、行ける町(最短距離がR[i]以下)すべてにコストC[i]の辺を張った新しいグラフを作成します。
最後に町1からdijkstraして、新しいグラフにおける町Nまでの最短距離を求めると、それが答えとなります。
ooooo 100pts

ソースコード

#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <iostream>
using namespace std;
typedef pair<int,int> P;
#define pb push_back
#define INF 1000000000
#define fi first
#define sec second
struct edge{int to,cost;};
vector<edge> g[5050],newg[5050];
int c[5050],p[5050],d[5050],dist[5050];
int n,k;
void bfs(int s)
{
	queue<P> q;
	fill(d,d+n,INF);
	d[s]=0;
	q.push(P(0,s));
	while(!q.empty())
	{
		P a=q.front();q.pop();
		int v=a.sec;
		if(d[v]<a.fi)continue;
		for(int i=0;i<g[v].size();i++)
		{
			edge e=g[v][i];
			if(d[e.to]>d[v]+e.cost)
			{
				d[e.to]=d[v]+e.cost;
				q.push(P(d[e.to],e.to));
			}
		}
	}
	return;
}
int dijkstra()
{
	priority_queue<P,vector<P>,greater<P> > q;
	fill(dist,dist+n,INF);
	dist[0]=0;
	q.push(P(0,0));
	while(!q.empty())
	{
		P a=q.top();q.pop();
		int v=a.sec;
		if(dist[v]<a.fi)continue;
		for(int i=0;i<newg[v].size();i++)
		{
			edge e=newg[v][i];
			if(dist[e.to]>dist[v]+e.cost)
			{
				dist[e.to]=dist[v]+e.cost;
				q.push(P(dist[e.to],e.to));
			}
		}
	}
	return dist[n-1];
}
int main()
{
	cin >> n >> k;
	for(int i=0;i<n;i++)cin >> c[i] >> p[i];
	for(int i=0;i<k;i++)
	{
		int a,b;
		cin >> a >> b;
		a--;b--;
		edge in;
		in.to=b;
		in.cost=1;
		g[a].pb(in);
		in.to=a;
		g[b].pb(in);
	}
	for(int i=0;i<n;i++)
	{
		bfs(i);
		for(int j=0;j<n;j++)
		{
			if(i==j)continue;
			if(d[j]<=p[i])
			{
				edge ne;
				ne.to=j;ne.cost=c[i];
				newg[i].pb(ne);
			}
		}
	}
	cout << dijkstra() << endl;
	return 0;
}

問題6 小籠包 (Xiao Long Bao)

5番を解き終わって残り30分、1≦D[i]≦7と小さいのでなんかできないかな…と思いましたがすぐに思いつかなかったのでテストケースを見てみると、ケース1だけN=10と小さかったのでシミュレートしました。
満点解法は、やはりDが小さいことに注目して、前7個の食べる順番を持つDPだそうです。
完全に部分点狙いのソースですが一応上げておきます…
o---- 20pts

ソースコード

#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define pb push_back
int d[150],a[150];
int n;
int simulate(vector<int> vec)
{
	bool used[150];
	memset(used,false,sizeof(used));
	int res=0;
	int s[150];
	for(int i=0;i<150;i++)s[i]=0;
	for(int i=0;i<vec.size();i++)
	{
		res+=s[vec[i]];
		used[vec[i]]=true;
		for(int j=max(0,vec[i]-d[vec[i]]);j<=min(n-1,vec[i]+d[vec[i]]);j++)
		{
			if(used[j])continue;
			else
			{
				s[j]+=a[vec[i]];
			}
		}
	}
	return res;
}
int main()
{
	cin >> n;
	for(int i=0;i<n;i++)cin >> d[i];
	for(int i=0;i<n;i++)cin >> a[i];
	vector<int> v;
	for(int i=0;i<n;i++)v.pb(i);
	int ans=0;
	do
	{
		ans=max(ans,simulate(v));
	}while(next_permutation(v.begin(),v.end()));
	cout << ans << endl;
	return 0;
}

総括

模擬予選で危ない点数をとったのでとても心配でしたが無事通過できて本当に嬉しいです。
自分より下の学年の人が1位というのは正直悔しいですが、精進して万全の体制で本選を迎えたいと思います。