yuyarinのtopcoder記

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

00:03

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

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

イカソース

続きを読む

SRM 483 Div1

SRM 483 | 00:55

SRM 483 Div1 Room 4

久々の SRM．

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

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

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

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

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

SRM 483 BestApproximationDiv1

★★☆☆☆, SRM 483 | 00:55

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 Bribes

★★★☆☆, SRM 483, dynamic programming | 00:55

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

SRM 483 Sheep

★★★★☆, SRM 483, binary search | 03:36

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

Anarchy Golf 339. Puyo Puyo

golf, anagol | 00:10

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

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

問題

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

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

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

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

続きを読む

TopCoder Open 2010 Algorithm Qualification Round 3 SumRectangle

★☆☆☆☆, TCO 2010 | 16:31

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

TopCoder Open 2010 Algorithm Qualification Round 3 WhatsThisChord

★★☆☆☆, TCO 2010 | 16:31

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

TopCoder Open 2010 Algorithm Qualification Round 3

★★★☆☆, TCO 2010, 2D matrix | 16:31

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

Google Code Jam 2010 Round 1A C. Number Game

★★★☆☆, GCJ 2010, Fibonacci number, memory limit | 18:46

問題

黒板に A, B ２つの数字がかかれていて，２人のプレイヤーこの数字を使ってゲームを行う． プレイヤーは交互に数字 A を A-k*B に置き換えるか，数字 B を B-k*A に置き換える操作をする． k は正数である．これを交互に行っていき，数字を 0 以下にしてしまった方が負けである．このゲームの初期値に対する先攻の必勝パターンの数を範囲 A∈[A1,A2] B∈[B1,B2] において求める．

アプローチ（再帰）

とりあえず再帰を使って単純に実装してみる．

using namespace std;
typedef long long ll;

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

// 必ず a>=b
// p==true: player が先攻
// 先攻のプレイヤーが必勝の場合は true を返す
bool rec(int a, int b, bool p)
{
	if(b<=0) return !p;
	For(k,1,(a-1)/b+1)
		if(rec(max(a-k*b,b),min(a-k*b,b),!p)==p) return p;
	return !p;
}

int main(void)
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int A1, A2, B1, B2;
		cin >> A1 >> A2 >> B1 >> B2;
		ll r = 0;
		For(a,A1,A2+1) For(b,B1,B2+1)
			if(rec(max(a,b),min(a,b),true)) r++;
		cout << "Case #" << t+1 << ": " << r << endl;
	}
}

sample は通るけど最大のケース，たとえば (A, B) = (1000000,1) だとスタックが足りなくなって落ちる*1ことや，そもそも計算が終わらないだろうことが容易に想像がつく．また，1,000,000 x 1,000,000 の配列を用意しておくのもメモリサイズの制約上厳しい．VSIZE 3728GB って．．．

なので数学的に解を出す方向で考えてみる．

アプローチ（数学）

ひとまず 50x50 ぐらいで出力してみると，傾向があるのがわかる．

↓A B→
 *************************************************
*  ***********************************************
*   **********************************************
**    ********************************************
***     ******************************************
***      *****************************************
****       ***************************************
****        **************************************
*****         ************************************
******          **********************************
******           *********************************
*******            *******************************
********             *****************************
********              ****************************
*********               **************************
*********                *************************
**********                 ***********************
***********                  *********************
***********                   ********************
************                    ******************
************                     *****************
*************                      ***************
**************                       *************
**************                        ************
***************                         **********
****************                          ********
****************                           *******
*****************                            *****
*****************                             ****
******************                              **
*******************                               
*******************                               
********************                              
*********************                             
*********************                             
**********************                            
**********************                            
***********************                           
************************                          
************************                          
*************************                         
*************************                         
**************************                        
***************************                       
***************************                       
****************************                      
*****************************                     
*****************************                     
******************************                    
******************************                    

A > αB の場合と B > αA の場合に必勝パターンであることが分かる．このαを求める．

A, B は対称性があるので A > B の場合のみを考えれば良い（A==B の場合は先手が必ず負ける）．

まず A >= 2B の場合に必勝パターンであることは簡単にわかる．が，よく見ると傾きは 2 より若干小さい．(11,6) -> A:(5,6) -> B:(5,1) -> A(1,1) -> B:(1,0) と A < 2B でも A が必ず勝てる組が存在する．A >= 2B の場合に必勝パターンであるということは先に選択肢を持った方が必ず勝つということである．

なのでどちらも選択肢が 2 つ以上持てないギリギリのパターンを考えると，(1,1) <- (2,1) <- (3,2) <- (5,3) <- (8,5) <- ... という組の列になる．この列はフィボナッチ数列になっている．このとき A と B の比はフィボナッチ数列の隣接項の比，黄金比 Φ=(sqrt(5.0)+1)/2 ≒ 1.6 である．よって A > ΦB であれば必勝パターンであることがわかる．

B をある値 b に固定したときに A > Φb であればよい．[A1, A2] でこのようになる A の個数は　max(0,A2-max(A1,Φb)+1) である．これを b∈[B1, B2] の範囲で調べた後，A, B を反対にした場合の数を調べれば良い．

ソースコード

答えとなる数値は最大で 1M x 1M であるから int だとオーバーフローするので long long を使用する．

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

typedef long long ll;

using namespace std;

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

double golden = (sqrt(5.0)+1)/2;

ll solve(int A1, int A2, int B1, int B2)
{
	ll r = 0;
	For(b,B1,B2+1)
		r += max(0,A2-max(A1,int(b*golden)+1)+1);
	return r;
}

int main(int argc, char* argv[])
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int A1, A2, B1, B2;
		cin >> A1 >> A2 >> B1 >> B2;
		ll r = solve(A1, A2, B1, B2) + solve(B1, B2, A1, A2);
		cout << "Case #" << t+1 << ": " << r << endl;
	}
	
	return 0;
}