Hatena::Grouptopcoder

yuyarinのtopcoder記

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

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

2010/05/27

Google Code Jam 2010 Round 1A C. Number Game

| 18:46

問題

黒板に A, B 2つの数字がかかれていて,2人のプレイヤーこの数字を使ってゲームを行う. プレイヤーは交互に数字 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 って...

http://www.yuyarin.net/screenshot/20100527152740.png

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

アプローチ(数学)

ひとまず 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;
}

*1Mac OS X ではデフォルトで 8192 KB なので 10 万回ぐらいめの再帰で溢れてしまう.

VadimVadim2012/07/09 23:30Articles like this are an example of quick, hlepful answers.

qjbrhhqjbrhh2012/07/10 15:49kSuNdQ <a href="http://mdjoejftmbvz.com/">mdjoejftmbvz</a>

pqzkpfjtrpqzkpfjtr2012/07/10 21:46qQr9EH , [url=http://fhvkqwxahzhs.com/]fhvkqwxahzhs[/url], [link=http://mdchxyyvtvey.com/]mdchxyyvtvey[/link], http://rqniilnhuwie.com/

oidakxcccinoidakxcccin2012/07/12 12:07Jpayqp <a href="http://jyiazemeadxh.com/">jyiazemeadxh</a>

whmpyvpwhmpyvp2012/07/12 17:36VAQd8L , [url=http://gqopwfgotuey.com/]gqopwfgotuey[/url], [link=http://lfdyxzapnxeq.com/]lfdyxzapnxeq[/link], http://kqvfxprmucse.com/

2010/05/24

Google Code Jam 2010 Round 1A B. Make it Smooth

| 16:01

http://code.google.com/codejam/contest/dashboard?c=544101#s=p1

解き方がわからなかった問題に再チャレンジ.

問題

最長 100 個の [0,255] の値(文字)が入った配列(文字列)が与えられる.隣り合う要素の差が M 以内であればこの文字列は smooth であるという.文字列に対して削除,置換,挿入の3操作が可能である.削除のコストは D で与えられ,置換のコストは置換前後の数値の差で定義される.挿入のコストは1要素につき I で与えられる.

このとき与えられた文字列を smooth にするために必要なコストの最小値を求める.

アプローチ

与えられた文字列に対してレーベンシュタイン距離の最小となるような文字列を作る操作を求める問題と等価である.

当たり前だけど,各文字を適当に固定して分岐して行く方法だと 255^100 以上の計算量になる.

と考えて実はこれやっぱりまさに典型的に DP で解けるのではないかと気付く.

(100 文字 + 頭 1)×(255 値)の配列 dp[101][256] を用意して,コストを代入して行く. dp[i][j] には i-1 番目の文字が j で i 番目の文字を決める直前のコストを代入する.

dp[0][j] は 0 で,他は十分大きな値にする(*1).INT_MAX を使ってしまうとコストを足したときに簡単に integer overflow を起こすので適度に大きくする.

前の文字 v[i-1] が j に決まったときに v[i] をある値 k に決めるコストを求めていき,k に決めた操作の中でコストが一番小さいものを取る.

これを繰り返して最後に N 文字目のコストで一番小さいものをとる(*2).

削除

v[i] を削除したときの累積コストは dp[i][j]+D である(*3).

変更

v[i] を文字 k に変更したときの累積コストは dp[i][j]+abs(v[i]-k) である(*4).ただし変更は M 以内に収まるような場合のみを行う.

挿入

j → k をつなぐ挿入を行うコストは I*((abs(k-j)-1)/M+1) である.

ここで気をつけなくてはいけないのが,v[i] の前,つまり v[i-1]=j → v[i]=k について挿入操作を行うのではなく,v[i] の後に行うということである.v[i]=j の後に,最後の文字が k になるように挿入を行うと, v[i+1] はあたかも v[i]=k に見える.

ポイントはこの挿入の操作は削除,変更を行ってコストを決めた後の v[i] に対して行うということである.

これを考慮しないと,値の変更・削除を行ってからその間に挿入を行う方がコストが安いケースに対応出来ない.

ここでハマった.

なので累積コストは dp[i][j]+I*((abs(k-j)-1)/M+1) ではなく dp[i+1][j]+I*((abs(k-j)-1)/M+1) とし,削除と挿入の後にコストの改善を行わなくてはならない.

ソースコード

以上のことをまとめるとこういうコードになる.

  • 挿入のところの if(k!=j) が必要ないので削除(2010/05/27 10:07)
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

typedef vector<int> VI;

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

// 128 >= 100 chars + 1
// 256 = (0..255)
int dp[128][256];

int solve(int D, int I, int M, int N, VI &v)
{
	// initialization (*1)
	Rep(i,N+1) Rep(j,256) dp[i][j] = 10000000;
	Rep(j,256) dp[0][j] = 0;
	
	Rep(i,N)
	{
		//delete v[i] (*3)
		Rep(j,256)
			MN(dp[i+1][j], dp[i][j]+D);

		// modify v[i]=j to k (*4)
		Rep(j,256)
			Rep(k,256)
				if(abs(j-k)<=M)
					MN(dp[i+1][k], dp[i][j]+abs(v[i]-k));

		// insert chars after v[i] = j
		// the last inserted char is k (*5)
		if(M>0)
			Rep(j,256)
				Rep(k,256)
					MN(dp[i+1][k], dp[i+1][j]+I*((abs(j-k)-1)/M+1));
	}
	
	// (*2)
	int r = INT_MAX;
	Rep(j,256)
		MN(r,dp[N][j]);
	
	return r;
}

int main(int argc, char* argv[])
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int D, I, M, N;
		cin >> D >> I >> M >> N;
		VI v(N);
		Rep(n,N)
			cin >> v[n];
		int r = solve(D, I, M, N, v);
		cout << "Case #" << t+1 << ": " << r << endl;
	}
	
	return 0;
}

Google Code Jam 2010 Round 1C C. Making Chess Boards

| 11:40

「多分解けると思う」とか書いたので解いてみた.1時間かからなかったので B で試行錯誤せずにこっちを先に解けばよかったと思う.

問題

各マスが白か黒かで塗られた板が与えられるのでそこからチェスボード(市松模様の正方形)を切り出していく問題.切り取れるサイズが大きい順,次に上に位置する順,次に左に位置する順,で切り取っていき,切り取ることができたチェスボードのサイズと個数を求める.

結果

単純な実装をしたけど large input に対しても1秒以内で答えが出た.

アプローチ

列方向を(右向き正)を x, i 軸とする.行方向(下向き正)を y, j 軸とする.

とりあえず hex で渡されたデータを bool に変換する(*1).

以下,したのようなデータを例にする.

 01234567→ x, i
0□■■□■□■■
1■□■■□■■■
2□■■□■□□□
3□■■■□■□■
4■□□□■□■□
5■□■■□■□■
6□■■□■□■□
7■■□□■□□■
↓ y, j

答えは

4 1 (3,3)
3 1 (3,0)
2 3 (0,0), (0,3), (0,5)
1 27

まずあるマスが x, y 方向に,市松模様がこれまでいくつつづいているのかを調べる(*2).配列を mx, my とすると,こんなふうな結果になる.

mx[8][8]
[1][2][1][2][3][4][5][1]
[1][2][3][1][2][3][1][1]
[1][2][1][2][3][4][1][1]
[1][2][1][1][2][3][4][5]
[1][2][1][1][2][3][4][5]
[1][2][3][1][2][3][4][5]
[1][2][1][2][3][4][5][6]
[1][1][2][1][2][3][1][2]

my[8][8]
[1][1][1][1][1][1][1][1]
[2][2][1][2][2][2][1][1]
[3][3][1][3][3][3][2][2]
[1][1][1][4][4][4][1][3]
[2][2][2][5][5][5][2][4]
[1][1][3][6][6][6][3][5]
[2][2][1][7][7][7][4][6]
[3][1][2][1][1][1][5][7]

大きい順に求めるので最大のサイズ,つまりボードの短い辺のサイズから見て行く(*3).この例の場合 8 だが,切り取れるチェスボードのサイズは 4 なので s=4 とする.

あるマス (i, j) に着目したときにそれがサイズ s のチェスボードになっているか判定する.上・左から切り取るので左上から見ていくようにループを回す.(i, j) = (3, 3) を例とする.

(i, j) から y 方向にサイズ s だけ市松模様になっている条件は

my[j+s-1][i] - my[j][i] == s-1

である.市松模様が続いていれば my の値は 1 ずつ増えていくので最初のマス (i,j) と最後のマス (i, j+s-1) の my の差が s-1 になっていなければならない.逆に s-1 より小さい場合は途中で市松模様が切れていることがわかる(*4).

my[8][8]
 1  1  1  1  1  1  1  1 
 2  2  1  2  2  2  1  1 
 3  3  1  3  3  3  2  2 
 1  1  1 (4) 4  4  1  3 
 2  2  2  5  5  5  2  4 
 1  1  3  6  6  6  3  5 
 2  2  1 [7] 7  7  4  6 
 3  1  2  1  1  1  5  7

この例では (3, 3) は (4),(3, 3+s-1) = (3, 6) は [7] であるので条件を満たす.(3, 7) は 1 なので市松模様が切れていることが分かる.なので (3, 3) からサイズ 5 のチェスボードは切り取れない.

次に [j,j+s-1] のそれぞれの行について x 方向に市松模様が続いているか見て行く(*5).すべての行について同様の条件が成り立てば,チェスボードになっていると判定できる(*6).

mx[8][8]
 1  2  1  2  3  4  5  1 
 1  2  3  1  2  3  1  1 
 1  2  1  2  3  4  1  1 
 1  2  1 (1) 2  3 [4] 5 : j   = 3
 1  2  1 (1) 2  3 [4] 5 : j+1 = 4
 1  2  3 (1) 2  3 [4] 5 : j+2 = 5
 1  2  1 (2) 3  4 [5] 6 : j+s-1 = 6 (s=4)
 1  1  2  1  2  3  1  2

例では (3, j)→(6,j) (j∈[3,6]) のそれぞれについて差が s-1 = 3 になっているので市松模様になっている.

[i,i+s-1] のそれぞれの列について y 方向に市松模様が続いているのか調べる必要はない.これで十分である.

切り取った部分は 0 を代入して切り取ったことを示しておく(*7).

mx[8][8]
 1  2  1  2  3  4  5  1 
 1  2  3  1  2  3  1  1 
 1  2  1  2  3  4  1  1 
 1  2  1  0  0  0  0  5 
 1  2  1  0  0  0  0  5 
 1  2  3  0  0  0  0  5 
 1  2  1  0  0  0  0  6 
 1  1  2  1  2  3  1  2

これの操作をサイズについて大きい順で,上から,左から,行っていけば良い.

ソースコード

  • 初期化が冗長だったので冗長部分を削除
    • mx[], my[] には初めから 1 を代入すればいい
    • b[][] は false で初期化しなくてもいい
  • 切り取った箇所に代入する値を -1 から 0 に変更
  • 高速化のためサイズ 1 のボードの数を数えるのをやめて,計算する方法に変更
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;

#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 ForD(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())

bool b[512][512]; // 各マスの色, false なら白
int mx[512][512]; // x 方向に何マス市松が続いているか
int my[512][512]; // y 方向に何マス市松が続いているか
// mx, my は切り取られたら 0 を代入

int solve(int M, int N, VS &v)
{
	// 初期化
	Rep(j,512) Rep(i,512)
		mx[j][i] = my[j][i] = 1;
	
	// 入力が Hex で渡されるので 2 値に変換 (*1)
	Rep(j,M) Rep(i,N/4) ForD(k,3,-1)
	{
		char c = (v[j][i]>='A')?v[j][i]-'A'+10:v[j][i]-'0';
		b[j][i*4+3-k] = (((c>>k)&1u)==1u);
	}
	
	// x 方向に市松模様が続く数を数える (*2)
	Rep(j,M) For(i,1,N) if(b[j][i]!=b[j][i-1])
		mx[j][i] = mx[j][i-1]+1;
	
	// y 方向に市松模様が続く数を数える
	Rep(i,N) For(j,1,M) if(b[j][i]!=b[j-1][i])
		my[j][i] = my[j-1][i]+1;
	
	int ms = min(N,M); // 切り出せる最大のサイズ
	VI scv(ms);        // サイズごとの切り出した個数
	
	int cut = 0;
	
	// サイズの大きい順に (*3)
	ForD(s,ms,0)
	{
		scv[ms-s] = 0;
		// あるマス (i,j) に着目
		Rep(j,M) Rep(i,N)
		{
			// 既に切り取られた
			if(mx[j][i]<0) continue;

			// 範囲オーバー
			if(i+s-1>=N) continue;
			if(j+s-1>=M) continue;

			// y 方向に市松模様が続かない (*4)
			if(my[j+s-1][i]-my[j][i]<s-1) continue;

			// 各行について x 方向に市松模様が続くか (*5)
			bool f = true;
			For(y,0,s) if(mx[j+y][i+s-1]-mx[j+y][i]!=s-1)
			{
				f = false;
				break;
			}
			// チェスボードになった (*6)
			if(f)
			{
				scv[ms-s]++;
				cut += s*s;
				// 切り取る (*7)
				For(y,j,j+s) For(x,i,i+s)
					mx[y][x] = my[y][x] = -1;
			}
		}
	}

	scv[0] = M*N - cut;
	
	// 数えて出力
	int c = 0;
	Rep(i,ms) if(scv[i]>0)
		c++;
	cout << c << endl;
	
	ForD(s,ms,0) if(scv[ms-s]>0)
		cout << s << " "<<scv[ms-s]<<endl;
	
	return 0;
}

int main(int argc, char* argv[])
{
	int num_of_test_cases;
	cin >> num_of_test_cases;
	
	Rep(test_case,num_of_test_cases)
	{
		int M, N;
		cin >> M >> N;
		VS v(M);
		Rep(i,M) cin >> v[i];
		cout << "Case #" << test_case+1 << ": ";
		solve(M, N, v);
	}
	
	return 0;
}

忍者最終号忍者最終号2010/05/24 14:291を数えないようにした方がもっと早くなりそうだ.

yuyarinyuyarin2010/05/27 10:16あ,本当ですね.
そのようにしてみました.

2010/05/23

Google Code Jam 2010 Round 1

| 23:25

通過出来ませんでした.

総評

全体的に凡ミスが多いというか,注意力が欠けていることを思い知らされた感じです.きちんとできていれば通っていたなぁというのが悔しいですね(みんなそうだと思いますが).

コマンドの操作をミスする,ファイルの操作を間違える,変数名を間違える,boost のヘッダが全部無くなっている,入力ファイルをダウンロードしてからデバッグコードを取り除いてコンパイルする...アルゴリズムやコーディングと本質的に関係のない部分でのロスが大きすぎました.

急がば回れってことで次回までは落ち着いて注意深く解く訓練をしたいと思います.

Round 1A

23 pt. Rank: 1346

Problemsmalllarge
A. Rotate1:14:05, 2 wrong tries1:14:40
B. Make it Smooth------
C. Number Game------

A は方向を示す配列にバグが有ったので修正したのはいいけど,small の input が毎度変わっていることに気がつかずに無駄に時間を食った...

	int dx[] = {1,0,1,-1};
	int dy[] = {0,1,-1,1};

B は与えられた文字列に対してレーベンシュタイン距離が最小となるような smooth な文字列を求める問題ということまでは分かったけど,アプローチが全く分からず.要復習.

C は sample が通らずに撃沈.rng さんのコードをチラ見したがまだ理解出来ていない.

Round 1B

40 pt. Rank: 1625

Problemsmalllarge
A. File Fix-it2:26:582:27:32
B. Picking Up Chicks------
C. Your Rank is Pure1:35:28Time expired

C から着手した.

C は少し時間がかかったけど良く解けたと思う.large の submission が +0.674 遅かったらしく reject された.これは large をかけて「やっぱり」終わらなさそうなので急遽 cache を実装したことが原因.「やっぱり」と思うことは初めからそうしたほうが良かったのに,急いでしまって実装しなかった.頭の悪い判断ミス.解く順番を変えたことでファイルの保存先を間違えたせいで small では提出するファイルを間違えた.その時に map の変数名に map を使ってコンパイルエラーを出したのがロスになってさらに悔やまれる.

A は簡単なので何も考えずに実装してパス.ディレクトリ構造の多分木ライブラリを見つけておきたい.boost を使ったけど何故か /usr/include にインストルされてーた boost (しかも1.35から1.41まで全部)がごっそり消えていたので急遽インストール.焦る.

B は未着手.問題も見ていない.

C large が通っていれば通過したので非常に悔やまれる.

Round 1C

9 pt. Rank: 2815

Problemsmalllarge
A. Rope Intranet15:231 wrong try
B. Load Testing4 wrong tries---
C. Making Chess Boards------

18:05 頃まで寝てしまったので頭がボケていた.

A は簡単なのですぐに実装したのはいいけど,large で間違っていた.見直してみると

int solve(int N, VI A, VI B)
{
	int cnt = 0;
	For(i,0,N) For(j,i+1,N)
	{
		if(A[i+1]>A[i] && B[i+1]<B[i]) cnt++;
		if(A[i+1]<A[i] && B[i+1]>B[i]) cnt++;
	}
	return cnt;
}

i, j の全組み合わせループなのに j はどこにいった...しかも For(i,0,N) じゃなくて For(i,0,N-1) だ.

B は問題の意味が未だにわかっていないが,なんとなく解き方を推測してコードを書いてみたけど全部失敗.答え合わせをしたところ,最初に書いたコードで 2 とするべきところを何故か C としていた(サンプルが C=2 の場合が多かったせいだろうか).あと -1 するのを忘れていたり.凡ミス.

C は入力を読み込んで解析するところまでで終わり.多分解けると思う.


Google Code Jam 2010 Round 1B A. File Fix-it

| 07:16

http://code.google.com/codejam/contest/dashboard?c=635101#s=p0&a=0

問題

既に存在する UNIX 形式のディレクトリパスの集合がある時に,与えられたディレクトリパスのディレクトリを作る際に,いくつのディレクトリを作らなければならないかを求める問題.

結果

small, large 共に correct.

アプローチ

本番では問題の細かい条件までちゃんと読む時間がなかったので,要点だけ押さえて,思い付くまま多分木を作ってディレクトリ構造とディレクトリの作成をシミュレートした.

large でも特に問題が大きくないので set を使ってすべてのディレクトリパスを保存しても問題なさそう.

問題の条件を読み直したら

1 1
/home/yuyarin/test
/home/yuyarin

みたいなケースも無い,つまり既存のディレクトリパスについてはその上位のディレクトリのパス(/home/yuyarin,/home)も,既存ディレクトリパスの集合に含まれているので,作るかどうかは既存ディレクトリパスの集合にパスの文字列が有るか無いかだけで判定できる.

作るべきディレクトリに対しては上位ディレクトリを求めていって,それが集合に無ければ追加してカウントを増やせばいい.

ソースコード

初めから書き直したので,提出時とアルゴリズムが違う

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

using namespace std;

typedef vector<string> VS;

#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 boost C++ library Version 1.41>=
// http://www.boost.org/
#include <boost/algorithm/string.hpp>

int main(int argc, char* argv[])
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int N, M;
		cin >> N >> M;
		VS ve(N);
		VS vc(M);
		set<string> sp;
		Rep(n,N)
		{
			cin >> ve[n];
			sp.insert(ve[n]);
		}
		int r = 0;
		Rep(m,M)
		{
			cin >> vc[m];
			VS vs;
			boost::algorithm::split(vs, vc[m], boost::is_any_of("/"));
			string s = "";
			For(i,1,sz(vs))
			{
				s = s + "/" + vs[i];
				if(sp.insert(s).second)
					r++;
			}
		}
		cout << "Case #" << t+1 << ": " << r << endl;
	}
	
	return 0;
}

Google Code Jam 2010 Round 1B C. Your Rank is Pure

| 04:38

http://code.google.com/codejam/contest/dashboard?c=635101#s=p2&a=0

問題

正数の集合 S の中においてある数 n が pure である条件がある.n が S の中で r 番目の数であるとき n のランクは r であると言う.n のランクが r1 であり,数 r1 のランクが r2 であり,,,としていき最後に 1 にたどり着けば n は pure であると言う.

与えられた n について, S = {x|x∈[2,n]} の部分集合 S' において n が pure であるような S' の作り方の個数を求める.

結果

small は correct だったけど提出するコードを間違えた.

large は答えを出したけど,提出がギリギリで駄目だったけど,admin に問い合せろとエラーが出た.

なので問い合わせ中.

→提出は + 0.674 秒遅かったらしい.そう計測された以上 reject とのこと.正しいソースコードの再アップロードと,エラーの理由はスルーされた.

large-practice では正解を出せていた.

アプローチ

数字 n がランク r として出現するときの場合の数を求める.

DP でも解けるけど DP にせずに再帰とキャッシュ(*1)を使った.

r〜n の間に m 個(m∈[0,r-2]) の数字が入る場合(*2)の数は Combination(n-r-1,m) で(*3),1〜r の間に数字が入る場合の数は数字 r がランク r-m-1 で現れる場合の数なのでこの関数の再帰で求められる.これらを掛け合せたものが,数字 n がランク r として出現するときの場合の数である(*4).

この関数を入力 n に対して,数字 n がランク r∈[1,n] として出現するときの場合の数の合計を計算してあげれば良い(*5).

Combination を求める部分で Integer Overflow を起こしそうな気配なので,gmpxx にお世話になった.

ソースコード

提出コードから掲載コードへの変更点

  • キャッシュ部分をマクロ化.
  • include 順序の整列,改行の追加削除等,表示を見やすくするもの
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <iostream>

// using The GNU Multiple Precision Arithmetic Library
// http://gmplib.org/
// compile with -lgmpxx -lgmp
#include <gmpxx.h>

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

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

#define make_cache(...) map< __VA_ARGS__ > cache;\
map< __VA_ARGS__ >::iterator cache_it;
#define cache_hit(query_) (cache_it=cache.find(query_))!=cache.end()
#define check_cache(query_) if(cache_hit(query_)) return (*cache_it).second;
#define store_cache(key_,value_) cache.insert(mp(key_,value_))

make_cache(pair<int,int>,mpz_class)

mpz_class func(int n, int r)
{
	if(r==1) return 1;
	
	// *1
	check_cache(mp(n,r));
	
	int N = n-r-1;
	int M = r-2;
	mpz_class ans = 0;
	
	// *2
	for(int m=0; m<=M; m++)
	{
		if(N<m) continue;
		mpz_class p=1;
		// Combination(N,m) *3
		for(int j=0; j<=m-1; j++)
			p *= (N-j);
		for(int j=2; j<=m; j++)
			p /= j;
		// *4
		ans += p*func(r, M-m+1);
	}
	
	// *1
	store_cache(mp(n,r),ans);
	
	return ans;
}

int solve(int n)
{
	mpz_class ans = 0;
	// *5
	for(int i=1; i<n; i++)
		ans += func(n, i);
	ans %= 100003;
	return ans.get_si();
}

int main(int argc, char* argv[])
{
	uint T;
	cin >> T;
	
	for(uint t=0;t<T;t++)
	{
		uint n;
		cin >> n;
		cout << "Case #" << t+1 << ": " << solve(n) << endl;
	}
	
	return 0;
}

AndiAndi2011/07/22 15:08Thanks alot - your answer solved all my problems after several days srtuglging

ymztwdpymztwdp2011/07/26 00:50iMKSlH , [url=http://vxqonjgohmzr.com/]vxqonjgohmzr[/url], [link=http://bdghiksyjeoz.com/]bdghiksyjeoz[/link], http://fqpjpgeffbmu.com/

EgwoloEgwolo2013/02/16 23:19Thanks for contributing. It's helepd me understand the issues.

zzokgazzokga2013/02/19 14:25gNeh7s <a href="http://jdxldqxslfbx.com/">jdxldqxslfbx</a>

ealpalshhtealpalshht2013/02/19 14:25ftpxVI <a href="http://cpdedlynamuf.com/">cpdedlynamuf</a>

2010/05/10

Google Code Jam 2010 Qual A. Snapper Chain

| 11:48

http://code.google.com/codejam/contest/dashboard?c=433101#s=p0

問題を理解するのに時間がかかった上に1回勘違いしてミスした.気づいたら凄く簡単...

※掲載しているコードは手直ししたものです.

#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
	unsigned int T, N, K;
	cin >> T;
	for(unsigned int i=0;i<T;i++)
	{
		cin >> N >> K;
		cout << "Case #" << i+1 << ": " << (((K+1)%(1u<<N)==0)?"ON":"OFF") << endl;
	}
	
	return 0;
}

Google Code Jam 2010 Qual B. Fair Warning

| 11:48

http://code.google.com/codejam/contest/dashboard?c=433101#s=p1

C++ で多倍長整数演算ができなかったので,本番では泣きながら Ruby で書いた.RubyC++ を行ったり来たりすると文法ミスが多発する...error: expected `;' before ... みたいな.

TopCoder では多分使えないけど,今後のことを考えて gmpxx で練習してみた.

※掲載しているコードは手直ししたものです.

#include <iostream>
#include <vector>
#include <gmpxx.h>

using namespace std;

mpz_class gcd(mpz_class& l, mpz_class &r)
{
	mpz_class a;
	mpz_gcd(a.get_mpz_t(), l.get_mpz_t(), r.get_mpz_t());
	return a;
}

int main(int argc, char* argv[])
{
	unsigned int C;
	cin >> C;
	
	for(unsigned int i=0;i<C;i++)
	{
		unsigned int N;
		cin >> N;
		vector<mpz_class> v(N);
		vector<mpz_class> d(N-1);
		for(unsigned int j=0;j<N;j++)
		{
			cin >> v[j];
		}
		sort(v.begin(), v.end());
		for(unsigned int j=0;j<N-1;j++)
		{
			d[j] = v[j+1]-v[j];
		}
		mpz_class g = d[0];
		for(unsigned int j=1;j<N-1;j++)
		{
			g = gcd(g, d[j]);
		}
		mpz_class m = v[0] % g;
		mpz_class r = (m==0) ? mpz_class(0) : g-m;
		cout << "Case #" << i+1 << ": " << r << endl;
	}
	
	return 0;
}

Google Code Jam 2010 Qual C. Theme Park

| 11:48

large では答えが 32bit で収まらないことに気付かず提出してしまった.本番では int を使っていたので負の値が出力されていたのだけど,時間を急いでしまって確認しなかった.もったいない.

本番ではやらなかったループ検出機能を追加.凄く速くなった.

※掲載しているコードは手直ししたものです.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main(int argc, char* argv[])
{
	unsigned int T;
	cin >> T;
	
	for(unsigned int t=0;t<T;t++)
	{
		unsigned int R, k, N;
		cin >> R >> k >> N;
		
		vector<unsigned int> g(N);
		for(unsigned int j=0;j<N;j++)
		{
			cin >> g[j];
		}
		
		vector<unsigned int> nv(N), cv(N);
		for(unsigned int j=0;j<N;j++)
		{
			unsigned int i = j;
			unsigned int c = g[i];
			i = (i+1)%N;
			while(c+g[i]<=k&&i!=j)
			{
				c += g[i];
				i = (i+1)%N;
			}
			nv[j] = i;
			cv[j] = c;
		}
		
		unsigned int idx = 0;
		unsigned long long euro = 0;
		map<unsigned int, pair<unsigned int, unsigned long long> > m;
		bool loop_detect = false;
		for(unsigned int r=0;r<R;r++)
		{
			if(loop_detect==false && m.insert(make_pair(idx, make_pair(r,euro))).second==false)
			{
				pair<unsigned int, unsigned long long> p = m.find(idx)->second;
				unsigned int repeat = ((R-p.first)/(r-p.first));
				euro += (euro-p.second)*(repeat-1);
				r += (repeat-1)*(r-p.first);
				if(r>=R) break;
				loop_detect = true;
			}
			euro += cv[idx];
			idx = nv[idx];
		}
		
		cout << "Case #" << t+1 << ": " << euro << endl;
	}
	return 0;
}

忍者最終号忍者最終号2010/05/13 00:53cin, cout使うな.

忍者最終号忍者最終号2010/05/13 00:53cin, cout使うな.

忍者最終号忍者最終号2010/05/13 00:53cin, cout使うな.

yuyarinyuyarin2010/05/13 04:17>忍者最終号さん
それはどういった理由からでしょうか?

exsexfexsexf2011/02/28 12:15RFRU9x <a href="http://kstxagthgxsq.com/">kstxagthgxsq</a>, [url=http://hoakvztpgsoj.com/]hoakvztpgsoj[/url], [link=http://liulzkniffql.com/]liulzkniffql[/link], http://gfaelupssudw.com/