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

前回に引き続き全探索問題の実装を試みます。

1. 問題

今回アタックする問題はこうです。０と１の二値行列があり、行番号がいくつか選ばれていて、これが行方向の分割を定義していると考えます。例えば５行の行列で(1, 3)であれば１行目、２から３行目、そして４から５行目、という風に三分割されているとするわけです。

一般に行数n_rowsで、横分割が

(0 < slice_1,
slice_2, …,
slice_i, …,
slice_(n_ints) < n_rows)

であれば、

cell_1 = [1, slice_1],
cell_2 = [slice_1 + 1, slice_2], …,
cell_i = [slice_(i-1) + 1, slice_i], …,
cell_(n_ints+1) = [slice_(n_ints) + 1, n_rows]

というセルに分割されます。

そこでこのような分割を受け取り、ある与えられた列から始まって、どの列で初めてあるセルの値が閾値を超えるかを計算して返す関数を実装します。ここであるセルの値とは、例えば列１から列３までの範囲で囲まれた各セルに含まれる成分の総和を指します。

2. 実装

//与えられたslicesでmatをn_slices+1個のcell_iに区切り、
//from_colからのvalue_cell[cell_i]がどれもthresholdを超えない最大の列番を返す
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;
}

関数の名前難しい！！どういう条件のもとRightmostなのかが名前からわからないのはまずい気がするのですが、いい表現が思い浮かばない…　やっていることは一番右の列を見つけるってことで名前と一致しているのですが。

また返す値としてcurrent_colから１引いたものをとっているので、例えばあるfrom_colを与えて関数を走らせたらfrom_col - 1が返って来た、ということであれば、それはしょっぱなの列から閾値を超えているわけですから、横分割のほうがもうまずいわけです。そこでこちらが引数として渡すfrom_colよりも（１だけ）小さな値が返って来たときは、横分割（これはすでに総当たりで探索済み）のほうを別のものに更新する、という風にしていけそうです。

3. 感想

こういう感じで、使える関数の武器庫を地道に増やしていくのは効率が悪いんじゃ…と思ったりもしますが、楽しんでやっていきたいのでこれはこれでいいでしょう。

研究をしていたときの癖で、答えをカンニングして(もうすでに答えがあるのなら)、泣く泣く嚥下するのに抵抗があるのも事実です。すでに分かっていることをわざわざ自分で導いたって意味ないでしょ、って言われたらその通りなんですが。でも自分で導けるっていうのは案外自信になったりするんですよね。自分の実力のチェックにもなるし、自分で考えた部分が多いとそれだけ吸収も早いです。食べ物は飲み込む前によく噛まないと多分だめなんです。