コーディング練習＠Coder.5

前回、前々回のモジュールを使ってコンテスト159のE問題(全探索問題)への解答をつくります。前々回:

そして前回:

1. 階乗

手始めとして組み合わせの総数を計算するため、階乗の計算をしてくれる関数を定義します。大きな数になる可能性があるのでlong intを返り値に設定します。

long int Factorial(int upto){
	if(upto == 0)
		return 1;
	return upto * Factorial(upto - 1);
}

再帰呼び出しをすれば短いコードで実現できます。

2. 関数定義

あとはいままでの結果をすべてがっちゃんこするだけ。まずは行方向の分割を全探索する関数（前々回）。

#include<stdio.h>
#include<stdlib.h>

int ROW_INDEX = 1;
void AllCombs_ints(int min_range, int max_range, 
                   int depth, int n_ints, int **comb){
	if(depth > 0){
		for(int x = min_range; x <= max_range; x++){
			comb[0][depth-1] = x;
			if(depth == 1){
				for(int num_i = 1; num_i <= n_ints; num_i++)
					comb[ROW_INDEX][num_i-1] = comb[0][n_ints-num_i];
				ROW_INDEX++;
			}
			AllCombs_ints(x + 1, max_range, depth - 1, n_ints, comb);
		}
	}
	if(depth == n_ints)
		ROW_INDEX = 1;
}

そして次に列方向に最適な分割を返す関数(前回)。

int Find_Rightmost_Col(int threshold, int from_col, int n_rows, 
                       int n_slices, int n_cols, int slices[n_slices], 
                       int mat[n_rows+1][n_cols+1]){

	int current_col = from_col;
	int value_cell[n_slices+1];
	for(int cell_i = 0; cell_i <= n_slices; cell_i++)
		value_cell[cell_i] = 0;

	while(current_col <= n_cols){
		for(int cell_i = 0; cell_i <= n_slices; cell_i++){
                            //1->slices[0]
			for(int row_i = (cell_i == 0 ? 1 : slices[cell_i-1] + 1);
                         //slices[n_slices-1]+1->n_rows  
				row_i <= (cell_i == n_slices ? n_rows : slices[cell_i]); 
               row_i++){
				value_cell[cell_i] += mat[row_i][current_col];
			}
			if(value_cell[cell_i] > threshold)
				return current_col - 1;
		}
		current_col++;
	}
	return current_col - 1;
}

さらに階乗計算をする関数。

long int Factorial(int upto){
	if(upto == 0)
		return 1;
	return upto * Factorial(upto　-　1);
}

3. main関数構築

ここまで来ればmainの構築は簡単です。流れとしては行方向の分割を全探索してリストアップし、それらをひとつずつ固定して縦方向の最適分割を求めます。もし分割自体が可能であれば、前の結果と比較して分割回数が少ない方を保存しておく、という感じ。最後に最も少ない分割回数を出力して終了です。

int main(){
	int n_rows, n_cols, nmax_white;
	scanf("%d %d %d", &n_rows, &n_cols, &nmax_white);
	int mat_choco[n_rows+1][n_cols+1];
	for(int row_i = 1; row_i <= n_rows; row_i++){
		char str[n_cols];
		scanf("%s", str);
		for(int col_i = 1; col_i <= n_cols; col_i++){
			if(str[col_i-1] == '0')
				mat_choco[row_i][col_i] = 0;
			else
				mat_choco[row_i][col_i] = 1;
		}
	}

まずは入力から行列のディメンション、ホワイトチョコレートのセル内の最大数（閾値）を読みとります。また次にチョコレートの分布を読みとり、0（チョコレート）1（ホワイトチョコレート）に変換します。

	int ans = n_rows * n_cols; //分割の回数の最大値
	for(int n_slices = 0; n_slices < n_rows; n_slices++){
		long int n_combs = Factorial(n_rows-1) / Factorial(n_slices) 
                        / Factorial(n_rows-1-n_slices);
		int **pt_slice;    //行方向の分割を格納するダブルポインタ
		pt_slice = (int **) malloc(sizeof(int *) * (n_combs+1));
		for(int pt_i = 0; pt_i <= n_combs; pt_i++)
			pt_slice[pt_i] = (int *) malloc(sizeof(int) * 
                                (n_slices > 0 ? n_slices : 1));
		AllCombs_ints(1, n_rows-1, n_slices, n_slices, pt_slice);

		for(int comb_i = 1; comb_i <= n_combs; comb_i++){
			int ans_temp = n_slices;
			int current_col = 1;

			while(current_col <= n_cols){
				int col_temp = current_col;
				current_col = Find_Rightmost_Col(nmax_white, current_col, 
                                n_rows, n_slices, n_cols, 
								pt_slice[comb_i], mat_choco);
				if(col_temp > current_col){ //分割不可能
					ans_temp = n_rows * n_cols;
					break;
				}
				ans_temp++;
				current_col++;
			}
			if(--ans_temp < ans) //最後の列カウントをans_tempから引く
				ans = ans_temp;
		}
		
		for(int pt_i = 0; pt_i <= n_combs; pt_i++)
			free(pt_slice[pt_i]);
		free(pt_slice);
	}
	printf("%d", ans);
	return 0;
}

コードを見ていて思ったが、階乗計算のところは普通に組み合わせの総数を求める関数（コンビネーション）を定義したほうがすっきりするかもしれない。ansのデフォルト値は最大分割回数（行数×列数）にしていて、ans_tempと比較して解答を更新しています。

4. 感想

問題はこれをコンテスト中に書けるかってことなんだよね。毎週コンテストがあるのでとりあえず参加していきます。（先週は無理だったが…）

問題を解く鍵となるアルゴリズムは有限なので、まずは個々のアルゴリズムを実装して自分の武器庫にしていくことですね。コンテストで出会った問題が自分の知らないアルゴリズムを必要とするなら、都度それを自分のものにしていく感じで進んでいきます。

あと課題としては数学的な考察で計算が大幅に縮小できる場合。解析解があるときや解の範囲が絞れるときは、もう自分がそこに気づくしかない。問題の数学的特性を抽出して効果的なアルゴリズムに落とし込むことに慣れるしかないと思います。やはり先は長い。