2013-08-19

■ SRM566D1M PenguinEmperor 18:20

要約:

1<=i<=daypassedをみたす整数iに対し

i%numcities分左か右に行くことを繰り返す。

もとにもどってくるような行き方は何通り？

解法:

dp[i][j]=i日後にjにいるような動き方の総数

two[i][j]=2^i*numcities日後にjにいるような動き方の総数

dp2[i]=daypassed-daypassed%numcities日後にiにいるような動き方の総数

をてきとうに更新すると通る。簡単。

#line 2 "PenguinEmperor.cpp"
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
// I'll become a member of  IOI 2014 Japan team.
#include 
#include 
#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 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i
ll dp[355][355];
ll two[65][355];
ll dp2[2][355];
class PenguinEmperor
{
	public:
	int countJourneys(int numCities, long long daysPassed) 
	{
		dp[0][0]=1;
		for(int i=1;i<=numCities;i++)
		{
			for(int j=0;jint t=(j-i+numCities)%numCities;
				int s=(j+i)%numCities;
				if(t!=s) dp[i][j]=(dp[i-1][t]+dp[i-1][s])%mod;
				else dp[i][j]=dp[i-1][t];
				//cout << i << " " << " " << j << " " << dp[i][j] << endl;
			}
		}
		
		if(daysPassed<=numCities) return dp[daysPassed][0];

		for(int i=0;i0][i]=dp[numCities][i];
		for(int i=0;i<60;i++)
		{
			for(int j=0;jfor(int k=0;k1][(j+k)%numCities]+=(two[i][j]*two[i][k])%mod;
					two[i+1][(j+k)%numCities]%=mod;
				}
			}
		}
		ll ret=0;
		ll x=daysPassed/numCities;
		int cur=0,nxt=1;
		dp2[cur][0]=1LL;
		for(int i=0;i<=60;i++)
		{
			if(((x>>i)&1LL))
			{
				for(int j=0;j<355;j++) dp2[nxt][j]=0;
				for(int j=0;jfor(int k=0;kfor(int i=0;ireturn ret;
	}
};

ツイートする

■ SRM525D1M Rumor 07:00

要約: N匹のうさぎさんがぴょんぴょんしている。

うさぎさんは噂好きなので、

1日に自分が知っている噂の内1つを自分のことを信用しているうさぎに伝える。

はじめにうさぎが噂を2つとも知っているか両方知らないかと

N*Nの行列でうさぎがどのうさぎを信用しているかが与えられるので

最低何日ですべてのうさぎに噂が伝わるか求めよ。

制約:N<=16

解法:

噂が二つあるとき決めなければいけないことは

どちらを先に伝えるべきか、ということである。

よって、すべてのうさぎにたいしてどちらの噂を先に伝えるか、

ということを決めうちすると、

ただのやるだけと化しますが

実装力がないので無限に時間がかかりました。

157pts

//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 Rumor{
public:
int getMinimum(string knowledge, vector  graph)
{
	int n=knowledge.size();
	int ret=INF;
	bool path[20][20]={};
	for(int i=0;ifor(int j=0;j'Y');
		}
	}
	
	for(int i=0;i<(1<int decide[17]={};
		int have[20][2]={};
		for(int j=0;jif(knowledge[j]=='Y') have[j][0]=have[j][1]=1;
			decide[j]=((i>>j) & 1);
		}
		queue
que;
		int cur[20]={};
		bool already[20][3]={};
		for(int j=0;j0]?3:0;
		}
			int now=0;
		while(1)
		{
			while(!que.empty()) que.pop();
			for(int j=0;jif(cur[j] && !(already[j][1] && already[j][2])) que.push(mp(j,cur[j]));
			}
			int s=que.size();
			int all=count(cur,cur+n,3);
			if(all==n)
			{
				ret=min(ret,now);
				//cout << now << endl;
				break;
			}
			bool update=false;
			now++;
			while(s--)
			{
				bool par=false;
				P p=que.front();
				int up=p.first;
				int info=p.second;
				if(info==1 && !already[up][1])
				{
					//par=true;
					for(int j=0;jif(path[up][j])
						{
							if(cur[j]==0 || cur[j]==2)
							{
								que.push(mp(j,cur[j]+1));
								update=true;
								cur[j]++;
							}
						}
					}
					already[up][1]=true;
				}
				if(info==2 && !already[up][2])
				{
				//par=true;
					for(int j=0;jif(path[up][j])
						{
							if(cur[j]==0 || cur[j]==1)
							{
								que.push(mp(j,cur[j]+2));
								cur[j]+=2;
								update=true;
								par=true;
							}
						}
					}
					already[up][2]=true;
				}	
				if(info==3 && !(already[up][1] && already[up][2]))
				{
				//par=true;
						if(already[up][1] || (decide[up] && !already[up][2]))
						{
							for(int j=0;jif(path[up][j])
								{
									if(cur[j]==0 || cur[j]==1)
									{
										que.push(mp(j,cur[j]+2));
										cur[j]+=2;
										update=true;
										par=true;
									}
								}
							}
							already[up][2]=true;	
						}
						else
						{
							for(int j=0;jif(path[up][j])
								{
									if(cur[j]==0 || cur[j]==2)
									{
										que.push(mp(j,cur[j]+1));
										cur[j]++;
										update=true;
										par=true;
									}
								}
							}
							already[up][1]=true;	
						}
				}
				que.pop();
			}		
			if(!update) break;
		}	
	}
		return ret==INF?-1:ret;
	}
};

ツイートする