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

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

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

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

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

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

弾さんも書いている通り総当りでも 25_P_6 = 127,512,000 なんで TopCoder でもなければ総当たったほうが楽で，時と場合と目的に依ってはそれもベストなコードの１つですね（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

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

イカソース

http://www.topcoder.com/stat?c=problem_statement&pm=10920&rd=14236

問題

重さのある羊がたくさんいる．これを重量の容量がある船に乗せて川を渡らせる．乗せる羊の選び方は，残り容量以下で重い方から選んでいく．与えられた回数以下で全ての羊を渡らせるときに，船の最小の容量を求める．

アプローチ

ぱっと見，何の変哲もない二分探索の問題であるが落とし穴がある．

ある容量で回数内に運べるからといって，それより大きい容量で運べるとは限らないからである．chokudai 氏がテストケースを挙げている

すげえｗｗｗどうやって見つけたんだｗｗｗ［出典］

容量 159 で成立するけど 160 では成立しないケースのようである．

というわけで二分探索で求めた後，前を 2000 個ほど探索している．この 2000 という値には全く根拠がないのだが（しいて言えば羊の重さの上限），本当にこれでいいんだろうか・・・？

※追記：wata さんによれば，(羊の重さの合計)/(運べる最大回数)から(羊の重さの合計)/(運べる最大回数)+(羊の最大の重さ)までに必ず解があると証明できるとのこと．

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#include <set>
#include <algorithm>
#include <numeric>

using namespace std;

#define sz(a) int((a).size())
#define All(a)  (a).begin(),(a).end()

#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)
#define Each(i,c)     for(typeof((c).begin()) i=(c).begin();i!=(c).end();++i)

bool judge(multiset<int> s, int c, int maxRuns)
{
	int runs = 0;
	multiset<int>::iterator it;
	while(sz(s))
	{
		int cc = c;
		while(cc>0&&sz(s))
		{
			it = s.upper_bound(cc);
			if(it==s.begin()) break;
			it--;
			cc -= *it;
			s.erase(it);
		}
		if(++runs>maxRuns)
			return false;
	}
	
	return true;
}

int minCapacity(int numSheep, int maxRuns, vector <string> part1, vector <string> part2, vector <string> part3, vector <string> part4)
{
	multiset<int> msi;
	string str;
	int n;
	Each(s,part1) str+=*s;
	Each(s,part2) str+=*s;
	Each(s,part3) str+=*s;
	Each(s,part4) str+=*s;
	istringstream iss(str); while(iss>>n) msi.insert(n);
	int sum = accumulate(All(msi),0);
	int max = *max_element(All(msi));
	
	for(int capasity=sum/maxRuns; capasity<=sum/maxRuns+max+1; capasity++)
		if(judge(msi,capasity,maxRuns)) return capasity;
	return -1;
/*
	// binary search version
	int min = *max_element(All(msi));
	int max = accumulate(All(msi),0);
	
	while(max-min>1)
	{
		int mid = (min+max)/2;
		if(bs(msi,mid,maxRuns))
			max = mid;
		else
			min = mid;
	}
	
	For(c,min-2000,max)
		if(bs(msi,c,maxRuns)) return c;
	
	return max;
*/
}

http://www.topcoder.com/stat?c=problem_solution&rm=305892&rd=14236&pm=11037&cr=22851423

問題

選挙において投票者に最小限の賄賂を渡して勝つようにする．n 人の投票者がいて，それぞれ影響度 influence と抵抗度 resistance が存在する．i 番目の人に賄賂を渡すと，j 番目の人の抵抗度が influence[i]/2^|i-j| だけ減る．全員の抵抗度が 0 以下になれば賄賂は成功する．賄賂が成功する渡し方のうち，賄賂を渡す人数が最小になる人数を返す．できなければ失敗として -1 を返す．

アプローチ

一見すると O(n*2^n) な複数ナップサック問題のように見えるが，影響度の値が 500 以下，つまり 2^9 より小さいので両隣 8 人目まで考慮すればいいことが分かる．これで 2^n の部分が 2^17 の定数で押さえられるので O(n)．で解くことができる（定数項はそれなりに大きいので注意）．

両隣 8 人を含めた計 17 人への賄賂を 17-bit で表現することができる．DP の問題の分割は投票者の人数で行うことができる．つまり０人，１人，と増やしていく．i 人目の抵抗度を 0 にするには i-8 人目から i+8 人目までの影響度を考慮すればいい．抵抗度を 0 にできるパターンの中から最も賄賂を渡す人数が少ないパターンを記録している． i+1 人目を計算するには i 人目のビットパターンのうち上位 16-bit だけ分かればよいので，配列に保存するのは 16-bit 分で良いことが分かる． n 人目まで繰り返していき，最小の値（人数）を選ぶ．

配列のサイズが大きいので int では allocate できない．short を使う．

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#include <cmath>

using namespace std;

#define sz(a) int((a).size())
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

short dp[51][1<<16];

int minBribes(vector <int> influence, vector <int> resistance)
{
	int n = sz(influence);
	int INF = 100;
	
	Rep(i,n+1) Rep(j,1<<16)
		dp[i][j] = i ? INF : __builtin_popcount(j);
	
	Rep(i,n) Rep(mask,1<<17)
	{
		int sum = 0;
		for(int j=i-8,k=0; j<=i+8; j++,k++)
			if((mask&(1<<k)) && 0<=j&&j<n)
				sum += influence[j]>>abs(j-i);
		if(sum>=resistance[i])
			dp[i+1][mask>>1] = min(
				(int)dp[i+1][mask>>1],
				(int)dp[i][mask%(1<<16)]+mask/(1<<16)
			);
	}
	int r = INF;
	Rep(j,1<<16)
		r = min(r,(int)dp[n][j]);
	
	return r>n ? -1 : r;
}

http://www.topcoder.com/stat?c=problem_solution&rm=305892&rd=14236&pm=11023&cr=22851423

問題

与えられた数より小さい分母を持つ分数の中から，与えられた 1 より小さい小数点以下６桁の小数を最もよく近似する分数を見つける問題．

アプローチ

分母を小さい値から固定していき，分子を近似対象の小数と分母の掛け算で決定．誤差があるので分子は floor と ceil の両方を計算する．

本番では Failed System Test だった．理由は作った分数の小数表現を sprintf("%.8f") で作ったから．sprintf は指定桁数以下の値を四捨五入してしまうので小数点以下７桁目以降が 995 より大きいテストケースだと失敗する．"%.10f" で失敗するケースは無かった模様．

Test Case: 138
Args: {1000, "0.812983"}
Expected: "313/385 has 6 exact digits"
Received: "526/647 has 7 exact digits"

こうした誤差を最初から出さないためには 10^6 倍して整数として計算するのがよい．問題はこの方法でも int の範囲内で計算できるように設計されているようだ．

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

inline int toi(string s){int v; istringstream iss(s);iss>>v;return v;}
template<class T> inline string tos(T x){ostringstream oss;oss<<x;return oss.str();}

#define For(i,a,b)    for(int i=(a);i<(b);++i)

string findFraction(int maxDen, string number)
{
	int ml = 0;
	int mn = 0;
	int md = 0;
	int num = toi(number.c_str()+2);
	
	For(d,1,maxDen+1) For(dd,0,2)
	{
		int n = num*d;
		n -= n%1000000;
		n += dd*1000000;
		int x = n/d;
		int y = 100000;
		int l = 1;
		For(i,0,6)
		{
			if(x/y!=num/y) break;
			l++;
			y /= 10;
		}
		if(l>ml)
		{
			mn = n/1000000;
			md = d;
			ml = l;
		}
	}
	
	char s[64];
	sprintf(s, "%d/%d has %d exact digits", mn, md, ml);
	
	return string(s);
}

SRM 483 Div1 Room 4

久々の SRM．

250 pt. を取れていると思ったらまさかの Failed System Test.

500 pt. を開いて他制約ナップサック（ナップサックが複数並列して存在するような問題）だと思い解き方に悩み，解けずじまい．

0 point で rating down．アルゴリズムの勉強をちゃんとできないまま挑んでいるので，次あたりそろそろヤバそう．

Room では target, vlad89 による 900 pt. 虐殺タイムが始まる．結果，意外と 250 も落ちている人が多かった．

Petr がまさかの１問も解けていなかったせいで，今週は雨です．

http://golf.shinh.org/p.rb?Puyo+Puyo

初めて出題した golf の問題なので解説を書いてみようと思う．

問題

ぷよぷよのスクリーンが与えられるので連鎖後のスクリーンの状態と連鎖数を表示する．

ぷよは r, g, b, y, p で表示される．もちろん赤，緑，青，黄，紫に対応している．

スクリーンのサイズはぷよぷよの通り横6縦13である．

本来のぷよぷよでは13段目はスクリーン外で見えない＆消えないという性質を持つので，幽霊連鎖というものが可能だが，今回はこの仕様は省いた．

http://www.topcoder.com/stat?c=problem_statement&pm=10929&rd=14278

問題

横 W 縦 H の芝生をダイアモンドカッターが切っていく．カッターの初期位置と，移動方向のプログラムが与えられたときに，芝生が何分割されているかを答える．

アプローチ

ある位置の芝生の左が切れているかどうかのフラグと上が切れているかどうかのフラグを用意しておき，プログラムを走らせて切っていき，最後に領域を数える．

領域を数えるのは再帰（スタック，深さ優先）だと最悪 10^6 になるのでオーバーフローする．queue を使って幅優先探索を行う．

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <queue>

using namespace std;

typedef pair<int,int> PII;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

bool cutu[1024][1024];
bool cutl[1024][1024];
bool glass[1024][1024];

queue<PII> q;

int pieces(int W, int H, int startx, int starty, vector <string> program)
{
	Rep(j,H+1) Rep(i,W+1)
		cutu[j][i] = cutl[j][i] = glass[j][i] = false;
	Rep(i,W+1)
		cutu[0][i] = cutu[H][i] = true;
	Rep(j,H+1)
		cutl[j][0] = cutl[j][W] = true;
	
	int x = startx;
	int y = starty;
	
	Rep(pp,sz(program)) Rep(p,sz(program[pp]))
	{
		switch(program[pp][p])
		{
		case 'U':
			cutl[--y][x] = true;
			break;
		case 'D':
			cutl[y++][x] = true;
			break;
		case 'L':
			cutu[y][--x] = true;
			break;
		case 'R':
			cutu[y][x++] = true;
			break;
		}
	}
	
	int c = 0;
	Rep(j,H) Rep(i,W) if(!glass[j][i])
	{
		c++;
		q.push(mp(i,j));
		while(!q.empty())
		{
			PII co = q.front(); q.pop();
			int x = co.first;
			int y = co.second;
			if(glass[y][x])
				continue;
			glass[y][x] = true;
			if(!cutu[y][x])   q.push(mp(x,y-1));
			if(!cutu[y+1][x]) q.push(mp(x,y+1));
			if(!cutl[y][x])   q.push(mp(x-1,y));
			if(!cutl[y][x+1]) q.push(mp(x+1,y));
		}
	}
	
	return c;
}

http://www.topcoder.com/stat?c=problem_statement&pm=10927&rd=14278

問題

ギターの弦を押さえる時にどのコードになるのかを求める問題．６つの弦のどのフレットを押さえるのかが数値で与えられる．特に 0 なら開放弦，-1 なら弾かない，である．どの音の Major か Minor なのかを判定する．

アプローチ

全探索でも全く問題ないが，コードが汚くなる．

とりあえず押さえる弦を配列に突っ込んで 12 の剰余を取って unique をかけて正規化する(*1)．ここで要素が 3 つでなければ終了．3 つの場合，その後ろにそれぞれ 12 を足した値を追加しておくと(*2)後のコード判定がすっきりして楽になる(*3)．

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

typedef vector<int> VI;

#define pb push_back
#define sz(a) int((a).size())

#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

#define Unique(v) \
	sort((v).begin(),(v).end());\
	v.resize(unique((v).begin(),(v).end())-(v).begin());
	
int s[6] = {4,9,2,7,11,4};
string name[12] = {"C","C#","D","D#","E","F","F#","G","G#","A","A#","B"};

string classify(vector<int> chord)
{
	VI c;
	Rep(i,6) if(chord[i]>=0)
		c.pb((chord[i]+s[i])%12);
	// (*1)
	Unique(c);
	
	if(sz(c)!=3)
		return "";
	
	// (*2)
	Rep(i,3)
		c.pb(c[i]+12);
	
	// (*3)
	Rep(i,3)
	{
		if(c[i+1]-c[i]==4 && c[i+2]-c[i+1]==3)
			return name[c[i]]+" Major";
		if(c[i+1]-c[i]==3 && c[i+2]-c[i+1]==4)
			return name[c[i]]+" Minor";
	}
	
	return "";
}

http://www.topcoder.com/stat?c=problem_statement&pm=10948&rd=14278

問題

二次元の表の一番左の列と一番上の行の値が与えられている．あるセルの値は下と右下と右のセルの和になっている．表の一番右下の値を求める．

アプローチ

特に工夫は必要なし．

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

#define sz(a) int((a).size())

using namespace std;

int m[10][10];

int getCorner(vector <int> leftColumn, vector <int> topRow)
{
	int nl = leftColumn;
	int nt = topRow;
	
	Rep(j,nl)
		m[j][0] = leftColumn[j];
	Rep(i,nt)
		m[0][i] = topRow[i];
	
	For(j,1,nl) For(i,1,nt)
		m[j][i] = m[j-1][i-1] - m[j][i-1] - m[j-1][i];
	
	return m[nl-1][nt-1];
}