c++で競技プログラミング、binary_search関数で論理エラー

//int n, m, k[MAX_N];

//2つで作れる数を格納する配列
int kk[MAX_N * MAX_N];

bool binary_search(int x){
    //xの存在し得る範囲はkk[1], kk[l+1],...,kk[r-1]
    int l=0; r = n * n;

    //範囲に何も含まれなくなるまで繰り返す
    while(r-1 >= 1){
        int i = (1+r)/2;
        if (kk[i] == x)return true; //見つかった
        else if(kk[i] < x)l=i+1;
        else r = i;
    }
    //見つからなかった
    return false;
    void solve(){
        //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++){
                //内側の二つのループの代わりに二分探索
                if(binary_search(m-k[a]-k[b])){
                    f = true;
                }
            }
        }
        if (f) puts("Yes");
        else puts("No");
    }
}

上記のコードは、プログラミングコンテストの参考書に載っていたもので、便宜的に入力が全てmain関数で読み込まれてグローバル変数に置かれたのち、関数solveが呼ばれることによって問題を解く形式で書かれています。
当の問題ですが、以下のようなものです。
<問題>
あなたの友人は次のようなゲームをあなたに仕掛けてきました。数字が書かれたn舞の紙切れが袋に入っています。あなたはこの袋から紙切れを取り出し、数字を見て袋に戻すということを４回行い、４回の紙切れの数字を和がmになっていればあなたの勝ち、そうでなければ友人の勝ちになります。あなたはこのゲームに何度か挑戦しましたが、一度も勝つことができませんでした。怒ったあなたは袋を破り、滑れの紙切れを取り出して本当に勝つ可能性があるのかを調べることにしました。紙切れに書かれている数字がk1,k2,...knであったとき、和がmになる取り出し方が存在するかどうかを計算し、存在するならYes, 存在しないならNoと出力するプログラムを書きなさい。
＜制約＞1 <= n <= 50, 1 <= m <= 108(10の8乗）, 1<= k_i <= 108(10の8乗）
<例1>
<入力>n = 3
m = 10
k = {1, 3, 5}
<出力>Yes(例えば1,1,3,5のように出れば、和が10になる）
<例2>
<入力>n = 3
m = 9
a = {1, 3, 5}
<出力>No(和が9になるような出方は存在しない）
これを、ローカル環境で実行できる形に直そうとしたのが、以下のコードです。

コード
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 50;
int n, m, k[MAX_N];
//2つで作れる数を格納する配列
int kk[MAX_N * MAX_N];

bool binary_search(int x)
{
    //xの存在し得る範囲はkk[l],kk[l+1],....kk[r-1]
    int l = 0;
    int r = n * n;
    //範囲に何も含まれなくなるまで繰り返す
    while (r - l >= 1)
    {
        int i = (l + r) / 2;
        if (kk[i] == x)
        {
            return true;
            printf("a\n");
        }
        else if (kk[i] < x)
        {
            l = i + 1;
            printf("b\n");
        }
        else
        {
            r = i;
            printf("c\n");
        }
    }
    //見つからなかった
    return false;
    printf("d\n");
}
void solve()
{
    //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];
        }
    }
    //2分探索を行うためにソートする
    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");
}
int main()
{
    scanf("%d", &n);
    scanf("%d", &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &kk[i]);
    }
    solve();
    return 0;
}

コードを実行すると、
3
10
1 3 5の入力に対しても、NOになってしまいます。
binary_search関数の各箇所にprintf()を入力してみたところ、上記入力に対しては、bbbbbbbbbbbbbbbbbbbbbbbbbbbNO(表記上、改行を除く）と表示されました。
ということは、binary_search関数の周りでミスがあると思われるのですが、どう直せば良いのかどうしても分かりません。ご教授いただけますと幸いです。
どうぞよろしくお願いいたします。
なお、ローカル環境とは、mac OS High Sierra10.13.6
コンパイラは
Apple LLVM version 10.0.0 (clang-1000.10.44.4)
Target: x86_64-apple-darwin17.7.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin
になります。VSCodeを使っています。

行動規範の内容に同意します

回答1件

ベストアンサー

凡ミスです。

C++

int main()
{
...
for (int i = 0; i < n; i++)
{
scanf("%d", &kk[i]); // ⇒ scanf("%d", &k[i]);
}

コードの組み方

一通りコードを完成させてからバグを解消するのは困難です。
小さな、でも確かに動作するコードを組み立てていった方がスムーズでしょう。

######ステップ1： binary_search関数の実装と簡易なテスト
グローバル変数を使わないように少し改造してますが、ざっくりこんな感じで組みます。

C++
1bool binary_search(int sorted_arr[], size_t len, int purpose) {
2    int left  = 0;
3    int right = len;
4
5    while (right - left >= 1) {
6        int middle = (left + right) / 2;
7
8        if (sorted_arr[middle] == purpose) {
9            return true;
10        }
11
12        if (sorted_arr[middle] < purpose) {
13            left = middle + 1;
14        }
15        else {
16            right = middle;
17        }
18    }
19
20    return false;
21}

ダミーデータで動作を確認します。

C++
1int main(void) {
2    int arr[] = {1, 3, 5, 7, 9};
3    size_t len = std::size(arr);
4    
5    printf(
6        "%s\n", binary_search(arr, len,  3) ? "true" : "false"
7    );
8    printf(
9        "%s\n", binary_search(arr, len, 10) ? "true" : "false"
10    );
11}

実行結果 Wandbox

true
false

OK。
たまたま上手くいっている可能性も捨てきれませんが、何もしないよりはマシです。

######ステップ2： solve関数の前処理の実装と簡易なテスト
solve関数は、内部的にはいくつか処理に分かれています。
0. データを成形する前処理
0. サーチ
0. 結果の出力

ここでは、まず前処理だけを実装します。

C++
1void solve(int arr[], size_t len, int m)
2{
3    int work[MAX_N * MAX_N];
4    size_t valid_len = len * len;
5    
6    for(size_t i = 0; i < len; ++i) {
7        int offset = i * len;
8        
9        for(size_t j = 0; j < len; ++j) {
10            work[offset + j] = arr[i] + arr[j];
11        }
12    }
13
14    std::sort(work, work + valid_len);
15    
16    for(size_t i = 0; i < len; ++i) {
17        int offset = i * len;
18        
19        for(size_t j = 0; j < len; ++j) {
20            printf("%2d ", work[offset + j]);
21        }
22        printf("\n");
23    }
24}

そしてダミーデータでチェック。

C++
1int main(void) {
2    int arr[] = {1, 3, 5};        // できるだけ小規模に
3    size_t len = std::size(arr);
4    
5    solve(arr, len, -1);
6}

実行結果 Wandbox

prog.cc: In function 'void solve(int*, size_t, int)':
prog.cc:32:39: warning: unused parameter 'm' [-Wunused-parameter]
 void solve(int arr[], size_t len, int m)
                                   ~~~~^
 2  4  4 
 6  6  6 
 8  8 10

問題なさそうです。

######ステップ3： solve関数の本処理の実装と簡易なテスト
solve関数に機能を肉付けします。

C++
1bool solve(int arr[], size_t len, int m)
2    //
3    // 前処理
4
5    ...
6
7
8    //
9    // 本処理
10
11    for(size_t i = 0; i < len; ++i) {
12        for(size_t j = 0; j < len; ++j) {
13            
14            // 内側のループの代わりに2分探索
15            int purpose = m - arr[i] - arr[j];
16            
17            if(binary_search(work, valid_len, purpose)) {
18                return true;
19            }
20        }
21    }
22    
23    return false;
24}

そしてテスト。

C++
1int main(void) {
2    {
3        int arr[] = {1, 3, 5};
4        size_t len = std::size(arr);
5    
6        printf(
7            "%s\n", solve(arr, len, 10) ? "OK" : "NG"
8        );
9    }
10    {
11        int arr[] = {1, 3, 5};
12        size_t len = std::size(arr);
13    
14        printf(
15            "%s\n", solve(arr, len, 9) ? "OK" : "NG"
16        );
17    }
18}

実行結果 Wandbox

OK
NG

######ステップ4：値を入力できるようにする
ここでようやく標準入力を利用します。

C++
1int main(void) {
2    int arr[MAX_N];
3    
4    size_t arr_len; scanf("%zu", &arr_len);
5    int    purpose; scanf("%d",  &purpose);
6    
7    for(size_t i = 0; i < arr_len; ++i) {
8        scanf("%d", &arr[i]);
9    }
10    
11    bool found = solve(arr, arr_len, purpose);
12    printf("%s\n", found ? "OK" : "NG");
13}

完成。

細かにテストを挟むことで、バグ発生時の調査範囲は激減します。
今、目の前で実装したばかりのコードを重点的に調べれば良いなら、とても楽だと思いませんか。

もちろん、段階を踏んで作っていっても、過程のバグに気付けない場合もありますが。

コード

C++
1#include <cstdio>
2#include <cstdlib>
3
4#include <algorithm>
5
6
7constexpr int MAX_N = 50;
8
9bool binary_search(int sorted_arr[], size_t len, int purpose) {
10    int left  = 0;
11    int right = len;
12
13    while (right - left >= 1) {
14        int middle = (left + right) / 2;
15
16        if (sorted_arr[middle] == purpose) {
17            return true;
18        }
19
20        if (sorted_arr[middle] < purpose) {
21            left = middle + 1;
22        }
23        else {
24            right = middle;
25        }
26    }
27
28    return false;
29}
30
31bool solve(int arr[], size_t len, int m)
32{
33    //
34    // 前処理
35    
36    int work[MAX_N * MAX_N];
37    size_t valid_len = len * len;
38    
39    for(size_t i = 0; i < len; ++i) {
40        int offset = i * len;
41        
42        for(size_t j = 0; j < len; ++j) {
43            work[offset + j] = arr[i] + arr[j];
44        }
45    }
46
47    std::sort(work, work + valid_len);
48    
49    /*
50    for(size_t i = 0; i < len; ++i) {
51        int offset = i * len;
52        
53        for(size_t j = 0; j < len; ++j) {
54            printf("%2d ", work[offset + j]);
55        }
56        printf("\n");
57    }
58    */
59    
60    
61    //
62    // 本処理
63
64    for(size_t i = 0; i < len; ++i) {
65        for(size_t j = 0; j < len; ++j) {
66            
67            // 内側のループの代わりに2分探索
68            int purpose = m - arr[i] - arr[j];
69            
70            if(binary_search(work, valid_len, purpose)) {
71                return true;
72            }
73        }
74    }
75    
76    return false;
77}
78
79int main(void) {
80    int arr[MAX_N];
81    
82    size_t arr_len; scanf("%zu", &arr_len);
83    int    purpose; scanf("%d",  &purpose);
84    
85    for(size_t i = 0; i < arr_len; ++i) {
86        scanf("%d", &arr[i]);
87    }
88    
89    bool found = solve(arr, arr_len, purpose);
90    printf("%s\n", found ? "OK" : "NG");
91}

投稿2019/01/19 02:47

編集2019/01/19 03:48

LouiS0616

総合スコア35660

hon.ki

2019/01/19 12:52

LouiS0616さん、回答ありがとうございました。指摘いただいた箇所を修正したところ、無事ローカル環境でコードは正しく動きました。また、コードの組み方にも言及いただき、とても参考になりました。小さな、確かに動作するコードを組み上げていくという考え方はしたことがなかったので、これから気をつけていきます。また、グローバル変数を使わない書き方も勉強になりました。-std=c++2aで実行したのは初めてだったのですがC++のバージョンの違いによる文法の違いも、少しずつ知っていこうと思いました。改めて、回答本当にありがとうございました。

行動規範の内容に同意します