HIR180's diary

ICPC World Finals 2022 を集大成に

2014-01-04

■ JOI contest 18:39

2つ決定勢は無視でき、0個決定勢は貪欲に決定でき、またチームCの得点も確定できるため

1つ決定勢のみ考慮する。これは「いくつCを超えるか」を決めうちすれば貪欲でできる。

vectorのiteratorの使い方さえわかれば簡単です(白目)

//Daily Lunch Special Tanoshii !!
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i
int v[3005]={};
int m[3005]={};
vector<int>vec;
vector<int>one;
vector<int>cpy;
int main()
{
	int n,k;
	scanf("%d %d",&n,&k);
	for(int i=0;i<2*n;i++)
	{
		int x,y; scanf("%d %d",&x,&y);
		if(!y) vec.pb(x);
		else { v[y]+=x; m[y]++;}
	}
	sort(vec.begin(),vec.end());
	while(m[k]!=2){ m[k]++; v[k]+=vec[vec.size()-1]; vec.pop_back();}
	int add=0;
	for(int i=1;i<=n;i++)
	{
		if(m[i]==1) one.pb(v[i]);
		if(m[i]==2 && v[i]>v[k]) add++;
	}
	sort(one.begin(),one.end());
	for(int i=0;i<6005;i++) cpy.pb(i);
	int ret=INF;
//cout << vec.size() << " " << one.size() << endl;
	for(int i=0;i<=one.size();i++)
	{
		bool u[6005]={};
		int res=i;
		for(int j=0;j1-j]=true;
		}
		vector<int>val(0);
		vector<int>num=cpy;
		while(!num.empty() && num[num.size()-1]>vec.size()-1-i) num.pop_back();
		cpy=num;
		for(int j=0;jint f=upper_bound(vec.begin(),vec.end(),v[k]-one[j])-vec.begin();
			int d=lower_bound(num.begin(),num.end(),f)-num.begin();
			vector<int>::iterator it=lower_bound(num.begin(),num.end(),f);
			d--;
			if(d==-1) goto fail;
			it--;
			u[num[d]]=true;
			num.erase(it);
		}
		for(int j=0;jif(u[j]) continue;
			u[j]=true;
			vector<int>::iterator it=lower_bound(num.begin(),num.end(),j);
			num.erase(it);
			int f=upper_bound(vec.begin(),vec.end(),v[k]-vec[j])-vec.begin();
			int d=lower_bound(num.begin(),num.end(),f)-num.begin();
			it=lower_bound(num.begin(),num.end(),f);
			d--;
			if(d==-1)
			{
				u[num[num.size()-1]]=true;
				num.pop_back();
				res++;
			}
			else {it--;u[num[d]]=true;num.erase(it);}
		}
		ret=min(ret,res);
		fail:;
	}
	ret+=1+add;
	cout << ret << endl;
}

■ JOIの幾何 15:16

Belt,Nightman,Ruinsです。

体感難易度はNightman< Ruins <

Belt

atan2して角度とイベントを対応づける。次にソートして順に見ていく。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<double,double> P;
typedef pair<double,int> PP;
//perditus†paradisusは関係ないだろ！！いい加減にしろ！！
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i
#define cyc 3.14159265
P za[1005];
 
int main()
{
	int n; double d;
	scanf("%d %lf",&n,&d);
	d*=2.0;
	for(int i=0;i"%lf %lf",&za[i].first,&za[i].second);
	}
	int ret=1;
	for(int i=0;iint difx[1005],dify[1005];
		for(int j=0;j10005];
		int idx=0;
		for(int j=0;jif(i==j) continue;
			
			query[idx++]=mp(atan2(dify[j],difx[j]),0);
			query[idx++]=mp(atan2(dify[j],difx[j])+cyc,1);
			query[idx++]=mp(atan2(dify[j],difx[j])+cyc*2,0);
			query[idx++]=mp(atan2(dify[j],difx[j])+cyc*3,1);
			
			if(d*d1);
				query[idx++]=mp(atan2(dify[j],difx[j])+cyc-asin(d/sqrt(difx[j]*difx[j]+dify[j]*dify[j])),0);
				query[idx++]=mp(atan2(dify[j],difx[j])+cyc*2+asin(d/sqrt(difx[j]*difx[j]+dify[j]*dify[j])),1);
				query[idx++]=mp(atan2(dify[j],difx[j])+cyc*3-asin(d/sqrt(difx[j]*difx[j]+dify[j]*dify[j])),0);
			}
		}
		sort(query,query+idx);
		int cur=1;
		for(int i=0;iif(!query[i].second) cur++;
			else cur--;
			ret=max(ret,cur);
		}
	}
	printf("%d\n",ret);
}

Nightman

WFフェーズは自明で、平面走査もやるだけ...

まあ難しいけど...

あとepsの重要さを再確認した問題になりました(epsを0->1e-7にしただけで75->100になった)

//Daily Lunch Special Tanoshii !!
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i
double d[225][225];
int za[1005][1005]={};
bool fill[1005][1005]={};
int perx[15],pery[15];
int unkx[15],unky[15];
int s[55],t[55],u[55],v[55];
int idx=0;
int main()
{
	int a,b,c,w,h;
	scanf("%d %d %d",&a,&b,&c);
	scanf("%d %d",&w,&h);
	for(int i=0;iint s,t; scanf("%d %d",&s,&t);
		perx[i]=s; pery[i]=t;
		if(!za[s][t]) za[s][t]=(++idx);
	}
	for(int i=0;i"%d %d %d %d",&s[i],&t[i],&u[i],&v[i]);
		if(!za[s[i]][t[i]]) za[s[i]][t[i]]=(++idx);
		if(!za[s[i]][v[i]]) za[s[i]][v[i]]=(++idx);
		if(!za[u[i]][t[i]]) za[u[i]][t[i]]=(++idx);
		if(!za[u[i]][v[i]]) za[u[i]][v[i]]=(++idx);
	}
	for(int i=0;iint s,t; scanf("%d %d",&s,&t);
		unkx[i]=s; unky[i]=t;
		if(!za[s][t]) za[s][t]=(++idx);
	}
	vector
z(idx+1);
	for(int i=0;i<1005;i++)
	{
		for(int j=0;j<1005;j++)
		{
			if(za[i][j])
			{
				z[za[i][j]]=mp(i,j);
			}
		}
	}
	for(int i=0;i<225;i++)for(int j=0;j<225;j++)d[i][j]=1e8;
	d[0][0]=0;
	for(int i=1;i<=idx;i++)
	{
		for(int j=1;j<=idx;j++)
		{
			if(i==j){ d[i][j]=0; continue;}
			int x1=z[i].first;
			int y1=z[i].second;
			int x2=z[j].first;
			int y2=z[j].second;
			
			if(y1>y2)
			{
				swap(x1,x2); swap(y1,y2);
			}
			for(int k=0;kif(x1==x2)
				{
					if(!(s[k]continue;
					if(y2<=t[k] || v[k]<=y1) continue;
					goto fail;
				}
				else if(y1==y2)
				{
					if(x1>x2){swap(x1,x2); swap(y1,y2);}
					if(!(t[k]continue;
					if(x2<=s[k] || u[k]<=x1) continue;
					goto fail;
				}
				else
				{
					int up=max(t[k],y1);
					int down=min(v[k],y2);
					if(up>=down) continue;
					double v1=((double)(x2-x1)/(double)(y2-y1))*(double)up
					+(double)(x1*y2-x2*y1)/(double)(y2-y1);
					
					double v2=((double)(x2-x1)/(double)(y2-y1))*(double)down
					+(double)(x1*y2-x2*y1)/(double)(y2-y1);
					
					if(v1>v2) swap(v1,v2);
					double lb=max((double)s[k],v1);
					double ub=min((double)u[k],v2);
					if(lbeps) goto fail;
					else continue;
				}
			}
			d[i][j]=(double)sqrt((double)(x2-x1)*(double)(x2-x1)+(double)(y2-y1)*(double)(y2-y1));
			continue;
			fail:;
			d[i][j]=1e8;//cout << z[i].first << " " << z[i].second << " " << z[j].first << " " << z[j].second << " " << d[i][j] << endl;
		}
	}
	for(int k=1;k<=idx;k++){
		for(int i=1;i<=idx;i++){
			for(int j=1;j<=idx;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	double ret=0;
	for(int j=0;jdouble res=INF;
		for(int i=0;iint x=za[perx[i]][pery[i]];
			int y=za[unkx[j]][unky[j]];
			res=min(res,d[x][y]*2);
		}
		ret+=res;
	}
	printf("%.3f\n",ret);
}

Ruins

はじめは使う辺を決めうちして、そこから適当にDPするとしていてO(N^5)でデデドン(絶望)

としていましたが使う辺じゃなくて左端の点を決めうちするだけでよいと分かり、O(N^4)になる。

N<=128だけど定数倍軽い(?)ので余裕で通る。

//Daily Lunch Special Tanoshii !!
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<double,double> P;
typedef pair<double,int> PP;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i
#define PI 3.14159265
P za[130];
int main()
{
	int n; scanf("%d",&n);
	for(int i=0;i"%lf %lf",&za[i].first,&za[i].second);
	}
	sort(za,za+n);
	int ret=3;
	for(int i=0;ivec(0);
		for(int j=i+1;jdouble dx=za[j].first-za[i].first;
			double dy=za[j].second-za[i].second;
			double ang=atan2(dy,dx);
			vec.pb(mp(ang,j));
		}
		sort(vec.begin(),vec.end());
		int dp[130][130]={};
		int vs=vec.size();
		for(int j=0;j2;
		}
		vec.pb(mp(0,i));
		for(int j=1;jfor(int k=0;kfor(int l=-1;lint trl;
					//昨日true blue初見落ちして青パレ復帰ってそれ一番言われてるから
					if(l==-1)
					{
						trl=vs;
					}
					else
					{
						trl=l;
					}
					int a=vec[trl].second;
					int b=vec[k].second;
					int c=vec[j].second;
					if(za[a].first==za[b].first)
					{
						if(za[a].first>za[c].first)
						{
							dp[j][k]=max(dp[j][k],dp[k][trl]+1); ret=max(ret,dp[j][k]);
						}
					}
					else
					{
						double x1=(double)za[a].first;
						double y1=(double)za[a].second;
						double x2=(double)za[b].first;
						double y2=(double)za[b].second;
						double v=(y2-y1)/(x2-x1)*(double)za[c].first+
							(x2*y1-x1*y2)/(x2-x1);
						if(!((za[a].first1); ret=max(ret,dp[j][k]);
						}
					}
				}
			}
		}
	}
	printf("%d\n",ret);
}