2012-07-07
SRM460Div1HARD(TheCitiesAndRoadsDivOne)
Div1HARD |
最初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 |
まず、最初に16以下の素数で割りまくる。この過程で既に計算量が2500^2を超えるので、定数倍に気をつけて実装しなくてはいけない問題だと気づく。この手の問題は16以下の素数にどんなものが存在するかきちんと調べることが必要。最悪ケースのテストを作りにくいので、定数倍に細心の注意を払いながら実装する。
#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 |
各マスを中心に両側探索を行う。最悪計算量の見積もりが難しい。
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
リンク元
- 127 http://topcoder.g.hatena.ne.jp/
- 28 https://www.google.co.jp/
- 12 topcoder.g.hatena.ne.jp
- 9 http://topcoder.g.hatena.ne.jp/keyworddiary/Codeforces
- 5 https://www.google.com/
- 5 http://topcoder.g.hatena.ne.jp/n4_t/
- 3 http://www.google.co.jp/url?sa=t&rct=j&q=hirosegolf&source=web&cd=36&ved=0CD0QFjAFOB4&url=http://topcoder.g.hatena.ne.jp/hirosegolf/?word=*%5BSRM%E7%B7%B4%E7%BF%92%5D&ei=4bJ6UKPdIJGuiQfBpoCwBg&usg=AFQjCNHxQgfkyGt1vBznw97jHZsoPoS14A
- 2 http://www.google.co.jp/search?hl=ja&client=chrome-mobile&q=aho-corasick+topcoder&oq=aho-corasick+topcoder&gs_l=mobile-gws-serp.3..0i30.5945.14371.0.15749.19.18.0.0.0.1.650.3312.5j2j1j2j0j3.13.0...0.0...1ac.IFiOQs-tyS0&mvs=0
- 2 http://webcache.googleusercontent.com/search?q=cache:UcVVSf32JNIJ:topcoder.g.hatena.ne.jp/hirosegolf/20111218+PrinceXDominoes&cd=20&hl=ja&ct=clnk&gl=jp&lr=lang_ja
- 2 http://www.google.co.jp/url?sa=t&rct=j&q="ostream& operator"&source=web&cd=6&ved=0CE4QFjAF&url=http://topcoder.g.hatena.ne.jp/hirosegolf/20120707&ei=AOdGUL_BCePvmAXnt4DQCQ&usg=AFQjCNE2G3voAPuS5iKVfwK3jkELA4umyg