質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

1332閲覧

atcoder 155 d問題が解けない

goro_gnm

総合スコア42

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

1クリップ

投稿2020/03/19 14:57

atcoder155 d問題
https://atcoder.jp/contests/abc155/tasks/abc155_d
が解けません。解説動画を見て、そのコードは理解したのですが、なぜ自分のコードがだめなのかわかりません。

どこがだめなのかわからないので、教えてもらえると嬉しいです。

c++

1#include<iostream> 2#include<cmath> 3#include<algorithm> 4#include<vector> 5#define rep(i, n) for (int i=0; i<(n); i++) 6typedef long long ll; 7using namespace std; 8 9 10int main(){ 11 int N, K; cin >> N >> K; 12 vector<ll> A(N, 0); 13 int minus = 0, plus = 0; 14 rep(i, N) cin >> A[i]; 15 sort(A.begin(), A.end()); 16 rep(i, N){ 17 if(A[i] > 0) plus++; 18 else if(A[i] < 0) minus++; 19 } 20 ll a = max(abs(A[0]), abs(A[N-1])); 21 ll l = -a*a, r = a*a; 22 ll tot=0; 23 ll mid; 24 while(l+1 < r){ 25 ll limit_minus = 0; 26 ll limit_plus = N-1; 27 mid = (l+r)/2; 28 rep(i, N){ 29 if(A[i]<0){ 30 while(A[i]*A[limit_minus] > mid && limit_minus < N) limit_minus++; 31 tot += N-limit_minus; 32 }else{ 33 while(A[i]*A[limit_plus] > mid && limit_plus >= 0 ) limit_plus--; 34 tot += limit_plus+1; 35 } 36 } 37 rep(i, N){ 38 if(A[i]*A[i] <= mid) tot--; 39 } 40 tot /= 2; 41 if(tot < K) l = mid; 42 else r = mid; 43 tot = 0; 44 } 45 cout << r << endl; 46}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kazuma-s

2020/03/19 20:45

plus と minus を求めていますが、その値を使っていません。説明の追加をお願いします。
guest

回答1

0

ベストアンサー

C++

1 if(A[i]<0){ 2 while(A[i]*A[limit_minus] > mid && limit_minus < N) limit_minus++; 3 tot += N-limit_minus; 4 }else{ 5 while(A[i]*A[limit_plus] > mid && limit_plus >= 0 ) limit_plus--; 6 tot += limit_plus+1; 7 }

二分探索中のこの部分について、A = {-2, -1, 1, 2}, mid = 2 として考えてみると、
i = 0 の時、limit_minusは1となりtotに3が足されます。
i = 1 の時、limit_minusは1のままでtotに3が足されます。
しかし、i = 1の時にはtotに4が足されるべきです(Aの要素すべてに-1をかけると{2, 1, -1, -2}で、mid以下である要素の個数は4)。

これと同じことがmidがマイナスの場合のlimit_plusの動きにも当てはまります。mid = -2とすると、
i = 2 の時、limit_plusは0となりtotに1が足されます。
i = 3 の時、limit_plusは0のままでtotに1が足されます。
しかしi = 3の時にはtotに2が足されるべきです。


一番ネックなのはここだと思いますが、ほかにも多少問題があります。
一つは上のwhileの条件式で、インデックスの境界チェックはインデックスでアクセスする前にすべきです。境界チェックでランタイムエラーになる可能性があります。

C++

1while(A[i]*A[limit_minus] > mid && limit_minus < N) limit_minus++; 23while(limit_minus < N && A[i]*A[limit_minus] > mid) limit_minus++;

もう一つはKの値が32bitには収まらない可能性があることです。

投稿2020/03/19 19:51

yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問