2013-08-07 - HIR180's diary

■ SRM534&SRM402 00:40

今日(昨日?)はSRMを2setやりました

SRM 534

oo- 121.04,(295.92),0.0

416.96pts 63位相当

Easy:

ゲームの必勝法。

状態数が高々2^20なのでDPをする

バグる。

提出.121.04pts

終了後めっちゃ簡単に解けることが分かる。闇。

//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
int dp[(1<<20)]={};
class EllysCheckers{
public:
string getWinner(string board)
{
	dp[0]=-1;
	int n=board.size();
	for(int i=1;i<(1<<(n-1));i++)
	{
	bool used[25]={};
		for(int j=0;j1;j++)
		{
			if(((i>>j) & 1))
			{
				used[j]=true;
			}
		}
		for(int j=0;j1;j++)
		{
			if(!j && used[j])
			{
				if(dp[i-1]==-1) {dp[i]=1; goto end;}
			}
			else if(j==2 && used[j])
			{
				if(dp[i-4]==-1) {dp[i]=1; goto end;}
				if(!used[j-1] && dp[i-2]==-1 ) {dp[i]=1; goto end;}
			}
			else if(used[j])
			{
				if(j!=1){ if(dp[i-(1<<(j-3))*7]==-1 && !used[j-3]) {dp[i]=1; goto end;}}
				if(dp[i-(1<<(j-1))]==-1 && !used[j-1]) {dp[i]=1; goto end;}
			}
		}
		dp[i]=-1;
		end:;
	}
	reverse(board.begin(),board.end());
	int nest=0;
	for(int i=1;i'o'?(1<<(i-1)):0;
	}
	return dp[nest]==1?"YES":"NO";
}
};

Med

昔解いていた。

なんかbitDPしないといけないみたいなんだけど

mapをつかってゆるふわ～とDPしたら通る

//E? Nandatte?
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define pb push_back
long long gcd(long long a,long long b)
{
	if(aif(a%b==0) return b;
	else return gcd(b,a%b);
}
class EllysNumbers
{
	public:
	long long getSubsets(long long n,vector special)
	{
		vector<long long>sp;
		string all="";
		for(int i=0;i<(int)special.size();i++)
		{
			all+=special[i];
		}
		long long int cur=0;
		for(int i=0;iif(all[i]==' ')
			{
				sp.push_back(cur);
				cur=0;
				continue;
			}
			cur*=10ll;
			cur+=all[i]-'0';
		}
		if(cur)
		{
			sp.pb(cur);
			cur=0ll;
		}
		sort(sp.begin(),sp.end());
		vector<long long> ele;
		bool chance=0;
		for(int i=0;iif(n % sp[i] == 0)
			{
				long long e=n/sp[i];
				if(gcd(sp[i],e) == 1)
				{
					ele.pb(sp[i]);
					if(sp[i]==1) chance=1;
				}
			}
		}
		map<long long,long long>m;
		m[1]=1;
		for(int i=0;ilong long,long long>::iterator it;
			for(it=m.begin();it!=m.end();++it)
			{
				long long se=n/(it->first);
				if(se%ele[i]==0)
				{
					m[(it->first)*ele[i]]+=it->second;
				}
			}
		}
		return m[n];
	}
};

SRM 402

x-- 0.00,0.00,0.00

0.00pts hoge位相当

本番だったら1772->72(-1700)

easy:

サイズが8なので普通にやればいい。

再帰を使うと割とらくに書ける。

メモ化わすれてTLE.楽しい！！✌('ω'✌ )三✌('ω')✌三( ✌'ω')✌

//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
mapint>,double>ma;
double rec(vector<int>per,int depth)
{
double ret=0.0;
if(ma[per]>0.0) return ma[per];
int div=0;
	for(int i=0;ifor(int j=i+1;jif(per[i]>per[j])
			{
				div++;
				swap(per[i],per[j]);
				double sub=rec(per,depth+1);
				ret+=sub;
				swap(per[i],per[j]);
			}
		}
	}
	if(!div) return 0.0;
	else return ma[per]=ret/div+1.0;
}
class RandomSort{
public:
double getExpected(vector <int> permutation)

{
	double p=rec(permutation,0);
	return p;
}
};

Med:

区間をもってひとつづつ消していって

つなげて並べて比較する。

読み間違えと実装力のなさのせいですごく時間がかかった＞＜


//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
class LargestGap{
public:
int getLargest(vector  board)
{
	vectorstore;
	string all="";
	for(int i=0;ichar prev;
	int cur=0;
	vectorprs;
int fss=0;
	if(all[0]==all[all.size()-1]) fss=1;
	P1 res;
	for(int i=0;iif(!i)
		{
				prev=all[i];
				cur++;
		}
		else if(prev!=all[i])
		{
		if(fss)
		{
			if(prev=='X') res=(mp(mp(cur,0),i-cur));
			else res=(mp(mp(cur,1),i-cur));
			fss--;
			goto fil;
		}
			if(prev=='X') store.pb(mp(mp(cur,0),i-cur));
			else store.pb(mp(mp(cur,1),i-cur));
			
			fil:;
			prev=all[i];
			cur=1;
		}
		else
		{
			cur++;
		}
	}
	int m[2505];
	if(res.first.first)
	{
			if(prev=='X') store.pb(mp(mp(cur+res.first.first,0),0));
			else  store.pb(mp(mp(cur+res.first.first,1),0));
	}
	else
	{
			if(prev=='X')  store.pb(mp(mp(cur,0),all.size()-cur));
			else  store.pb(mp(mp(cur,1),all.size()-cur));
	}
	int c=0;
	int s=0;
	vector<int>pri;
	vector<int>nowbest,hok;
	for(int i=0;i" " <" " << store[i].second <if(store[i].first.second) { prs.pb(mp(store[i].first.first,s));pri.pb(store[i].first.first); }
		s+=store[i].first.first;
	}
	sort(pri.begin(),pri.end(),greater<int>());
	int bestidx=INF;
	int rui=0;
	for(int i=0;iif(store[i].first.second) continue;
		
		int p=store[(i+store.size()-1)%store.size()].first.first;
		int q=store[(i+store.size()+1)%store.size()].first.first;
		vector<int>now;
		int a=0,b=0,c=0;
		for(int ii=0;iiif(!a && pri[ii]==p){a=1; continue;}
			if(!b && pri[ii]==q){b=1; continue;}
			if(pri[ii]<=p+q && !c)
			{
				now.pb(p+q);
				c=1;
				ii--;
				continue;
			}
			now.pb(pri[ii]);
		}
		if(!c) now.pb(p+q);
		cout << i << endl;
		for(int ii=0;ii" ";
		cout << endl;
		if(nowbest.empty()) { nowbest=now; bestidx=store[i].second;}
		else
		{
		bool winam=true,win=false;
			for(int ii=0;iiif(nowbest[ii]true; break;}
				else if(nowbest[ii]>now[ii]) { winam=false;break;}
			}
			if(win) { nowbest=now;  bestidx=store[i].second;}
			else if(winam) bestidx=min(store[i].second,bestidx);
		}
	}
	
	return bestidx;
	}
};

まとめ:探索&実装ゲー得意になりたい