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

アルゴリズムの基本は総当たりだそうです。人間には現実的な時間で解けない問題も、計算機なら解ける。この差が顕著に現れるのが、有効な解法が見つかっておらず、可能性を総当たりするほかない問題。コンテスト159のE問題がこれでした:

E - Dividing Chocolate

1. 問題

板チョコを分割する最小回数を求める問題。

板チョコはホワイトチョコレートと普通のチョコレートが分布していて、これと板チョコのディメンションが最初に入力として与えられる。

板チョコを横か縦の直線で割っていって、そのあとできる各サブブロック内のホワイトチョコレートが与えれた閾値以下になるようにしたい。そのような分割を達成するための横縦線の最小本数を求めるという、問題を見た瞬間へ？となる設定。

2. 方針

まず、板チョコを行列とみて横方向の分割を総当たりする。各横分割に対して、縦の分割必要回数を次のように計算する。

●まず一列目からスタートする。
●列は横分割によってセルに区切られている。各セルのホワイトチョコレートの数を算出する。
●もしこの時点で閾値を超えていたら、横分割を更新する。
●もし閾値を超えていなかったら、列をひとつ進めて同じことをし、前の結果に今の結果を足し合わせる。以下、順次列を進める。
●初めてk列目であるセルのホワイトチョコレートの数が閾値を超えたら、現在の列マイナス１の列で止め、縦分割の回数を１増やす。
●スタート列をkとし、kが板チョコの列数に達するまで同じことを繰り返す。

分割の総数(縦横分割の総数)を前の横分割の結果と比較し、より小さいなら更新する。

これを実装するにはまず、与えられた範囲から選び出せる整数の組をすべて列挙する関数が要ります。(板チョコの横分割の総当たりの部分。)これをまずは構築することを私は考えました。

3. 再帰呼び出し

演算が同じ構造をスケールを変えて繰り返す種類のものだった場合、再帰呼び出しで関数を定義できます。例えば１からnまでの総和の計算であれば、それは１からn-1までの総和にnを足せばよいので、ここに同じ関数を繰り返し使える構造があります。(ただしスケールがnからn-1になる。)

１からnまでの整数からm個の整数の組をすべて取り出すには、for文をいくつも書けばいいのですが(第一の整数を１からnの範囲で、第二の整数を第一の整数からnの範囲で、以下同様)、今はfor文の数が可変なのでこのアプローチは有効ではありません。しかし最初の整数を固定すれば、あとはその整数からnまででm-1個の整数を取り出す作業に帰着するので、ここに再帰的構造があります。そこで始まりと終わりの整数と、そこから取り出す整数の個数を引数とする関数を再帰呼び出しすればいけそうです。

4. 実装

//異なる組を区別するインデックス。関数内で処理できないか？
int ROW_INDEX = 1;
//[min_range, max_range]からn_ints個の整数の組をすべてとりだしcomb[組][整数]に格納する
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]を一時的な格納場所として使っている。気持ち悪い。
			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;
}

ROW_INDEXという変数が関数の外に出ているのは、関数内部で宣言しても再帰呼び出しのときに区別されてしまって、異なる組のインデックスとして機能しないからです。どうにかならんかな…

またダブルポインタ**combを受け取ってそこに整数の組を入れていくのですが、その第０行を一時的な値の保管場所として使っています。これは最後の整数が定まった直後に配列への書きだしを一気にしているため、それ以前の整数の履歴を保存しておく必要があるからです。

またforループの階層をdepthとして引数にしていますが、これは最初の呼び出し時点ではn_ints、つまり取り出す整数の個数とまったく同じ値です。

5. 感想

問題の回答を実装するにはさらに、閾値を超える直前の列を返す関数が必要です。この関数を繰り返し用いることで、縦分割の回数を求め、最小分割回数を求めます。その実装はまた次回に。先は長い！