2010年度ICPC模擬国内予選

ICPC

圧倒的敗北感……


というか何だろう。モチベーション下がりまくり。
チームメイトさんは授業以外で3週間全く問題解かないどころかチームwikiすら見ないし。
大体、学習ブログ最後に更新したの4月じゃねえかよ。


何か言ってくれないと僕もどうしたらいいのか判らないんだけど。
お互いに不幸になるためにチーム組んだんじゃないんだけどな。


と、まあどうせここなんか誰も見てないだろうし書く。


さてさて今日の復習。問題解きなおして行こう。


TCOで睡眠不足なんで3問解けるだろうか。。。
↓以下更新予定。

問題文などはめんどいので今日のところは省略。
戦略とか考え出すとイライラする。起きていてもいいことないのでコードだけ貼ってもう寝よう。


あー立ち直れるかなあ。

てんぷれ

#include<iostream>
#include<algorithm>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)

A

int sum(int b,int len)
{
	int ret=0;
	rep(i,len)ret+=b+i;
	return ret;
}

int main(){
	int n;
	while(cin>>n,n)
	{
		int ans=0;
		for(int len=2;len<=n;len++)
		for(int b=1;b<=n;b++)
		{
			int s=sum(b,len);
			if(s==n)ans++;
			if(s>n)break;
		}
		cout<<ans<<endl;
	}
	return 0;
}

B

struct S{
	string name;
	double ratio;
	bool operator<(const S &r)const{
		if(ratio==r.ratio)return name<r.name;
		return ratio>r.ratio;
	}
};

int main(){
	int n;
	while(cin>>n,n)
	{
		S crop[50];
		rep(i,n)
		{
			int p,a,b,c,d,e,f,s,m,gain=0,time=0;
			cin>>crop[i].name>>p>>a>>b>>c>>d>>e>>f>>s>>m;
			gain=s*m*f-p;
			time=(a+b+c)+(d+e)*m;
			crop[i].ratio=double(gain)/time;
		}
		sort(crop,crop+n);
		rep(i,n)cout<<crop[i].name<<endl;
		cout<<"#"<<endl;
	}
	return 0;
}

C

#define SQ(n) ((n)*(n))
const int inf=1<<28;

int n,m,code[16],in[20000];
int dp[20001][256];

int func(int n)
{
	if(n<0)return 0;
	return min(255,n);
}

int main(){
	while(cin>>n>>m,n)
	{
		rep(i,m)cin>>code[i];
		rep(i,n)cin>>in[i];
		
		rep(i,n+1)rep(j,256)dp[i][j]=inf;
		dp[0][128]=0;
		
		for(int i=1;i<=n;i++)
		rep(j,256)rep(k,m)dp[i][func(j+code[k])]=min(
			dp[i][func(j+code[k])],dp[i-1][j]+
			SQ(func(j+code[k])-in[i-1])
		);
		
		cout<<*min_element(dp[n],dp[n]+256)<<endl;
	}
	return 0;
}

D

int n,m,r,z[1000];
int DL[200][200],DS[200][200];

int dp[1000][200];

int main(){
	while(cin>>n>>m,n)
	{
		rep(i,n)rep(j,n)DL[i][j]=DS[i][j]=inf;
		
		rep(i,m)
		{
			int x,y,t; char c;
			cin>>x>>y>>t>>c; x--,y--;
			if(c=='L')DL[x][y]=DL[y][x]=min(DL[x][y],t);
			if(c=='S')DS[x][y]=DS[y][x]=min(DS[x][y],t);
		}
		rep(i,n)DL[i][i]=DS[i][i]=0;
		
		cin>>r;
		rep(i,r)cin>>z[i],z[i]--;
		rep(i,r)rep(j,n)dp[i][j]=inf;
		
		rep(k,n)rep(i,n)rep(j,n)
		{
			DL[i][j]=min(DL[i][j],DL[i][k]+DL[k][j]);
			DS[i][j]=min(DS[i][j],DS[i][k]+DS[k][j]);
		}
		
		dp[0][z[0]]=0;
		priority_queue<pair<int,pi> > Q; Q.push(mp(0,mp(0,z[0])));
		while(!Q.empty())
		{
			int cc=Q.top().first;
			int cur=Q.top().second.first,ship=Q.top().second.second; Q.pop();
			
			if(dp[cur][ship]>-cc)continue;
			if(cur==r-1)
			{
				cout<<-cc<<endl; break;
			}
			
			//land
			int nc=cc-DL[z[cur]][z[cur+1]];
			if(DL[z[cur]][z[cur+1]]!=inf&&dp[cur+1][ship]>-nc)
				dp[cur+1][ship]=-nc,Q.push(mp(nc,mp(cur+1,ship)));
			
			//sea
			rep(i,n)if(DL[z[cur]][ship]!=inf&&DS[ship][i]!=inf&&DL[i][z[cur+1]]!=inf)
			{
				nc=cc-DL[z[cur]][ship]-DS[ship][i]-DL[i][z[cur+1]];
				if(dp[cur+1][i]>-nc)
					dp[cur+1][i]=-nc,Q.push(mp(nc,mp(cur+1,i)));
			}
		}
	}
	return 0;
}