Hatena::Grouptopcoder

hirosegolf@競技プログラミング

2012-07-07

SRM460Div1HARD(TheCitiesAndRoadsDivOne)

Div1HARD | 20:52

最初bit-dpかと思って苦労した。実際は20の分割数があまり大きくないことをつかうパターン。その意味で、TCO11WildCardのHardと似ている。http://topcoder.g.hatena.ne.jp/hirosegolf/20120612#1339488542。実行時間は適当に組んでも最悪ケースで100m程でかなり余裕がある。


#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ALL(s) (s).begin(),(s).end

#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(a,b) make_pair((a),(b))

using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<long long> vl;
typedef vector<vector<long long> > vvl;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
typedef vector<string> vs;

ll mod=1234567891;
struct mint{
	ll value;
	mint():value(0){}
	mint(ll v):value((v%mod+mod)%mod){}
};
mint& operator+=(mint&a, mint b){return a=a.value+b.value;}
mint& operator-=(mint&a, mint b){return a=a.value-b.value;}
mint& operator*=(mint&a, mint b){return a=a.value*b.value;}
mint operator+(mint a, mint b){return a+=b;}
mint operator-(mint a, mint b){return a-=b;}
mint operator*(mint a, mint b){return a*=b;}
mint operator-(mint a){return 0-a;}
bool operator==(mint a, mint b){return a.value==b.value;}
bool operator!=(mint a, mint b){return a.value!=b.value;}
 
 
std::ostream& operator<<(std::ostream& os, const mint& m){
return ( os << m.value );}
ll extgcd(ll a, ll b, ll &x, ll &y){
	ll d=a;
	if(b!=0){
		d=extgcd(b, a%b, y, x);
		y-=(a/b)*x;
	}
	else{
		x=1,y=0;
	}
	return d;
}
ll modinverse(ll a, ll b){
	ll x,y;
	ll d=extgcd(a,b, x, y);
	assert(d==1);
	return (x%b+b)%b;
}
mint& operator/=(mint&a, mint b){return a=a.value*modinverse(b.value,mod);}
mint operator/(mint a, mint b){return a/=b;}

mint p1, p2;

int n;
map<vi, mint> memo;
mint rec(vi a, int b){
	vi aa=a;
	aa.pb(b);
	if(EXIST(memo, aa)){
		return memo[aa];
	}
	mint &ret=memo[aa];
	mint ans=0;
	if(b==0){
		REP(i,a.size()) ans+=(a[i]-1)*(a[i]-2)/2*rec(a, 1);
	}
	REP(i1,a.size()) FOR(i2, i1+1, a.size()){
		vi na;
		REP(i,a.size()) if(i!=i1 && i!=i2) na.pb(a[i]);
		na.pb(a[i1]+a[i2]);
		sort(na.begin(), na.end());
		ans+=rec(na, b)*a[i1]*a[i2];
	}
	if(a.size()==1){
		if(b==0){
			ans+=p1;
		}
		else ans+=p2;
	}
	return ret=ans;
}

class TheCitiesAndRoadsDivOne {
public:
	int find(vector <string> m) {
		n=m.size();
		vi u;
		int b=0;
		int tot=0;
		{
	 
			vi par(n);
			REP(i,n)par[i]=i;
			REP(i,n) FOR(j,i+1,n) if(m[i][j]=='Y'){
				tot++;
				int t=par[j];
				if(t==par[i])b=1;
				REP(x,n) if(par[x]==t)par[x]=par[i];
			}
			map<int,int> z;
			REP(i,n) z[par[i]]++;
			EACH(pp,z){
				u.pb(pp->second);
			}
		}
		p1=1, p2=1;
		for(int k=1; k<=n-1-tot; k++) p1/=k;
		for(int k=1; k<=n-tot; k++) p2/=k;
		//deb(p1);
		//deb(p2);
		if(tot==n)p1=0;
		sort(u.begin(), u.end());
		//debug(b);
		//debug(u);
		memo.clear();
		int ans=rec(u,b).value;
		
		return ans;
	}
	

};

SRM519Div1HARD(VerySmoothDecomposition)

Div1HARD | 19:11

まず、最初に16以下の素数で割りまくる。この過程で既に計算量が2500^2を超えるので、定数倍に気をつけて実装しなくてはいけない問題だと気づく。この手の問題は１６以下の素数にどんなものが存在するかきちんと調べることが必要。最悪ケースのテストを作りにくいので、定数倍に細心の注意を払いながら実装する。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ALL(s) (s).begin(),(s).end

#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(a,b) make_pair((a),(b))

using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<long long> vl;
typedef vector<vector<long long> > vvl;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
typedef vector<string> vs;

int mod=1000000009;
int b[2600];

class VerySmoothDecompositions {
public:
	int solve(vector <string> digits) {
		vi bs;		
		REP(i,digits.size()){
			REP(j,digits[i].size()){
				bs.pb(digits[i][j]-'0');
			}
		}
		int ps[6]={2,3,5,7,11,13};
		vi cnt(6);
		vi nbs(bs.size());
		REP(ip,6){
			int p=ps[ip], rem=0;
			while(true){
				REP(i,bs.size()){
					nbs[i]=(rem+bs[i])/p;
					rem=(rem+bs[i])%p*10;
				}
				if(rem!=0)break;
				REP(i,bs.size()) bs[i]=nbs[i];
				cnt[ip]++;
			}
		}
		{
			int tot=0;
			REP(i,bs.size()) tot+=bs[i];
			if(tot!=1)return 0;
		}
		//debug(cnt);
		int m2=cnt[0], m3=cnt[1];
		vvi g(m2+1, vi(m3+1));
		g[m2][m3]=1;
		int d[8]={2,3,4,6,8,9,12,16};
		REP(ii,8){
			int n=d[ii];
			int c2=0, c3=0;
			while(n%2==0){
				n/=2;
				c2++;
			}
			while(n%3==0){
				n/=3;
				c3++;
			}
			for(int i2=m2; i2>=c2; i2--){
				for(int i3=m3; i3>=c3; i3--){
					g[i2-c2][i3-c3]+=g[i2][i3];
					if(g[i2-c2][i3-c3]>=mod)g[i2-c2][i3-c3]-=mod;
				}
			}
		}
		ll ans=0;
		for(int i2=0; i2<=m2; i2++) for(int i3=0; i3<=m3 && i3<=cnt[2]; i3++){
				int n5=cnt[2]-i3, n7=cnt[3];
				if(n5+n7<i2)break;
				ans+=(ll)(min(n5, i2) - max(0,i2-n7) + 1) * g[i2][i3];
				ans%=mod;
			}
		
		return ans;
	}
	

};

SRM523Div1HARD(AlphabetPaths)

Div1HARD | 11:14

各マスを中心に両側探索を行う。最悪計算量の見積もりが難しい。

441*3^10なので時間的に結構ぎりぎり。このようなタイプの問題だと、最悪のケースをテストしながら高速化していくのが定石だと思っているが、最悪ケースを作るのが難しいのでとてもやっかい。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ALL(s) (s).begin(),(s).end

#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(a,b) make_pair((a),(b))

using namespace std;

// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<long long> vl;
typedef vector<vector<long long> > vvl;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
typedef vector<string> vs;



int maze[30][30];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int ind;
int cnt[1<<21];
int hist[1<<21];
ll ans;
int target;
void rec(int x, int y, int rem, int b){
	//deb(x);deb(y);deb(rem);deb(b);debl;
	if(rem==0){
		if(hist[b]!=ind){
			hist[b]=ind;
			cnt[b]=0;
		}
		cnt[b]++;
		int rev_b=target^b;
		//debug(rev_b);
		if(hist[rev_b]==ind){
			ans+=cnt[rev_b];
		}
		return;
	}
	REP(r,4){
		int nx=x+dx[r], ny=y+dy[r];
		if((b|maze[nx][ny])!=b){
			rec(nx,ny,rem-1,b|maze[nx][ny]);
		}
	}
	return;
}

class AlphabetPaths {
public:
	long long count(vector <string> letterMaze) {
		int mx=letterMaze.size();
		int my=letterMaze[0].size();
		string s="ABCDEFZHIKLMNOPQRSTVX";
		clr(maze);
		clr(hist);
		ind=1;		
		REP(x, mx){
			REP(y,my){
				REP(i, s.size()){
					if(letterMaze[x][y]==s[i])maze[x+1][y+1]=1<<i;
				}
			}
		}
		ans=0;
		REP(x,mx+1) REP(y, my+1){
			ind++;
			if(maze[x][y]){
				target=(1<<21)-1-maze[x][y];
				rec(x,y,10,maze[x][y]);
			}
		}
		return 2*ans;
	}
	

};
コメントを書く

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/hirosegolf/20120707
リンク元
日記の検索
カレンダー
<< 2012/07 >>
日 月 火 水 木 金 土
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
最新タイトル
カテゴリー
最新日記一覧