前提・実現したいこと
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
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2021/08/11 12:38