//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舞の紙切れが袋に入っています。あなたはこの袋から紙切れを取り出し、数字を見て袋に戻すということを4回行い、4回の紙切れの数字を和が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件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/01/19 12:52