Hatena::Grouptopcoder

hirosegolf@競技プログラミング

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

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/hirosegolf/20120706