アルゴリズム二分探索用いた問題の解法

Question

c++でアルゴリズムの勉強をしています。
二分探索を用いて問題を解いていたのですが、わからないところがあります。
コード46行目の、配列kkにおいて、c * n + d とする意味がわかりません。
なぜ c * n + d とするのですか？kk[0]から順に埋めていくのではダメなのですか？

(問)
n枚の数字が書かれた紙がある。この中から一枚引いて、数字を見たのち元に戻す。これを４回行う。引いた数字をk1,k2,k3...,knとするとき、数字の和がmになる取り出し方が存在するか確認したい。存在するならyes,存在しないならnoと出力する。
[制約]
1 <= n <= 50
1 <= m <= 10^8
1 <= ki <= 10^8

該当のソースコード

ソースコード

#include<iostream>
using namespace std;

const int MAX_N = 50;
int n, m, k[MAX_N];
int kk[MAX_N * MAX_N];

//二分探索
bool binary_search(int x) {
    //配列kkについて考える。xの存在し得る範囲は、kk[1],kk[2],...,kk[n*n-1]
    //最小の添え字
    int min = 0;
    //最大添え字
    int max = n * n - 1;
    //中央の要素番号
    int mid;
    
    //最大値と最小値が一致するまで比較する
    while (min <= max) {
        mid = (min + max) / 2;
        
        //一致するか比較
        if (kk[mid] == x) return true;
        //目的値が中央値よりも上なら最小値を中央値の１個上に設定
        else if (kk[mid] < x) min = mid + 1;
        //目的値が中央値よりも下なら最大値を中央値の１個下に設定
        else if (kk[mid] > x) max = mid - 1;
    }
    
    return false;
}

int main() {
    
    //標準入力
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &k[i]);
    }
    
    //k[c] + k[d]のとり得る値を列挙する
    for (int c = 0; c < n; c++) {
        for (int d = 0; d < n; d++) {
            kk[c * n + d] = k[c] + k[d];
        }
    }
    
    
    sort(kk, kk + n * n);
    
    bool f = false;
    
    for (int a = 0; a < n; a++) {
        for (int b = 0; b < n; b++) {
            //内側の2つ代わりに二分探索を用いる
            if (binary_search(m - k[a] - k[b])) {
                f = true;
            }
        }
    }
        
        if (f) puts("Yes");
        else puts("No");
}

Comments

[episteme]

> kk[0]から順に埋めていくのではダメなのですか？

やってみた?

[nisi]

すいません！勝手なイメージで２次元配列になると勘違いしていました、、、
実際に数字を代入して考えてみたところ、１次元の配列で、順に埋まっていくのを確認できました。
ありがとうございます！

Answer 1

コード46行目の、配列kkにおいて、c * n + d とする意味がわかりません。

配列kkの大きさがn×nであるからです。
c*nで配列の行、dで列の位置を表しています。
例えばn=3の場合、配列kkは以下の表のようになります。
そこで、c=1, d=1とするとkk[4]になり、２次元配列上の座標(c,d)が特定できたことになります。
つまり、変数cが行の位置、変数dが列の位置を示しています。

列1	列2	列3
0	1	2
3	4	5
6	7	8

Comments

[nisi]

ありがとうございます！理解することができました！