HIR180's diary

ICPC World Finals 2022 を集大成に

2013-08-11

■ if(SRM401 && SRM429 && SRM445 && TestSRM) puts("I'm so happy."); 01:47

練習会まとめ.

結果はそれぞれ

ox- x-- o--

でした。

SRM401

Easy:

うん。はい。

242.89pts

//E? Nandatte?
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
class 
FIELDDiagrams{
public:
long long countDiagrams(int fieldOrder)
{
	long long dp[31][31]={};
	dp[1][0]=1;
	dp[1][1]=1;
	for(int i=2;i<=30;i++)
	{
		for(int j=0;j<=i;j++)
		{
			for(int k=0;k<=j;k++)
			{
				dp[i][j]+=dp[i-1][k];
			}
		}
	}
	long long val=0;
	for(int i=1;i<=30;i++)
	{
		val+=dp[fieldOrder][i];
	}
	return val;
	
	}
};

Med:

X^X+Y^Y=1になる点のみ考えればいい。

二次関数を解く。

係数が0の時や係数が0の時や係数が0の時に注意しないと(sun)です。

165pts

//E? Nandatte?
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
class ParticleCollision{
public:
vector <double> collision(int vx, int vy, int vz, int x0, int y0, int z0)
{
	vector<double>ret;
	ret.clear();
	double a=1.0*vx*vx+1.0*vy*vy;
	double b=2.0*(1.0*x0*vx+1.0*y0*vy);
	double c=1.0*x0*x0+1.0*y0*y0-1.0;
	if(b*b-4.0*a*c<0.0)
	{
		return ret;
	}
	if(!a && !b)
	{
		if(c==0.0 && vz!=0){
			for(int i=0;i<3;i++) ret.pb(0.0);
		}
		else if(c==0.0) 
		{
			double arc=acos(x0);
			bool ok=false;
			if(sin(arc)!=y0)
			{
				arc=2*3.14159265358979323846-arc;
			}
			double se=arc/3.14159265358979323846;
			if(abs(1.0*z0-se-floor(1.0*z0-se))==0.0 && (int)floor(1.0*z0-se)%2==0) ok=true;
	
			if(!ok) return ret;
			ret.pb(x0);
			ret.pb(y0);
			ret.pb(z0);
		}
	return ret;
	}
	printf("%lf %lf %lf",a,b,c);
	
	
	double t=(-1.0*b+sqrt(b*b-4.0*a*c))/2.0/a;
	cout << t << endl;
	ret.pb(x0+t*vx);
	ret.pb(y0+t*vy);
	double arc=acos(x0+t*vx);
	if(sin(arc)!=y0+t*vy)
	{
		arc=2*3.14159265358979323846-arc;
	}
	cout << arc << endl;
	double se=arc/3.14159265358979323846;
	int hoge=0;
	vector<double>prev;
	if(1.0*z0+t*vz-se-floor(1.0*z0+t*vz-se)==0.0 && (int)floor(1.0*z0+t*vz-se)%2==0) ret.pb(z0+t*vz);
	if(ret.size()==3)
	{
		hoge++;
		prev=ret;
	}
	cout << hoge << "hoge" << endl;
	ret.clear();
	if(sqrt(b*b-4.0*a*c)==0.0)
	{
 		if(prev.size()) return prev;
 		else return ret;
 	}
	t=(-1.0*b-sqrt(b*b-4.0*a*c))/2.0/a;
	cout << t << endl;
	ret.pb(x0+t*vx);
	ret.pb(y0+t*vy);
	arc=acos(x0+t*vx);
	if(sin(arc)!=y0+t*vy)
	{
		arc=2*3.14159265358979323846-arc;
	}
	se=arc/3.14159265358979323846;
	cout << se << endl;
	cout << (1.0*z0+t*vz-se-floor(1.0*z0+t*vz-se)) << endl;
	cout << (int)floor(1.0*z0+t*vz-se)%2 << endl;
	if(abs(1.0*z0+t*vz-se-floor(1.0*z0+t*vz-se))==0.0 && (int)floor(1.0*z0+t*vz-se)%2==0) ret.pb(z0+t*vz);
	
	if(ret.size()==3)
	{
		hoge++;
		prev=ret;
	}
	cout << hoge << endl;
	cout << ret.size() << endl;
	if(hoge==2) 
	{
	ret.clear();
		for(int i=0;i<3;i++) ret.pb(0.0);
		return ret;
	}
	else if(!prev.empty()) return prev;
	
	ret.clear();
	
	return ret;
	}
};

SRM 429

Easy:

テーブルをつくる。計算する。

209.88pts

//E? Nandatte?
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
class SubrectanglesOfTable{
public:
vector<long long> getQuantity(vector  table)
{
	int s=table.size();
	table.resize(2*s);
	for(int i=0;i<2*s;i++)
	{
		if(ielse
		{
			table[i]=table[i-s];
		}
	}
	long long ma[26]={};
	for(int i=0;ifor(int j=0;j0].size();j++)
		{
			long long val=1;
			val*=(i+1);
			val*=(table.size()-i);
			val*=(j+1);
			val*=(table[0].size()-j);
			ma[table[i][j]-'A']+=val;
		}
	}
	vector<long long>ret;
	for(int i=0;i<26;i++)
	{
		ret.pb(ma[i]);
	}
	return ret;
	}
};

Med:

適当につじつま合うまで回したら~~~~~TLE

したので普通のBFSにしたら通った。こわい。

150pts

//E? Nandatte?
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pairint> P1;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
long long gcd(long long a,long long b)
{
	if(aif(a%b==0) return b;
	else return gcd(b,a%b);
}
class IngredientProportions{
public:
vector <int> getMasses(vector  proportions)
{
	int edge[15][15]={};
	queueque;
	P p[12][12];
	int val[12][2];
	for(int i=0;i<10;i++)for(int j=0;j<10;j++) p[i][j].first=p[i][j].second=0;
	vectorvec=proportions;
	for(int i=0;iint a=vec[i][1]-'0';
		int b=vec[i][8]-'0';
		int c=vec[i][13]-'0';
		int d=vec[i][15]-'0';
		int f=gcd(c,d);
		c/=f; d/=f;
		edge[a][b]=true;
		edge[b][a]=true;
		p[a][b]=mp(c,d);
		p[b][a]=mp(d,c);
		if(!i)
		{
			val[a][0]=c;
			val[b][0]=d;
			val[a][1]=val[b][1]=1;
			que.push(mp(mp(val[a][0],val[a][1]),a));
			que.push(mp(mp(val[b][0],val[b][1]),b));
		}
	}
	bool used[12]={};
	while(!que.empty())
	{
		
		P1 p1=que.front(); que.pop();
		if(used[p1.second]) continue;
		used[p1.second]=true;
		for(int i=0;i<10;i++)
		{
			if(edge[p1.second][i])
			{
				if(used[i]) continue;
				long long s=gcd(val[p1.second][0]*p[p1.second][i].second,val[p1.second][1]*p[p1.second][i].first);
				val[i][0]=val[p1.second][0]*p[p1.second][i].second/s;
				val[i][1]=val[p1.second][1]*p[p1.second][i].first/s;
				que.push(mp(mp(val[i][0],val[i][1]),i));
			}
		}
	}
	vector<int>ret;
	long long cur=1LL;
	for(int i=0;i<=vec.size();i++)
	{
	
		cur=cur*val[i][1]/gcd(cur,val[i][1]);
	}
	for(int i=0;i<=vec.size();i++)
	{
		long long d=cur/val[i][1];
		val[i][0]*=d;
	}
	long long v=gcd(val[0][0],val[1][0]);
	for(int i=2;i<=vec.size();i++)
	{	
		v=gcd(v,val[i][0]);
	}
	for(int i=0;i<=vec.size();i++) ret.pb(val[i][0]/v);
	return ret;
	}
};

SRM 445

Easy:

えっ＞＜となるもおそらく解は.0か.5の形なので2倍して全探索すると通るだろうと思ってその通りに書くと通る。こわい。

214.19pts

//E? Nandatte?
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define ge 200
class TheNewHouseDivOne{
public:
double distance(vector <int> x, vector <int> y, int k)
{
	for(int i=0;i2;
		y[i]*=2;
	}
	int ret=INF;
	
	for(int i=-150;i<=150;i++)
	{
		for(int j=-150;j<=150;j++)
		{
			vector<int>v;
			for(int d=0;d1]);
		}
	}
	
	return (double)ret/2.0;
	}
};

Med:

※以下leading-zeroは無視します

長さlの文字列は2^l通りある。

ここでルール上長さlの文字列をすべて使い切ったあとはl+1の長さにしなければならない。

先頭の0以外は1にしても困るのでl+1文字の文字列のブロックはl文字の文字列のブロックの最後のものの頭に'1'をつけたものになる。

また、ルール上ブロックの二つ目は10...0という形になるので

先頭の1とその他を分けたとき、その他の方は長さ1~lのやつに0を付けてl文字にしたやつを順につけてることが

わかるので、あとは適当にほげ

165pts

//E? Nandatte?
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<long long,long long> ss;
typedef pair P;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
class TheLockDivOne{
public:
string password(int n, long long k)
{
	string ret="";
	vector
vec;
	vec.pb(mp(mp(1,k),""));
	string nowbest="";
	for(int a=0;along long d=(1LL<<(n-a-1));
		int hoge=vec.size();
		for(int i=0;iif(p.first.first-d>1)
			{
				vec[i].first.first-=(d+1);
				vec[i].first.second-=(d+1);
				vec[i].second+='1';
			}
			else if(p.first.second-d<1)
			{
				vec[i].second+='0';
			}
			else
			{
				P b;
				b.first.first=(1LL<<(n-a-1));
				b.first.second=(1LL<<(n-a-1));
				b.second=vec[i].second+"1";
				vec.pb(b);
				vec[i].first.first=1;
				vec[i].first.second-=(d+1);
				vec[i].second+='1';

				
			}
			cout << i << endl;
			cout << vec[i].first.first << " " << vec[i].first.second << " " << vec[i].second << endl;
		}
	}
	for(int i=0;ireturn nowbest;
}
};

TestSRM

E>M>Hの珍しいセット。

300-500-700

Easy(=SRM202D1E):

面倒 of the 面倒。こういう問題きらい。Room3のdreamoonさんのコードが簡潔でいいと思うので消えない内に

みておくといいかもです

75pts

//E? Nandatte?
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
class 
Hyphenated{
public:
double avgLength(vector  lines)
{
	int a=0,b=0;
	bool hy=false;
	int now=0;
	for(int i=0;iint d=lines[i].size();
		for(int j=0;jif(lines[i][j]==' ' || lines[i][j]=='.')
			{
				if(!now) continue;
				cout << now << endl;
				a+=now;
				b++;
				now=0;
				hy=false;
			}
			else if(lines[i][j]=='-')
			{
				if(j==d-1 && d!=1 && lines[i][d-2]!=' ' && lines[i][d-2]!='.' && lines[i][d-2]!='-')
				{
					hy=true;
				}
				else
				{
					if(!now) continue;
					a+=now;
					cout << now << endl;
					b++;
					now=0;
					hy=false;
				}			
			}
			else
			{
				now++;
			}
			
		}
		if(now)
		{
			if(i==lines.size()-1 ||  (lines[i+1][0]==' ' || lines[i+1][0]=='.' || lines[i+1][0]=='-') || !hy)
			{
					if(!now) continue;
					a+=now;
					cout << now << endl;
					b++;
					now=0;
					hy=false;
			}
		}		
		hy=false;				
	}
	if(now){ a+=now; b++;}
	cout << a << " " << b << endl;
	return (double)a/b;
	}
};

Med(=SRM347D1M):

数学ゲー？

なんかさぶたんという怖いものは使えないので

にぶたんを使いました。さすがにおちるよねwと思ったら通った。

338.26pts

//E? Nandatte?
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
class FlightScheduler{
public:
double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel)
{
	double as=1e18;
	long long lb=0;
	long long ub=1e12;
	while(ub-lb>1)
	{
		int i=(lb+ub)>>1;
		double s=distance*1.0/i*1.0/K*1.0;
		double sd=pow(2.71828182846,s);
		sd-=1.0;
		sd*=emptyMass;
		sd=sd*i+takeoffFuel*1.0*i;
		
		double ss=distance*1.0/(i+1)*1.0/K*1.0;
		double ssd=pow(2.71828182846,ss);
		ssd-=1.0;
		ssd*=emptyMass;
		ssd=ssd*(i+1)+takeoffFuel*1.0*(i+1);
		
		if(sdelse lb=i;
		
	}
		double ss=distance*1.0/ub*1.0/K*1.0;
		double ssd=pow(2.71828182846,ss);
		ssd-=1.0;
		ssd*=emptyMass;
		ssd=ssd*ub+takeoffFuel*1.0*ub;	
	return ssd;
}};

Hard(=SRM296D1H):

三つの文字列に含まれる部分文字列の総数は？

シンプルな良問だが明らかにD1Mで使うべき。

最後の文字をきめうちすると、

明らかにその文字がある場所の内一番右しか考えなくて良い。

その他の文字列も同じことがいえ、

次に考えるべきことは

それぞれの文字列に対し一番右の場所より左の部分文字列に対してこの問題を

解き、その答え+1(何も選ばなくていいので)をたせばいい。

よってメモ化再帰すればおｋ.

746.56pts

//E? Nandatte?
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
long long  mem[55][55][55]={};
string a,b,c;
long long dp(int x,int y,int z)
{
	if(!x || !y || !z) return 0LL;
	if(mem[x][y][z]) return mem[x][y][z];
	int rmost[26][3];
	for(int i=0;i<26;i++)for(int j=0;j<3;j++) rmost[i][j]=-1;
	for(int i=0;i'a'][0]=i;
	}
	for(int i=0;i'a'][1]=i;
	}
	for(int i=0;i'a'][2]=i;
	}	
	for(int i=x-1;i>=0;i--)
	{
		int s=rmost[a[i]-'a'][0];
		if(s!=i) continue;
		int t=rmost[a[i]-'a'][1];
		int u=rmost[a[i]-'a'][2];
		if(t==-1 || u==-1) continue;
		mem[x][y][z]+=dp(s,t,u)+1LL;
	}
	return mem[x][y][z];
}
class CountingCommonSubsequences{
public:

long long countCommonSubsequences(string _a, string _b, string _c)
{
	a=_a;
	b=_b;
	c=_c;
	
	return dp(a.size(),b.size(),c.size());
}
};

明日のSRMはレート1900代にするというやばい目標を立てときます(笑)