LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@imadedede

第23回オフラインリアルタイムどう書く　をC言語で

Last updated at Posted at 2014-07-12

まとめ

  • なんかみつけたからやってみた。
  • C言語で200行ほど。コメントやテストコードを抜けば実質100行くらい？
  • 事前にざっくり計算することで探索量を減らす。
  • Rubyで30行くらいの人がいてすごいと思った。
  • 考えた時間は一晩くらい。コーディングは3時間くらい。

問題に対するアプローチ

問題はこちら。
自然数を設定済みのマス目をたどって、単調増加の数列をどれだけ長く作れるか、というもの。
どれだけ長く作るか、ということで、おそらく深さ優先探索をすればよいだろうと思った。
ざっくり計算量を考える。マス数を n 、マスが取りうる値を m とすると、単純な深さ優先探索だとたぶん O(nm^2) くらいになる。例題は55マスで値は0〜9の範囲なので実質あんまり気にしなくても良いけど、できればアルゴリズムを O(n*m) に近づけたい。

というわけで、事前にいろいろ計算することにした。
探索中に、もう無理とわかったら引き返す。これで計算量はだいぶ少なくなるはず。
まず事前にマス目に出現する値の分布を調べる。そして分布から次の値を計算する。

  • ステージ全体で最大限可能な接続数
  • ステージ上のある値から可能な残り接続数

例えば用意されているテストデータ8 (01234/11234/22234/33334/44444) だと、

マスの取りうる値 0 1 2 3 4 5 6 7 8 9
値の分布 1 3 5 7 9 0 0 0 0 0
可能な残り接続数 4 3 2 1 0 0 0 0 0 0

ステージ全体で最大限可能な接続数は5。接続数はそれぞれ表のようになる。

この2つは分布を元に計算するので、単純な指標にしかならない。しかしこの事前計算はだいたい O(n) くらいなので、まあ費用対効果に見合っているように思う。

ということで、実際のコードはこちら。
（この例題くらいデータ量が小さいと、事前計算とそれによる判定のコストがかなり多くなってしまったような……）

コードと結果

kunekune.c
// くねくね
// C99 では変数宣言をどこに置いても良い。積極的に利用。
# include <stdio.h>
# include <stdlib.h>

# define CELL_VALUE_MAX 9		// マス目のとりうる値の最大値
# define CELL_VALUE_END 10		// 最大値+1
# define Y_END 5		// 縦マスの数
# define X_END 5		// 横マスの数

// 事前計算する理論値を格納する構造体
typedef struct{
	int LimitConnections;		// ステージで予想できる最大接続数
	int RemainConnectionsTable[CELL_VALUE_END];		// 各値から可能な残り接続数
}PreCalc;
// ステージデータを格納する構造体
typedef struct{
	int Footmark;		// 足跡
	int Status;		// 升目に指定された数字
}StageData;

// ステージから理論値を求める
// マス目の取りうる最小値が0以外になると、途端に面倒になる。でも今回は考えない。
void TheolValueCalc(const char* stage, PreCalc *theol_val){
	int existTable[CELL_VALUE_END]={};

	// 存在を調べる
	for(const char *c=stage; *c!='\0'; c++){
		if(*c=='/'){ continue; };
		char ctos[2]={*c};
		existTable[atoi(ctos)]+=1;
	}
	// 可能な連結の最大値を調べる
	for(int i=0; i<CELL_VALUE_END; i++){
		if(existTable[i]>=1){
			theol_val->LimitConnections += 1;
		};
	}
	// 可能連結数テーブルを求める
	int remains = theol_val->LimitConnections-1;
	for(int i=0; i<CELL_VALUE_END; i++){
		if(existTable[i]>=1){
			theol_val->RemainConnectionsTable[i] = remains;
			remains--;
		};
	}
	return;
}

// ステージデータを構築。二次元は引数が面倒なので一次元配列
void ImportStage(const char *stage, StageData stage_data[]){
	const char *c=stage;
	// 一つずつ文字列ポインタを進めて数字に変換していく
	for(int i=0; i<Y_END; i++){
		for(int j=0; j<X_END; j++){
			char ctos[2]={*c};
			stage_data[ i*X_END + j ].Status = atoi(ctos);
			c++;
			if(*c=='\0'){ goto EXIT; };		// 安全装置
		}
		if(*c=='/'){ c++; }		// 区切り文字ならポインタを進める
	}
EXIT:
	return;
}

// 探索開始　深さ優先探索　時計回り
void SearchKunekune(StageData stage_data[], int posi, int prev_status,
		int count, int *max,const PreCalc *theol_val){
	// 引き返し判定パート
	if(theol_val->LimitConnections <= *max){ return; }	// 既に理論値に達しているなら脱出
	if( posi<0 || X_END*Y_END <= posi){ return; };		// 指定された場所が範囲外なら脱出
	if(stage_data[posi].Footmark >= 1){ return; };		// すでに来たなら脱出
	// 前のマス以下なら脱出
	const int status = stage_data[posi].Status;
	if( status <= prev_status){ return; };
	// 事前の計算結果から可能な最大値を計算して、現在の記録を超えられないなら脱出
	const int count_hope = theol_val->RemainConnectionsTable[status] + count;
	if( count_hope <= *max){ return; };
	
	// 計算・移動パート
	if(count>*max){ *max=count; };

	// 時計回りに探索
	stage_data[posi].Footmark = 1;	// 足跡
	// 上へ移動
	SearchKunekune(stage_data, posi-X_END, status, count+1, max, theol_val);
	// 右へ移動
	if(posi%X_END < X_END-1){		// 今いるのが右端じゃなければ
		SearchKunekune(stage_data, posi+1, status, count+1, max, theol_val);
	}
	// 下へ移動
	SearchKunekune(stage_data, posi+X_END, status, count+1, max, theol_val);
	// 左へ移動
	if(posi%X_END > 0){		// 今いるのが左端じゃなければ
		SearchKunekune(stage_data, posi-1, status, count+1, max, theol_val);
	}
	stage_data[posi].Footmark=0;		// 足跡消し

	return;
}

// くねくね長の最長連結数を求める
int Kunekune(const char* stage){
	// 理論値を求める
	PreCalc theol_val={};
	TheolValueCalc(stage, &theol_val);
	// 理論値の最大値が2以下ならその場で返す
	if(theol_val.LimitConnections<=2){ return theol_val.LimitConnections; };
	
	// ステージデータを構築
	StageData stage_data[X_END*Y_END]={};
	ImportStage(stage, stage_data);
	
	// 探索開始　深さ優先探索
	int max=0;
	for(int i=0; i<Y_END; i++){
		for(int j=0; j<X_END; j++){
			int posi = X_END*i + j;
			SearchKunekune(stage_data, posi, -1, 1, &max, &theol_val);
			// 理論値を達成したら探索終了
			if(max>=theol_val.LimitConnections){ goto ANSWER; };
		}
	}

ANSWER:
	return max;
}

// テストしやすいようにラップ
void test(const char* stage, const char* correct){
	static int i=0;
	int answer = Kunekune(stage);
	if( answer != atoi(correct) ){
		printf("Wrong! No.%d, cor:%s, ans:%d\n", i, correct, answer);
	}
	else{ printf("Successe! No.%d\n", i); };
	i++;
	return;
}

// エントリポイント
int main(int argc, char *argv[]){
	// ここで呼び出してテストする
/*0*/ test( "01224/82925/69076/32298/21065", "6" );    
/*1*/ test( "03478/12569/03478/12569/03478", "10" );    
/*2*/ test( "09900/28127/87036/76545/87650", "10" );    
/*3*/ test( "77777/77777/77777/77777/77777", "1" );    
/*4*/ test( "00000/11111/22222/33333/44444", "5" );    
/*5*/ test( "01234/12345/23456/34567/45678", "9" );    
/*6*/ test( "10135/21245/43456/55567/77789", "8" );    
/*7*/ test( "33333/33333/55555/55555/77777", "2" );    
/*8*/ test( "01234/11234/22234/33334/44444", "5" );    
/*9*/ test( "98765/88765/77765/66665/55555", "5" );    
/*10*/ test( "01234/10325/23016/32107/45670", "8" );    
/*11*/ test( "34343/43434/34343/43434/34343", "2" );    
/*12*/ test( "14714/41177/71141/17414/47141", "3" );    
/*13*/ test( "13891/31983/89138/98319/13891", "4" );    
/*14*/ test( "01369/36901/90136/13690/69013", "5" );    
/*15*/ test( "02468/24689/46898/68986/89864", "6" );    
/*16*/ test( "86420/68642/46864/24686/02468", "5" );    
/*17*/ test( "77777/75557/75357/75557/77777", "3" );    
/*18*/ test( "53135/33133/11111/33133/53135", "3" );    
/*19*/ test( "01356/23501/45024/61246/13461", "5" );    
/*20*/ test( "46803/68025/91358/34792/78136", "4" );    
/*21*/ test( "66788/56789/55799/43210/33211", "9" );    
/*22*/ test( "40000/94321/96433/97644/98654", "9" );    
/*23*/ test( "58950/01769/24524/24779/17069", "6" );    
/*24*/ test( "97691/01883/98736/51934/81403", "4" );    
/*25*/ test( "92049/27798/69377/45936/80277", "5" );    
/*26*/ test( "97308/77113/08645/62578/44774", "5" );    
/*27*/ test( "90207/17984/01982/31272/60926", "6" );    
/*28*/ test( "62770/65146/06512/15407/89570", "4" );    
/*29*/ test( "93914/46889/27554/58581/18703", "5" );    
/*30*/ test( "42035/12430/60728/30842/90381", "5" );    
/*31*/ test( "90347/53880/67954/95256/68777", "6" );    
/*32*/ test( "05986/60473/01606/16425/46292", "5" );    
/*33*/ test( "18053/90486/24320/04250/03853", "5" );    
/*34*/ test( "36865/13263/67280/18600/12774", "5" );    
/*35*/ test( "72456/72052/79971/14656/41151", "5" );    
/*36*/ test( "94888/28649/05561/76571/97567", "5" );    
/*37*/ test( "50214/94693/88718/78922/55359", "5" );    
/*38*/ test( "76502/99325/17987/31737/93874", "7" );    
/*39*/ test( "87142/14764/13014/00248/73105", "6" );    
/*40*/ test( "24573/71679/48704/19786/91834", "7" );    
/*41*/ test( "20347/61889/06074/61263/20519", "7" );    
/*42*/ test( "74344/97459/97302/14439/35689", "6" );    
/*43*/ test( "04794/52198/50294/09340/24160", "5" );    
/*44*/ test( "41065/69344/64698/54167/43348", "7" );    
/*45*/ test( "39947/15696/03482/19574/70235", "7" );    
/*46*/ test( "92767/16790/84897/69765/75734", "7" );    
/*47*/ test( "09654/79610/05070/23456/74687", "8" );    
/*48*/ test( "73998/98799/98707/05633/23915", "8" );    
/*49*/ test( "35661/17480/89723/64335/27217", "7" );    
/*50*/ test( "02489/77571/84873/03879/84460", "7" );
	return 0;
}

実行結果

$ ./a.out 
Successe! No.1
Successe! No.2
Successe! No.3
Successe! No.4
Successe! No.5
Successe! No.6
Successe! No.7
Successe! No.8
Successe! No.9
Successe! No.10
Successe! No.11
Successe! No.12
Successe! No.13
Successe! No.14
Successe! No.15
Successe! No.16
Successe! No.17
Successe! No.18
Successe! No.19
Successe! No.20
Successe! No.21
Successe! No.22
Successe! No.23
Successe! No.24
Successe! No.25
Successe! No.26
Successe! No.27
Successe! No.28
Successe! No.29
Successe! No.30
Successe! No.31
Successe! No.32
Successe! No.33
Successe! No.34
Successe! No.35
Successe! No.36
Successe! No.37
Successe! No.38
Successe! No.39
Successe! No.40
Successe! No.41
Successe! No.42
Successe! No.43
Successe! No.44
Successe! No.45
Successe! No.46
Successe! No.47
Successe! No.48
Successe! No.49
Successe! No.50
Successe! No.51

問題なし。

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?