Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2011/01/27

「5×5のマス目に6個の○を次の条件を満たすように全部書く」を解いてみた

00:03

404 Blog Not Found:Math - 5×5のマス目に6個の○を次の条件を満たすように全部書く

5×5のマス目に6個の○を次の条件を満たすように書きます。

条件:各行・各列に少なくとも1個は○を書く。同じマスには2個以上の○を書くことはできない。

このとき、6個の○を書く方法は全部で何通りありますか。

RSS を眺めているときにこの記事を見つけて dankogai ならきっと...!と思って「続きを読む」を押したら総当り6重 for ループでがっかりしたので,変数を可変にして自分で書いてみた.combination 関数をちゃんと書いてないのででかい数を渡すとオーバーフローします.

典型的な DP ですよね.20分ぐらいで書けました.間違ってたら指摘お願いします.

弾さんも書いている通り総当りでも 25_P_6 = 127,512,000 なんで TopCoder でもなければ総当たったほうが楽で,時と場合と目的に依ってはそれもベストなコードの1つですね(TopCoderだとTLEする).

/Users/yuyarin% time ./a.out       
n=5 m=5 c=6
answer: 4200
./a.out  0.00s user 0.00s system 18% cpu 0.012 total
/Users/yuyarin% time ./a.out 7 7 9 
n=7 m=7 c=9
answer: 13003620
./a.out 7 7 9  0.00s user 0.00s system 17% cpu 0.013 total
/Users/yuyarin% time ./a.out 9 7 13
n=9 m=7 c=13
answer: 1016446631327
./a.out 9 7 13  0.00s user 0.00s system 31% cpu 0.008 total

どっかでオーバーフローしてるかもしれない.

イカソース


#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

long long int combination(long long int n, long long int m)
{
	if(n<m)
		return 0;
	long long int r = 1;
	// warning! r may overflow with large n and m
	for(int i=0; i<m; i++)
		r *= n-i;
	for(int i=0; i<m; i++)
		r /= i+1;
	return r;
}

int main(int argc, char *argv[])
{
	int n=5, m=5, c=6;
	if(argc==4)
	{
		n = atoi(argv[1]);
		m = atoi(argv[2]);
		c = atoi(argv[3]);
		if(n<1||m<1||c<1)
		{
			cerr << "usage: ./a.out n m c (n>0,m>0,c>0)" << endl;
			return 1;
		}
	}
	
	cout << "n=" << n << " m=" << m << " c=" << c << endl;
	
	vector<vector<long long int> > dp(n+1, vector<long long int>(m+1, 0));
	
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++)
	{
		dp[i][j] = combination(i*j, c);
		for(int h=0; h<=i; h++) for(int v=0; v<=j; v++)
		{
			if(h==0&&v==0) continue;
			dp[i][j] -= combination(i,h)*combination(j,v)*dp[i-h][j-v];
		}
	}
	
	cout << "answer: " << dp[n][m] << endl;
	
	return 0;
}

DeandreDeandre 2011/07/22 14:58 This site is like a classroom, eecxpt I don't hate it. lol

zxvhpdyvzazxvhpdyvza 2011/07/23 22:36 9w6OE2 , [url=http://enhrpdbgcmdg.com/]enhrpdbgcmdg[/url], [link=http://lpzrrvhelrkj.com/]lpzrrvhelrkj[/link], http://jokklpgtygzh.com/

zevawpmjzevawpmj 2011/07/24 21:51 YPOmgY <a href="http://pcdropmnzimz.com/">pcdropmnzimz</a>

bacbrkenswbacbrkensw 2011/07/26 01:48 df0FdI , [url=http://ttrsfridzjtd.com/]ttrsfridzjtd[/url], [link=http://utvyqfhdxaie.com/]utvyqfhdxaie[/link], http://kytqpktiamcy.com/

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/yuyarin/20110127