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

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

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

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

Q&A

1回答

1107閲覧

ABC212-Cの解答の修正

退会済みユーザー

退会済みユーザー

総合スコア0

C++

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

0グッド

0クリップ

投稿2021/08/08 09:19

前提・実現したいこと

Atcoderでc++を使って競技プログラミングを始めたものです(初心者なのでお恥ずかしながら茶よりの灰です...)
先日のABCのC問題で、ACにしたいのですがどうしてもそうならず分からなかったため質問させていただきます。別の解法ではACになるのでしょうが、できるだけこの解法がACになるように修正していただきたいです。もしこの解法自体に問題があってそれが出来なければ、それもお願いします。

###問題のリンク
https://atcoder.jp/contests/abc212/tasks/abc212_c

発生している問題

サンプル三つはACです。しかしそれ以外のテストケース20のうち12個がAC,8個はWAです。書いた時はTLEになるかもしれないと思いながら提出しましたが、そうではありませんでした。WAになる原因も謎ですが、TLEにならない理由も謎です。

該当のソースコード

C++

1#include <bits/stdc++.h> 2using namespace std; 3int main(){ 4 int a,b; 5 cin >> a >> b; 6 vector<int> A(a); 7 vector<int> B(b); 8 for(int i=0;i<a;i++){ 9 cin >> A[i]; 10 } 11 for(int i=0;i<b;i++){ 12 cin >> B[i]; 13 } 14 sort(A.begin(),A.end()); 15 sort(B.begin(),B.end()); 16 int mini=1000000001,itiji=0; 17 for(int i=0;i<a;i++){ 18 for(int j=0;j<b-1;j++){ 19 if(abs(A[i]-B[j])<=abs(A[i]-B[j+1])){ 20 itiji=abs(A[i]-B[j]); 21 goto A; 22 } 23 if(j==b-2){ 24 itiji=abs(A[i]-B[j+1]); 25 } 26 } 27 A: ; 28 mini=min(mini,itiji); 29 if(mini==0){ 30 break; 31 } 32 } 33 cout << mini << endl; 34}

試したこと

同じく競技プログラミングをやられている方に質問し、b=1の時にitijiが更新されないのではないかとアドバイスをいただいたので以下のようにしてみましたが、何も変わりませんでした。

C++

1#include <bits/stdc++.h> 2using namespace std; 3int main(){ 4 int a,b; 5 cin >> a >> b; 6 vector<int> A(a); 7 vector<int> B(b); 8 for(int i=0;i<a;i++){ 9 cin >> A[i]; 10 } 11 for(int i=0;i<b;i++){ 12 cin >> B[i]; 13 } 14 sort(A.begin(),A.end()); 15 sort(B.begin(),B.end()); 16 int mini=1000000001,itiji=0; 17 for(int i=0;i<a;i++){ 18 //ここから追加 19 if(b==1){ 20 itiji=abs(A[i]-B[0]); 21 goto A; 22 } 23 //ここまで 24 for(int j=0;j<b-1;j++){ 25 if(abs(A[i]-B[j])<=abs(A[i]-B[j+1])){ 26 itiji=abs(A[i]-B[j]); 27 goto A; 28 } 29 if(j==b-2){ 30 itiji=abs(A[i]-B[j+1]); 31 } 32 } 33 A: ; 34 mini=min(mini,itiji); 35 if(mini==0){ 36 break; 37 } 38 } 39 cout << mini << endl; 40}

###Atcoder公式解説の正解コード
参考までにどうぞ。

C++

1#include <bits/stdc++.h> 2using namespace std; 3 4#define N 200010 5#define INF 1010000000 6#define rep(i, n) for(int i = 0; i < n; ++i) 7 8int main(void) { 9 int n, m; 10 int a[N]; 11 int b[N]; 12 int ans = INF; 13 cin >> n >> m; 14 rep(i, n)cin >> a[i]; 15 rep(i, m)cin >> b[i]; 16 sort(a, a + n); 17 sort(b, b + m); 18 int x = 0; 19 int y = 0; 20 while ((x < n) && (y < m)) { 21 ans = min(ans, abs(a[x] - b[y])); 22 if (a[x] > b[y])y++; 23 else x++; 24 } 25 cout << ans << endl; 26 27 return 0; 28} 29

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

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

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

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

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

guest

回答1

0

とりあえず、WAになる原因が分かる入力例を挙げておきます。

以下の入力の場合、正しい出力は1ですが、提示のコードだと2になります。

text

11 3 23 31 1 2

投稿2021/08/08 09:58

編集2021/08/08 10:03
actorbug

総合スコア2224

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

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

退会済みユーザー

退会済みユーザー

2021/08/11 12:38

ありがとうございます!とても役に立ちます。またわかったことがあったらぜひお願いします。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
85.48%

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

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

質問する

関連した質問