HIR180's diary

ICPC World Finals 2022 を集大成に

2014-08-31

■ 2012天プロ本選解いた 22:43

A:

Greedyだなあ...と書くと通る

int main()
{
	vectorvec;
	vec.pb(1); vec.pb(1);
	while(vec[vec.size()-2] + vec[vec.size()-1] <= 1e10)
	{
		vec.pb(vec[vec.size()-2] + vec[vec.size()-1]);
	}
	ll n;
	cin >> n;
	int res = 0;
	while(n > 0)
	{
		int a = upper_bound(vec.begin(),vec.end(),n)-vec.begin();
		n -= vec[a-1];
		res++;
	}
	cout << res << endl;
}

B:

O(N^2)を死ぬ気で改善しただけ。たぶん落とされるべき解法

int n;
int x[10005],y[10005];
P gcd[100][100];
ll tw[10005];
ll th[10005];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&x[i],&y[i]);
	}
	for(int i=1;i<100;i++) for(int j=1;j<100;j++)
	{
		int a = i,b = j;
		gcd[i][j] = mp(a/__gcd(i,j),b/__gcd(i,j));
	}
	for(int i=2;i<=10000;i++)
	{
		tw[i] = 1LL*(i)*(i-1LL)/2LL;
	}
	for(int i=2;i<=10000;i++)
	{
		th[i] = 1LL*(i)*(i-1LL)*(i-2LL)/6LL;
		th[i] %= mod;
	}
	ll t = 0,f = 0;
	
	for(int i=1;i<=n;i++)
	{
		int cnt[100][100][4] = {};
		for(int j=1;j<=n;j++)
		{
			if(i == j) continue;
			int a = x[j]-x[i];
			int b = y[j]-y[i];
			int c = 0;
			if(a < 0)
			{
				c += 2;
				a = -a;
			}
			if(b < 0)
			{
				c += 1;
				b = -b;
			}
			if(a == 0)
			{
				b = 1;
			}
			if(b == 0)
			{
				a = 1;
			}
			if(a && b)
			{
				int cc = a;
				a = gcd[a][b].fi;
				b = gcd[cc][b].sc;
			}
			cnt[a][b][c]++;
			t += cnt[a][b][c]-1;
			f += tw[cnt[a][b][c]-1];
		}
	}
	if(t % 2 == 1) t = ((t+mod)/2)%mod;
	else t = (t/2)%mod;
	if(f % 2 == 1) f = ((f+mod)/2)%mod;
	else f = (f/2)%mod;
	ll res = 1LL*n*(n-1)*(n-2)*(n-3)/24LL - t*(n-3LL) + 3*f;
	res %= mod;
	res = (res+mod)%mod;
	cout << res << endl;
}

C:

気づけばやるだけなんだけど実装が鬼

int dp[105][105][31][155];
int n;
int a[35],b[35],c[35];

int main()
{
	cin >> n;
	for(int i=0;i> a[i] >> b[i] >> c[i];
	}
	for(int i=0;i<105;i++)
	{
		for(int j=0;j<105;j++)
		{
			for(int k=0;k<31;k++)
			{
				for(int l=0;l<155;l++)
				{
					dp[i][j][k][l] = INF;
				}
			}
		}
	}
	dp[100][a[0]][0][0] = 0;
	queueque;
	que.push(mp(mp(100,a[0]),mp(0,0)));
	while(!que.empty())
	{
		P2 p = que.front(); que.pop();
		if(p.fi.sc == 0)
		{
			if(p.sc.fi == n-1) continue;
			if(dp[p.fi.fi][a[p.sc.fi+1]][p.sc.fi+1][p.sc.sc] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc])
			{
				dp[p.fi.fi][a[p.sc.fi+1]][p.sc.fi+1][p.sc.sc] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc];
				que.push(mp(mp(p.fi.fi,a[p.sc.fi+1]),mp(p.sc.fi+1,p.sc.sc)));
			}
			continue;
		}
		if(p.fi.fi-b[p.sc.fi] > 0)
		{
			if(p.fi.sc-(p.sc.sc+1) <= 0)
			{
				if(dp[p.fi.fi-b[p.sc.fi]][0][p.sc.fi][p.sc.sc+1] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1)
				{
					dp[p.fi.fi-b[p.sc.fi]][0][p.sc.fi][p.sc.sc+1] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1;
					que.push(mp(mp(p.fi.fi-b[p.sc.fi],0),mp(p.sc.fi,p.sc.sc+1)));
				}
			}
			else
			{
				if(dp[p.fi.fi-b[p.sc.fi]][min(a[p.sc.fi],p.fi.sc-(p.sc.sc+1)+c[p.sc.fi])][p.sc.fi][p.sc.sc+1] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1)
				{
					dp[p.fi.fi-b[p.sc.fi]][min(a[p.sc.fi],p.fi.sc-(p.sc.sc+1)+c[p.sc.fi])][p.sc.fi][p.sc.sc+1] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1;
					que.push(mp(mp(p.fi.fi-b[p.sc.fi],min(a[p.sc.fi],p.fi.sc-(p.sc.sc+1)+c[p.sc.fi])),mp(p.sc.fi,p.sc.sc+1)));
				}
			}
			if(p.fi.sc-5 <= 0)
			{
				if(dp[p.fi.fi-b[p.sc.fi]][0][p.sc.fi][0] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1)
				{
					dp[p.fi.fi-b[p.sc.fi]][0][p.sc.fi][0] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1;
					que.push(mp(mp(p.fi.fi-b[p.sc.fi],0),mp(p.sc.fi,0)));
				}
			}
			else
			{
				if(dp[p.fi.fi-b[p.sc.fi]][min(a[p.sc.fi],p.fi.sc-5+c[p.sc.fi])][p.sc.fi][0] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1)
				{
					dp[p.fi.fi-b[p.sc.fi]][min(a[p.sc.fi],p.fi.sc-5+c[p.sc.fi])][p.sc.fi][0] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1;
					que.push(mp(mp(p.fi.fi-b[p.sc.fi],min(a[p.sc.fi],p.fi.sc-5+c[p.sc.fi])),mp(p.sc.fi,0)));
				}
			}
			if(dp[min(100,p.fi.fi-b[p.sc.fi]+50)][min(a[p.sc.fi],p.fi.sc+c[p.sc.fi])][p.sc.fi][0] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1)
			{
				dp[min(100,p.fi.fi-b[p.sc.fi]+50)][min(a[p.sc.fi],p.fi.sc+c[p.sc.fi])][p.sc.fi][0] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1;
				que.push(mp(mp(min(100,p.fi.fi-b[p.sc.fi]+50),min(a[p.sc.fi],p.fi.sc+c[p.sc.fi])),mp(p.sc.fi,0)));
			}
		}
	}
	int res = INF;
	for(int i=1;i<=100;i++) for(int j=0;j<=150;j++) res = min(res,dp[i][0][n-1][j]);
	if(res == INF) res = -1;
	cout << res << endl;
}

D:

すごく面白かった(KONAMI)

20点は9C3*6C3*3C3なので全探索。

その後は少し厄介だが、

x座標でソートして

小さいほうから2/3をy座標でソートしなおす。

そのあとx座標が小さいほうの2/3のy座標が小さいほうと大きいほう、x座標の大きいほう1/3から大きいほうを結ぶ三角形をとる

をするだけでなんとN=18を除く60点がとれる。

N=18は9/9に分けてそれぞれで全探索してやるのを1.8secしたら18点もらえた。

int n;
double x[3005],y[3005];
vector<int>res;
vector<int>hoge;
double area(int a,int b,int c)
{
	double ab = sqrt( (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]) );
	double ac = sqrt( (x[a]-x[c])*(x[a]-x[c]) + (y[a]-y[c])*(y[a]-y[c]) );
	double bc = sqrt( (x[b]-x[c])*(x[b]-x[c]) + (y[b]-y[c])*(y[b]-y[c]) );
	return sqrt( (ab+ac+bc)/2 * (-ab+ac+bc)/2 * (ab-ac+bc)/2 * (ab+ac-bc)/2 );
}
bool cmp(int a,int b)
{
	return (x[a] < x[b]);
}
bool cmp2(int a,int b)
{
	return (y[a] < y[b]);
}
bool cmp3(int a,int b)
{
	return (x[a] > x[b]);
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i"%lf %lf",&x[i],&y[i]);
	}
	if(n == 9)
	{
		vector<int>a;
		for(int i=0;i<9;i++) a.pb(i);
		vector<int>b;
		double best = 0;
		do
		{
			double s = area(a[0],a[1],a[2])+area(a[3],a[4],a[5])+area(a[6],a[7],a[8]);
			if(best < s)
			{
				best = s;
				b = a;
			}
		}while(next_permutation(a.begin(),a.end()));
		for(int i=0;i3) printf("%d %d %d\n",b[i],b[i+1],b[i+2]);
	}
	else if(n == 18)
	{
		vector<int>a,b;
		for(int i=0;i<18;i++) a.pb(i);
		double z = 0.0; double begin = clock();
		do
		{
			random_shuffle(a.begin(),a.end());
			vector<int>c,d,e,f;
			for(int i=0;i<9;i++)
			{
				c.pb(a[i]);
			}
			for(int j=0;j<9;j++)
			{
				d.pb(a[9+j]);
			}
			for(int i=0;i<9;i++)
			{
				e.pb(-1); f.pb(-1);
			}
			int a[21][3];
			double best = 0.0;
			double best2 = 0.0;
			for(int i=0;i<9;i++)
			{
				for(int j=i+1;j<9;j++)
				{
					for(int k=j+1;k<9;k++)
					{
						for(int x=0;x<9;x++)
						{
							if(x == i || x == j || x == k) continue;
							for(int y = x+1;y<9;y++)
							{
								if(y == i || y == j || y == k) continue;
								for(int z = y+1;z<9;z++)
								{
									if(z == i || z == j || z == k) continue;
									bool used[9]={};
									used[i] = used[j] = used[k] = used[x] = used[y] = used[z] = true;
									vector<int>s;
									for(int qq=0;qq<9;qq++)
									{
										if(!used[qq]) s.pb(qq);
									}
									if(area(c[i],c[j],c[k])+area(c[x],c[y],c[z])+area(c[s[0]],c[s[1]],c[s[2]]) > best)
									{
										best = area(c[i],c[j],c[k])+area(c[x],c[y],c[z])+area(c[s[0]],c[s[1]],c[s[2]]);
										e[0] = c[i];
										e[1] = c[j];
										e[2] = c[k];
										e[3] = c[x];
										e[4] = c[y];
										e[5] = c[z];
										e[6] = c[s[0]];
										e[7] = c[s[1]];
										e[8] = c[s[2]];
									}
									if(area(d[i],d[j],d[k])+area(d[x],d[y],d[z])+area(d[s[0]],d[s[1]],d[s[2]]) > best2)
									{
										best2 = area(d[i],d[j],d[k])+area(d[x],d[y],d[z])+area(d[s[0]],d[s[1]],d[s[2]]);
										f[0] = d[i];
										f[1] = d[j];
										f[2] = d[k];
										f[3] = d[x];
										f[4] = d[y];
										f[5] = d[z];
										f[6] = d[s[0]];
										f[7] = d[s[1]];
										f[8] = d[s[2]];
									}
								}
								
							}
						}
					}
				}
			}
			if(z < best+best2)
			{
				z = best+best2;
				b.clear();
				for(int i=0;i<9;i++) b.pb(e[i]);
				for(int i=0;i<9;i++) b.pb(f[i]);
			}
		}while(begin+1.8*CLOCKS_PER_SEC >= clock());
		for(int i=0;i3) printf("%d %d %d\n",b[i],b[i+1],b[i+2]);
	}else
	{
		int a[3005];
		for(int i=0;iint>pre;
		vector<int>bac;
		for(int i=0;i2/3;i++) pre.pb(a[i]);
		for(int i=n*2/3;ifor(int i=0;i3;i++)
		{
			printf("%d %d %d\n",pre[i],pre[n*2/3-1-i],bac[i]);
		}
	}
}

E:

読んでない

100+100+100+98+0 = 398でした。