Hatena::Grouptopcoder

Hiro180の日記

 | 

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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> 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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> 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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> 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 <string> table)
{
	int s=table.size();
	table.resize(2*s);
	for(int i=0;i<2*s;i++)
	{
		if(i<s)
		{
			table[i]+=table[i];
		}
		else
		{
			table[i]=table[i-s];
		}
	}
	long long ma[26]={};
	for(int i=0;i<table.size();i++)
	{
		for(int j=0;j<table[0].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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> P1;
typedef pair<P,P> 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(a<b) swap(a,b);
	if(a%b==0) return b;
	else return gcd(b,a%b);
}
class IngredientProportions{
public:
vector <int> getMasses(vector <string> proportions)
{
	int edge[15][15]={};
	queue<P1>que;
	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;
	vector<string>vec=proportions;
	for(int i=0;i<vec.size();i++)
	{
		int 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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> 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;i<x.size();i++)
	{
		x[i]*=2;
		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;d<x.size();d++)
			{
				v.pb(abs(i-x[d])+abs(j-y[d]));
			}
			sort(v.begin(),v.end());
			ret=min(ret,v[k-1]);
		}
	}
	
	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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<long long,long long> ss;
typedef pair<ss,string> P;
typedef pair<P,P> 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<P>vec;
	vec.pb(mp(mp(1,k),""));
	string nowbest="";
	for(int a=0;a<n;a++)
	{
		long long d=(1LL<<(n-a-1));
		int hoge=vec.size();
		for(int i=0;i<hoge;i++)
		{
			P p=vec[i];
			if(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;i<vec.size();i++)
	{
		nowbest=max(nowbest,vec[i].second);
	}

	return nowbest;
}
};

TestSRM


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

300-500-700

Easy(=SRM202D1E):

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

みておくといいかもです

75pts

//E? Nandatte?
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> 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 <string> lines)
{
	int a=0,b=0;
	bool hy=false;
	int now=0;
	for(int i=0;i<lines.size();i++)
	{
		int d=lines[i].size();
		for(int j=0;j<d;j++)
		{
			if(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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> 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(sd<ssd) ub=i;
		else 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(何も選ばなくていいので)をたせばいい。

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

746.56pts

//E? Nandatte?
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> 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<x;i++)
	{
		rmost[a[i]-'a'][0]=i;
	}
	for(int i=0;i<y;i++)
	{
		rmost[b[i]-'a'][1]=i;
	}
	for(int i=0;i<z;i++)
	{
		rmost[c[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代にするというやばい目標を立てときます(笑)

snukesnuke2013/08/12 02:50ちなみにTEST SRMの問題は過去問です。

Hiro180Hiro1802013/08/12 02:56一応そのことは知ってました()コメントありがとうございます!!

 |