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

2012-04-04

SRM469Div1練習

| 22:18

250: 211.25

500: 232.12

1000: Opened

1000の問題文を読んでる途中で実は凄い眠いことに気がついた。やはり500を解くのが遅い。

2012-03-29

SRM470Div1練習

| 14:25

250: 134.64

500: 264.47

1000: Opened

250に時間がかかりすぎた。複数の方針があるので、それで迷ったのも良くなかった。迷わずbit dp一本でやるべきだった。500、もうすこし早く解きたいけど、こればっかりは慣れないことには仕方ないかな。

2012-03-17

SRM476Div1練習

| 13:31

250: 180.57

550: Opened

1000: Opened

久しぶりにSRMがあるので、感覚を取り戻すためにも練習。SRM250は、for(int v=n;v--;v>=0)というミスをして、再提出した。

550は、36人もいたら無理じゃない?とおもってた。

1000は問題文よく分からなさ過ぎて、諦めた。

550のEditorial見てみた。「友達最大15人?36人だろ。15とかどこから出てきた?」とか思ったら、between 1 and 36 "characters"に気づいて衝撃を受けた。こんなのありかよ。今までに無いパターンの罠だった。

2012-02-10

SRM479Div1練習

22:35

250: 182.74

500: Opened

1000: Opened

問題文を読むのがとにかく大変だった。easyを解くのに15分、HARDの問題文を読むのに15分で、それだけでhardを考える時間が殆ど無くなってしまう。500を読むのにも時間がかかって、駄目な感じだった。長文対策を何か考えたほうがいいかもしれない。長文の問題のときは、取り組む問題数が多いとそれだけ不利なので、Mediumを開いて長文だった場合は、最後までhardに取り組むことにするとか。

SRM480Div1練習

| 12:09

0点

あまりにも駄目すぎたので途中でやめた。EASYの実装量が多すぎて死んだ。今まではEasyだけは解くつもりだったけど、大変な実装問題のときは今度からはEasyは飛ばすことにする。

追記:Easyの実装で苦労した原因は変数名が明快でない割りに長すぎたのも原因にありそう。いい変数名が思いつかないときは一文字か二文字ぐらいの短い変数名を選ぶべき。Easyが落ちた原因は、continueと書くべき場所でbreakと書いてしまったことだった。

この手のミスは前にもあったのでなんらかの対策を採るべき。一番着実なのはsubmitしてから、見直すことだろうか。continueをbreakと書くミスは、pretestを通りやすいので気をつける。

参加環境メモ

10:13

色々メモ。

準備してあるライブラリ

Ahocorasick

extgcd, modの計算。行列の計算。

最大流、RMQ

SRMで今とっている戦略

Easy解く。

HARD開く。残り時間30~45分ぐらいまで粘って解けそうなら解く。

将来的にはHARD->Medium->Easyの順番に切り替える予定。

Medium、HARDを解くときはConstrainとサンプルを必ず慎重にチェックすることにしている。

問題文誤解は致命傷になりうると考えて。

デバッグの手間も考えて、配列はメモ化再帰のときぐらいしか使っていない。

殆どvectorですませているが、稀に実行時間がネック。

Codeforcesの時間配分は適当。

EditorはSciTEを使用。F5キーでコンパイル+実行。

スクリプトを書いてコーディング環境の改善をしたいが、面倒でまだ。

メモ化再帰は、コードを自動生成するためのjavascriptコードを使用。

dpはずっとメモ化再帰にこだわって書いていたが、あまりこだわらないようにする。

SRM Codeprocessorテンプレ

#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

// BEGIN CUT HERE
typedef long long ll;
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 $CLASSNAME$ {
public:
  $RC$ $METHODNAME$($METHODPARMS$) {
    $RC$ ans;

    return ans;
  }

  $TESTCODE$
};

// BEGIN CUT HERE
int main() {
  $CLASSNAME$ ___test;
  ___test.run_test(-1);
}
// END CUT HERE