Hatena::Grouptopcoder

hirosegolf@競技プログラミング

2012-07-07

SRM460Div1HARD(TheCitiesAndRoadsDivOne)

| 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)

| 19:11

まず、最初に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)

| 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;
	}
	

};

2012-07-06

SRM526.5(MagicMatchGame)

| 12:19

単に合計を最大にするだけなら、普通に貪欲法を使えばいいが、R*Bを最大化したいので工夫が必要。正の数x,yに対して、x*R+y*Bを最大化すれば、(x,y)の値によってはR*Bが最大となるようなR,Bが得られる。(x,y)の組み合わせを全て確かめるのは不可能だが、実際には(x,y)によって選択肢が分かれるような境界でだけ調べればいいので、実際に調べる必要(x,y)の組は高々50^2だけ。これ以外の問題でもR*R+B*Bを最大化したい場合とか、考え方自体は応用が広そう。

#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 pb push_back


using namespace std;


typedef vector<int> vi;
typedef long long ll;

int n;
bool ind(vi &z){
	int r=0;
	for(int i=0;i<20;i++){
		int v=-1;
		for(int k=0;k<z.size();k++){
			if((z[k]>>i)%2==1){
				if(v==-1){
					v=z[k];
					r++;
				}
				z[k]^=v;
			}
		}
	}
	//debug(z);
	//debug(r);
	return r==z.size();
}

vi red, blue;
ll wr,wb;
bool cmp(int i, int j){
	return wr*red[i]+wb*blue[i]<wr*red[j]+wb*blue[j];
}

class MagicMatchesGame {
public:
	long long minimumArea(vector <int> matches, vector <int> _red, vector <int> _blue) {
		long long ans=-1;
		red=_red, blue=_blue;
		vi z;
		for(int c=0;;c++){
			bool ok=false;
			for(int i=0;i<matches.size();i++){
				vi nz(z.begin(), z.end());
				nz.pb(matches[i]);
				if(ind(nz)){
					ok=true;
					z.pb(matches[i]);
					break;
				}
			}
			//debug(z);
			if(!ok){
				n=z.size();
				break;
			}
		}
		//debug(n);
		vi wrs, wbs;
		for(int i1=0;i1<red.size(); i1++){
			for(int i2=i1;i2<red.size();i2++){
				wbs.pb(abs(red[i2]-red[i1]));
				wrs.pb(abs(blue[i2]-blue[i1]));
			}
		}
		wbs.pb(1);wrs.pb(0);
		wbs.pb(0);wrs.pb(1);
	
		if(1){
			for(int iw=0;iw<wrs.size();iw++){
				wr=wrs[iw];
				wb=wbs[iw];
				z.clear();
				vi prio(matches.size());
				for(int i=0;i<matches.size();i++)prio[i]=i;
				sort(prio.begin(), prio.end(),cmp);
				int sr=0, sb=0;
				for(int ip=0;ip<matches.size();ip++){
					int i=prio[ip];
					vi nz(z.begin(), z.end());
					nz.pb(matches[i]);
					if(ind(nz)){
						z.pb(matches[i]);
						sr+=red[i];
						sb+=blue[i];
					}
				}
				ll nans=(ll)sr*sb;
				if(ans==-1 || nans<ans){
					ans=nans;
				}
			}
		}
		return ans;
	}
};

SRM535Div1HARD(FoxAndGreed)

| 11:42

母関数を使って紙の上で計算すれば、計算量は相当落ちる。やってみないと解けるかどうか分からない感じの問題。

#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())

// BEGIN CUT HERE
#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))
// END CUT HERE


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;

// BEGIN CUT HERE

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
// END CUT HERE

ll mod=10007;

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;
  extgcd(a,b, x, y);
  return (x%b+b)%b;
}
 
 
struct modular{
  ll value;
  modular(){
    value=0;
  }
  modular(ll v){
    value=(v%mod+mod)%mod;
  }
  modular operator+(const modular b){
    return modular(value+b.value);
  }
  modular operator-(const modular b){
    return modular( value-b.value );
  }
  modular operator*(const modular b){
    return modular( value*b.value );
  }
  modular operator/(const modular b){
    return modular( value*modinverse(b.value, mod) );
  }
};
 
modular operator+(ll a, modular b){
  return modular(a)+b;
}
modular operator-(ll a, modular b){
  return modular(a)-b;
}
modular operator*(ll a, modular b){
  return modular(a)*b;
}
modular operator/(ll a, modular b){
  return modular(a)/b;
}

typedef vector<modular> vm;
ll H, W, S;

vm fact;
modular powm(modular a, ll n){
	if(n==0)return 1;
	if(n%2==0)return powm(a*a,n/2);
	return a*powm(a*a, n/2);
}

modular calA(ll m, ll n){
	if(n<0)return 0;
	assert(m>=0);
	if(m==0)return(n==0 ? 1 : 0);
	return fact[n+m-1]/fact[n]/fact[m-1];
}

modular cal(ll x,ll y){
	return calA(H+W-2+x+y, S-x) * powm(S+1, H*W-(H+W-1)-(x+y));
}

class FoxAndGreed {
public:
	int count(int _H, int _W, int _S) {
	fact=vm(10000);
	fact[0]=1;
	FOR(i,1,fact.size()){
		fact[i]=fact[i-1]*i;
	}
	H=_H;
	W=_W;
	S=_S;
	if(H==1 && W==1){
		if(S==0)return 1;
		else return 0;
	}
	modular ans=0;
	//deb(H);deb(W);debl;
	vector<vm> a(H,vm(W));
	a[0][0]=1;
	REP(x,H-1) REP(y,W-1){
		a[x+1][y]=a[x+1][y]+a[x][y];
		a[x][y+1]=a[x][y+1]+a[x][y];
	}
	REP(x,H) REP(y,W) if(x!=H-1 || y!=W-1) if(x==H-1 || y==W-1){
		//deb(x);deb(y);deb(a[x][y].value);debl;
		ans=ans+a[x][y]*cal(x,y);
	}

    return ans.value;
  }
}

SRM536Div1HARD(BinaryPolynomialDivOne)

| 11:34

多項式をmod pでp乗したときの振る舞いを知っていれば難しくない。

本番ではバグを出して再提出になってしまった。

#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())

// BEGIN CUT HERE
#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))
// END CUT HERE


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;
// BEGIN CUT HERE

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
// END CUT HERE

class BinaryPolynomialDivOne {
public:
	int findCoefficient(vector <int> a, long long m, long long k) {
		map<ll,ll> z;
		z[0]=1;
		REP(i,62){
			if((m>>i)%2==1){
				map<ll,ll> nz;
				EACH(p,z){
					for(ll j=0; j<a.size(); j++){
						if(a[j]){
							ll t=p->first+(j<<i);
							if(t<=k && (k-t)%(1LL<<(i+1))==0){
								nz[t]+=p->second;
								nz[t]%=2;
							}
						}
					}
				}
				z=nz;
				//debug(z);
			}
		}
		//debug(z);
		int ans=z[k]%2;
		
		return ans;
	}
}

SRM537Div1HARD(PrinceXDominoes)

| 11:25

有向グラフ上で元の場所に戻る一筆書きを行うためには各頂点の入次数と出次数が等しくなくてはいけない(あと連結性)。各頂点の入次数と出次数が等しくなるように辺を取り除く行為は、出次数が多い頂点から入次数が多い頂点へフローを流す行為と対応することが分かる。なので最小費用流を用いれば答えが得られる。

#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 pb push_back
// BEGIN CUT HERE
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))

#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
// END CUT HERE


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 vector<int> vi;
typedef vector<vi> vvi;
// BEGIN CUT HERE

typedef pair<int,int> pii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
// END CUT HERE

struct edge{int to;ll cap;ll cost;int rev;
};

typedef pair<ll,int> pli;

const int MAX_V=40;
ll INF=1LL<<62-1;

struct cal_min_cost_flow{
	vector<edge> G[MAX_V];
	ll h[MAX_V];	//potential
	ll dist[MAX_V];
	int prev_v[MAX_V];
	int prev_e[MAX_V];
	void add_edge(int from, int to, ll cap, ll cost){
		G[from].pb( (edge){to,cap,cost,G[to].size()} );
		G[to].pb( (edge){from,0,-cost,G[from].size()-1} );
	}
	
	ll min_cost_flow(int s, int t, ll f){
		ll res=0;
		REP(v,MAX_V)h[v]=0;
		
		while(f>0){
			REP(v,MAX_V)dist[v]=INF;
			priority_queue<pli, vector<pli>, greater<pli> > Q;
			Q.push(pli(0,s));
			dist[s]=0;
			
			while(!Q.empty()){
				int v=Q.top().second; ll d=Q.top().first; Q.pop();
				if(dist[v]<d)continue; //古いのが残ってるかも
				assert(dist[v]==d);
				
				REP(i,G[v].size()){
					edge &e=G[v][i];
					int nv=e.to;
					ll nd=d+e.cost+h[v]-h[nv];
					if(e.cap>0 && dist[nv]> nd ){
						dist[nv]=nd;
						prev_v[nv]=v;
						prev_e[nv]=i;
						Q.push(pli(nd, nv));
					}
				}
			}
			
			if(dist[t]==INF)return -1;
			REP(v,MAX_V) h[v]+=dist[v];
			
			ll d=f; //流す量
			for(int v=t; v!=s; v=prev_v[v]){
				d=min(d, G[prev_v[v]][prev_e[v]].cap) ;
			}
			f-=d;
			res+=d*h[t];
			
			for(int v=t; v!=s; v=prev_v[v]){
				edge &e=G[prev_v[v]][prev_e[v]];
				e.cap-=d;
				G[v][e.rev].cap+=d;
			}
			
		}
		return res;
	}
};


class PrinceXDominoes {
public:
  int play(vector <string> dominoes) {
		int N=dominoes.size();
		int s=0, t=1+N;
		vvi d(N,vi(N,0));
		REP(i,N) REP(j,N){
			if(dominoes[i][j]!='.')d[i][j]=dominoes[i][j]-'A'+1;
		}
		//debug(d);
		vi v(N);
		REP(i,N) REP(j,N){
			v[j]+=d[i][j];
			v[i]-=d[i][j];
		}
		int f=0;
		REP(i,N) if(v[i]>0)f+=v[i];
		
		cal_min_cost_flow a;
		REP(i,N){
			if(v[i]>0) a.add_edge(s,i+1,v[i],0);
			if(v[i]<0) a.add_edge(i+1,t,-v[i],0);
		}
		REP(i,N) REP(j,N) if(d[i][j]>=2){
			a.add_edge(j+1, i+1, d[i][j]-1,1);
		}
		
		// check connectivity
		{
			int cnt=0;
			vi z(N);
			queue<int> Q;
			Q.push(0);
			while(!Q.empty()){
				int v=Q.front(); Q.pop();
				if(z[v])continue;
				z[v]=1;
				REP(v2,N) if(d[v][v2])Q.push(v2);
			}
			REP(i,N) if(z[i]==0)return -1;
		}
		
		//debug(v);
		//debug(f);		
		int res=a.min_cost_flow(s,t,f);
		if(res==-1)return -1;
		int ans=0;
		REP(i,N) REP(j,N) ans+=d[i][j];
		return ans-res;
  }
}

SRM539Div1HARD(FoxBomb)

| 11:11

本番とおした人のコードを参考に書いた。貪欲的な方法で解ける。

『まずフィールド全体を爆弾で埋める。問題文からフィールドは木構造になっているので、葉のほうから順に取り除き可能な爆弾を取り除いていく。』

言葉で適当にいうとたったこれだけの解法。シンプルかつ実装が簡単で一般性もある、かなり強力な解法だと思う。Editorial見る限り模範解答はdpでこの解法じゃなかったのが少し驚き。

#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 nclr(a) memset((a),-1,sizeof(a))
#define clr(a) memset((a),0,sizeof(a))
#define pb push_back
// BEGIN CUT HERE

#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
// END CUT HERE


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 pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
// BEGIN CUT HERE
typedef long long ll;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
// END CUT HERE


int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

class FoxBomb {
public:
vi xs,ys;
vvi g;
int check[60][60];
int cnt[60][60];

	void put(int x, int y, int v){
		cnt[x][y]+=v;
		REP(r,4){
			for(int k=1;;k++){
				int x2=x+k*dx[r], y2=y+k*dy[r];
				if(g[x2][y2]==0)break;
				cnt[x2][y2]+=v;
			}
		}
	}
	
	bool pullable(int x, int y){
		if(cnt[x][y]==1)return false;
		REP(r,4){
			for(int k=1;;k++){
				int x2=x+k*dx[r], y2=y+k*dy[r];
				if(g[x2][y2]==0)break;
				if(cnt[x2][y2]==1)return false;
			}
		}
		return true;
	}

	void dfs(int x, int y){
		if(g[x][y]==0 || check[x][y]==1)return;
		check[x][y]=1;
		REP(r,4){
			int x2=x+dx[r], y2=y+dy[r];
			dfs(x2,y2);
		}
		xs.pb(x);
		ys.pb(y);
	}
	
	int getMinimumCost(vector <string> grid) {
		clr(check);
		clr(cnt);
		xs.clear(), ys.clear();
		g.clear();
		{
			int n=grid.size();
			int m=grid[0].size();
			g=vvi(n+2, vi(m+2));
			REP(i,n) REP(j,m){
				if(grid[i][j]=='.')g[i+1][j+1]=1;
			}
		}
		pii root;
		REP(i,g.size()) REP(j,g[i].size()){
			if(g[i][j]==1)root=pii(i,j);
		}

		dfs(root.first, root.second);
		int ans=0;
		REP(i,xs.size()){
			put(xs[i], ys[i], 1);
			ans++;
		}
		REP(i,xs.size()){
			if(pullable(xs[i], ys[i])){
				ans--;
				put(xs[i], ys[i], -1);
			}
		}
		
		return ans;
	}

SRM540Div1HARD(ProductQuery)

| 11:02

考え方自体はさほど難しいものではないけど、複数の要素が絡んでいて実装に苦労する。

#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=1000000007;
int N,p;
vi S, T, G, can_zero;

const int MAX_i = 105;
const int MAX_prev = 105;
ll memo_rec[MAX_i][MAX_prev];
ll rec(int i, int prev){
	assert(0<=i && i<MAX_i);
	assert(0<=prev && prev<MAX_prev);
	ll &ret=memo_rec[i][prev];
	if(ret!=-1)return ret;
	ll ans=0;
	if(i==N)return ret=1;
	if(can_zero[i]) ans+=rec(i+1,i+1);
	bool must_zero=false;
	REP(k,S.size()){
		if(T[k]==i && prev<S[k]+1 && G[k]==0)must_zero=true;
	}
	if(!must_zero)ans+=rec(i+1, prev)*( can_zero[i]==1 ? (p-1) : 1 );
	return ret=ans%mod;
}

ll f(){
	can_zero=vi(N,1);
	REP(k,S.size()) if(G[k]!=0){
		for(int i=S[k]; i<=T[k]; i++)can_zero[i]=0;
	}
	nclr(memo_rec);
	ll z1=rec(0,0);
	REP(k,S.size()){
	}
	vi a=vi(N+1,-1);
	ll z2=1;
	int cnt=0;
	REP(i,a.size()) if(a[i]==-1 &&  !can_zero[i]){
		a[i]=1;
		while(true){
			bool change=false;
			REP(k,S.size()) if(G[k]!=0){
				if(a[S[k]]==-1 && a[T[k]+1]!=-1){
					for(int j=1;j<p;j++) if(j*G[k]%p==a[T[k]+1]){
						a[S[k]]=j;
						change=true;
						cnt++;
						break;
					}
				}
				else if(a[S[k]]!=-1 && a[T[k]+1]==-1){
					a[T[k]+1]=a[S[k]]*G[k]%p;
					cnt++;
					change=true;
				}
				else if(a[S[k]]!=-1 && a[T[k]+1]!=-1 && a[S[k]]*G[k]%p!=a[T[k]+1])return 0;
			}
			if(!change)break;
		}
	}
	int cnt2=0;
	REP(i,N) if(can_zero[i]==0)cnt2++;
	assert(cnt2>=cnt);
	REP(k,cnt2-cnt){
		z2=z2*(p-1)%mod;
	}
	//debug(a);
	//debug(z1);debug(z2);
	return z1*z2%mod;
}

class ProductQuery {
public:
	int theInput(int _N, vector <int> Qfrom, vector <int> Qto, vector <int> output) {
		//debug(Qfrom);
		//debug(Qto);
		//debug(output);
		N=_N;
		int ps[2]={2,5};
		ll ans[2];
		REP(ip,2){
			p=ps[ip];
			S=Qfrom;
			T=Qto;
			G.clear();
			REP(i,Qfrom.size()){
				G.pb(output[i]%p);
			}
			ans[ip]=f();
		}
		
		return ans[0]*ans[1]%mod;
	}
	

};

SRM541Div1HARD(XorLife)

| 10:52

時間が2ステップ進む時の様子をみると繰り返し二乗法が使えることが分かる。アイデアが殆ど全ての問題。5倍していくイメージの解法の誘惑が結構強くて正しい解法にたどり着くのに時間がかかってしまう。

#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())

// BEGIN CUT HERE
#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))
// END CUT HERE


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 vector<int> vi;
typedef vector<vi> vvi;
// BEGIN CUT HERE

typedef pair<int,int> pii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
// END CUT HERE

map<pair<vvi,ll>, ll> memo;

ll f(const vvi &field, ll m){
	//debug(m);
	//debug(field);
	pair<vvi,ll> a(field,m);
	if(EXIST(memo,a)){
		return memo[a];
	}
	ll &ret=memo[a];
	if(field.size()==0)return 0;
	if(field[0].size()==0)return 0;

	if(m==0){
		ll cnt=0;
		REP(i,field.size()) REP(j,field[i].size())cnt+=field[i][j];
		//debug(field);
		//debug(cnt);
		return ret=cnt;
	}
	if(m%2==1){
		int xs,ys;
		xs=field.size()+2;
		ys=field[0].size()+2;
		vvi new_field(xs,vi(ys));
		REP(x,xs-2) REP(y,ys-2) if(field[x][y]==1){
			new_field[x][y+1]++;
			new_field[x+1][y]++;
			new_field[x+2][y+1]++;
			new_field[x+1][y+2]++;
			new_field[x+1][y+1]++;
		}
		REP(x,xs) REP(y,ys) new_field[x][y]%=2;
		return ret=f(new_field, m-1);
	}
	else{
		int xs=field.size();
		int ys=field[0].size();
		vvi new_field[2][2];
		REP(i,2) REP(j,2) new_field[i][j]=vvi( (xs+1)/2, vi( (ys+1)/2) );
		REP(x,xs) REP(y,ys) if(field[x][y]){
			new_field[x%2][y%2][x/2][y/2]=1;
		}
		ll ans=0;
		REP(i,2) REP(j,2) ans+=f(new_field[i][j], m/2);
		return ret=ans;
	}
	return 0;
	
}

class XorLife {
public:
	long long countAliveCells(vector <string> _field, int K) {
		memo.clear();
		vvi field(_field.size(), vi(_field[0].size()));
		REP(x,field.size()) REP(y,field[x].size()) if(_field[x][y]=='o')field[x][y]=1;
		//debug(field);
		//debug(K);
		long long ans=f(field,K);
		
		return ans;
	}

SRM544Div1HARD(SplittingFoxes)

| 10:40

行列冪乗タイプの問題。

違う方向を向いているFoxも同等に扱えるのが実装を簡潔にする最大のポイント。

次のような式をノートに書くと分かりやすいかなと思った。

(→, x, y) ⇒
S(→, x+1, y) + L(↑, x, y) + R(↓, x, y)
= S(→, x+1, y) - L(→, y, -x) - R(→, -y, x)

N: 1の和(総数)
X: xの和
Y: yの和
XY: xyの和 として(N,X,Y,XY)を並べたものを考えると
next(N)  = (S-L-R)N
next(X)  = S(x+1) - Ly + Ry = SN + SX + (-L+R)Y
next(Y)  = S(y+1) + Lx - Rx = SN + (L-R)X + SY
next(XY) = S(x+1)y + Lxy + Rxy = SY + (S+L+R)XY

あと、enum{N,X,Y,XY}; って書くと順に0,1,2,3が入るらしい。よく分かってないけど。

#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 S,L,R;

ll mod=1000000007;
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;
	extgcd(a,b, x, y);
	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;}
*/


template <typename T> struct matrix : vector<vector<T > >{
	matrix(int n){
		vector<vector<T> >::clear();
		resize(n, vector<T>(n) );
		REP(i,n) (*this)[i][i]=1;
	}
	matrix(int n, int m){
		vector<vector<T> >::clear();
		resize(n, vector<T>(m) ); 
	}
	matrix<T> operator*(const matrix<T> &b){
		int n1=this->size(), n2=b.size(), n3=b[0].size();
		assert(this->size()==n2);
		matrix<T> ret(n1,n3);
		REP(i,n1) REP(j,n3) REP(k,n2) ret[i][j]=ret[i][j]+(*this)[i][k]*b[k][j];
		return ret;
	}
	matrix<T> pow(ll n){
		int m=this->size();
		assert((*this)[0].size()==m);
		return pow2(matrix<T>(m) ,n);
	}
	matrix<T> pow2(matrix t, ll n){
		if(n==0)return t;
		if(n%2==0)return ((*this)*(*this)).pow2( t, n/2);
		else return ((*this)*(*this)).pow2 ((*this)*t, n/2);
	}
	/*T det(){
		int n=this->size();
		vector<vector<T> >x;
		REP(i,n) x.pb((*this)[i]);
		T h=1;
		REP(i,n){
			FOR(j,i,n){
				if(x[j][i]!=0 && j!=i){
					REP(k,n)swap(x[j][k], x[i][k]);
					h*=-1;
					break;
				}
			}
			if(x[i][i]==0)return 0;
			T v=1/x[i][i];
			h=h*x[i][i];
			FOR(j,i+1,n){
				T v2=v*x[j][i];
				REP(k,n) x[j][k]=x[j][k]-x[i][k]*v2;
			}
		}
		return h;
	}*/
};

class SplittingFoxes {
public:
	int sum(long long n, ll _S, ll _L, ll _R) {
		mint S=_S, L=_L, R=_R;
		matrix<mint> a(4,4);
		enum{N,X,Y,XY};
		a[N][N]=S-L-R;
		
		a[XY][XY]=S+L+R;
		a[XY][Y]=S;
		
		a[X][N]=S;
		a[X][X]=S;
		a[X][Y]=-L+R;
		
		a[Y][Y]=S;
		a[Y][X]=L-R;
		//debug(a);
		//debug(a.pow(n));
		int ans=a.pow(n)[XY][N].value;
		
		return ans;
	}
};

2012-06-12

TCO11WildCardHARD(PermutationBias)

| 17:09

置換の状態数は分割数に一致するが、35番目の分割数が意外と小さく(20000程度)、愚直なdpでも何とかなる事に気付けるかどうかがポイント。計算を工夫しないとTLEしてしまう。このような計算量を把握しにくい解法で解く時は、普段の「要求される計算量→解法を考える」から、「計算速度をとにかく早くする」に発想を切り替えたほうがいい気がしている。この種の問題、あんまり見ないから練習が難しい。

2012-06-01

SRM538Div1HARD(SkewedPerspective )

| 03:22

複雑な感じのdp。ややこしくて、難しそうなので放置していたのを解いた。

とりあえず、この手の問題を解く時に自分なりにポイントだと思ったこと

  1. 頭の中で細部まで無理に詰めようとしない。何となく方針が出来たら、思い切ってとりあえずコーディングを始めた方がうまくいったりする。
  2. 変数の意味をコメントで書く。変数名を長くしすぎない。
  3. 一変数化してメモする。変数をまとめてvector<int>にするとか、long longにまとめるとか。
  4. とりあえずは変数の個数をけちらずに書く。
  5. globalに置く変数の個数を出来るだけ減らすように書いたほうが簡潔になりやすい。『使った個数』ではなく『残りの個数』を割り当てるなど。
  6. 出来るだけ脳内処理をせずに、定義に忠実に書く。
if(b==0 || (x==2 && c==0))

の部分を間違えて、

if(b==0 || x==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;

ll mod=1000000007;
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;}
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;
	extgcd(a,b, x, y);
	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;}

vector<mint> a;
int w;

mint fact(ll n){
	return (n==0 ? 1 : n*fact(n-1));
}

map<vi ,mint> memo;
// x:横幅 , y:縦幅, c:表面部分, n1, 残りの1ブロック, n2:残りの2ブロック, n3:非決定部分, b:直前が黒かどうか。黒なら下げない。
mint rec(int x, int y, int c, int n1, int n2, int n3, int b){
	int gg[7]={x,y,c,n1,n2,n3,b};
	vi g(gg,gg+7);
	if(EXIST(memo,g))return memo[g];
	mint &ret=memo[g];
	
	if(n1<0 || n2<0 || n1+n2*2<2*n3 || y==w+1)return ret=0;
	mint ans=0;
	if(x!=0)ans+=a[c];
	ans+=rec(x+1, y, c+1, n1-1, n2, n3, 0);
	ans+=rec(x+2, y, c, n1, n2-1, n3, 1);
	if(b==0 || (x==2 && c==0)){
		assert(x!=0);
		ans+=rec(x+1, y+1, c, n1-(x-1)%2, n2-1, n3+(x-1)/2, 1);
	}
	
	return ret=ans;
}


class SkewedPerspective {
public:
	int countThem(vector <int> cubes, int B, int _w) {
		memo.clear();
		w=_w;
		int tot=0;
		REP(i,cubes.size())tot+=cubes[i];
		a=vector<mint>(60);
		a[0]=1;
		REP(i,cubes.size()){
			vector<mint> a2(a.size());
			REP(j,a.size()) for(int k=j-cubes[i]; k<=j; k++) if(k>=0) a2[j]+=a[k]/fact(j-k);
			a=a2;
		}
		REP(i,a.size())a[i]*=fact(i);
		//debug(cubes);
		//debug(B);debug(w);
		int ans=rec(0,1,0,tot,B,0,1).value;
		
		return ans;
	}
};