2014-03-29

■ SRM 614 03:08

Easy:

D1Easyらしい問題。こういうの好きです

class MinimumSquare
{
	public:
	long long minArea(vector <int> x, vector <int> y, int K) 
	{
		int n=x.size();
		ll res=1LL*9e18;
		for(int i=0;ifor(int ii=0;ii1;
				ll ay=y[ii]-1;
				vectord;
				for(int j=0;jif(ax >= x[j]) continue;
					if(ay >= y[j]) continue;
					d.pb(max(1LL*x[j]-ax,1LL*y[j]-ay)+1LL);
				}
				sort(d.begin(),d.end());
				if(d.size()continue;
				res=min(res,d[K-1]*d[K-1]);
			}
		}
		return res;
	}
};

Med

D2Medに出そうなDPをしてからD1Easy+くらいのDPをすると解ける。

ll dp[55][2];
ll t[1000005][2];
class CycleColoring
{
	public:
	long long modpow(long long x,long long n)
	{
		long long res=1;
		while(n>0)
		{
			if(n&1) res=res*x%mod;
			x=x*x%mod;
			n>>=1;
		}
		return res;
	}
	int countColorings(vector <int> vertexCount, vector <int> fromVertex, vector <int> toVertex, int K) 
	{
		//same...0
		//dif...1
		t[0][0]=1;
		t[1][0]=0;
		t[1][1]=(K-1)%mod;
		for(int i=2;i<=1000000;i++)
		{
			t[i][0]=t[i-1][1];
			t[i][1]=t[i-1][0]*1LL*(K-1)+t[i-1][1]*1LL*(K-2);
			t[i][1]%=mod;
		}
		int n=vertexCount.size();
		if(fromVertex[0] == toVertex[n-1])
		{
			dp[0][0]=t[ vertexCount[0]-1 ][1];
		}
		else
		{
			int a=fromVertex[0];
			int b=toVertex[n-1];
			int c=abs(a-b);
			c--;
			dp[0][0]=(t[c][1]*t[vertexCount[0]-2-c][1])%mod;
			ll x=t[c][0]+ ( (t[c][1]*(K-2LL)%mod) * modpow(K-1LL,mod-2) )%mod;
			x%=mod;
			ll y=t[vertexCount[0]-2-c][0]+ ( (t[vertexCount[0]-2-c][1]*(K-2LL))%mod * modpow(K-1LL,mod-2) )%mod;
			y%=mod;
			dp[0][1]=(x*y%mod)*(K-1LL)%mod;
		}
		for(int i=1;iif(fromVertex[i] == toVertex[i-1])
			{
				dp[i][0]=(dp[i-1][0]*t[ vertexCount[i]-1 ][1])%mod;
				dp[i][1]=(dp[i-1][1]*t[ vertexCount[i]-1 ][1])%mod;
			}
			else
			{
				int a=fromVertex[i];
				int b=toVertex[i-1];
				int c=abs(a-b);
				c--;
				dp[i][0]=(dp[i-1][0] * ((t[c][1]*t[vertexCount[i]-2-c][1])%mod) )%mod;
				ll x=t[c][0]+ ( (t[c][1]*(K-2LL)%mod) * modpow(K-1LL,mod-2) )%mod;
				x%=mod;
				ll y=t[vertexCount[i]-2-c][0]+ ( (t[vertexCount[i]-2-c][1]*(K-2LL)%mod) * modpow(K-1LL,mod-2) )%mod;
				y%=mod;
				dp[i][1]=((dp[i-1][0] * (x*y%mod) )%mod)*(K-1LL)%mod;
				dp[i][0]=( dp[i][0] + (dp[i-1][1] * (x*y%mod) )%mod )%mod;
				
				dp[i][1]=( dp[i][1] + ((dp[i-1][1] * (x*y%mod) )%mod)*(K-2LL)%mod)%mod;
				dp[i][1]=( dp[i][1] + (dp[i-1][1] * ((t[c][1]*t[vertexCount[i]-2-c][1])%mod)))%mod;
			}
		}
		return (dp[n-1][0]*K)%mod;
	}
};

Hard:

brute force通るんですか...

challenge +1を生やす

systest 通る。38位

Rating 1790->1934(+144)

高1のうちにRedCoderになりたい。(fin)

ツイートする