Hatena::Grouptopcoder

hirosegolf@競技プログラミング

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