codelic（プログラミングサイト）のdemo taskの問題で、不正解コードのダメな箇所がわかりません。

Question

codelic（プログラミングサイト）のdemo taskの問題で、不正解コードのダメな箇所がわかりません。
答えに違いが出る理由を教えてほしいです。

問題文

• codelic（プログラミングサイト）のdemo task
• テストプログラムの入力値は非公開のためわかりません
• 問題文はこちらなどにものっています。

試したこと

• C1カバレッジでの動作確認は共に同じとなることを確認した
• codelic側テストプログラムでは、performance testは全件OK(4/4)した。一方、correctness test casesは1/5となり正しく期待値を出せていないケースがある
• 別の方法で正解コードは出せた。ただし、正解コードと不正解コードを比較してどこに問題があるのかわからない

code

//不正答コード
int solution(vector<int> &A) {
	int ans=1;
	int Asize=A.size();
	sort(A.begin(),A.end());

	//A[i]の最大値が0以下である場合は、1を返す。A={-1,-3}のケース;
	if(A[Asize-1]<=0) return 1;

	//A[]の最大値が1以上。A={-1,1,3,6,4,1,2};のケース
	for(int i=0; i<Asize;i++){
		if(ans>=A[i]){//条件①
		}else if((ans+1) ==A[i]){//条件②
			ans++;
		}else{//条件③
			return ++ans;
		}
	}

	//A={1,2,3}のケース、正の値がきちんと
	return ++ans;
}

不正答コードの、A={-1,1,3,6,4,1,2};のケースの動作の参考として、以下のスクリーンショットを添付します。

以下は、正解したコードになります。

//正答したコード
int solution(vector<int> &A) {
	int ans=1;
	int Asize=A.size();
	sort(A.begin(),A.end());

	// rep(i,Asize){
	for(int i=0; i<Asize;i++){
		if(A[i] <= 0){

		}else if(A[i] == ans){
			ans++;
		}
	}
	return ans;
}

code全文

//不正解コード
#define _GLIBCXX_DEBUG//配列外参照のデバッグ用

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

//1 <= int N <= 10^5
//int A[i]:-10^6 to 10^6
int solution(vector<int> &A) {
	int ans=1;
	int Asize=A.size();
	sort(A.begin(),A.end());

	//A[i]の最大値が0以下である場合は、1を返す。A={-1,-3}のケース;
	if(A[Asize-1]<=0) return 1;

	//A[]の最大値が1以上。A={-1,1,3,6,4,1,2};のケース
	for(int i=0; i<Asize;i++){
		if(ans>=A[i]){
		}else if((ans+1) ==A[i]){
			ans++;
		}else{
			return ++ans;
		}
	}

	//A={1,2,2,3}のケース
	return ++ans;
}

int main(){
	{vector<int> A={-1,1,3,6,4,1,2};
	cout << solution(A) << endl;}
	{vector<int> A={1,2,2,3};
	cout << solution(A) << endl;}
	{vector<int> A={-1,-3};
	cout << solution(A) << endl;}
	return 0;
}

Comments

[episteme]

どんな問題を解いたコードなのかわからん。

[ratera]

問題文の書き方がわかりづらくすみません。

問題文の箇所に2か所リンクを貼っていましたが、次回は他の方の書き方を調べたうえで、伝わりやすくしています。
（一応、問題に著作権があるようでしたのでベタ貼りすることは控えておりました。ご容赦ください）

Answer 1

こちらのケースをデバッガで追えばわかるでしょう。

    {vector<int> A = { 2 };
    cout << solution(A) << endl; }

Comments

[ratera]

ありがとうございます。理解できました。

自分の回答の穴を見つけられるようにもなりたいし、もっとバグの入り込む余地のないシンプルなアルゴリズムを考えられるようになりたい一問でした<m(_ _)m>

ご回答いただき、ありがとうございます。

[ratera]

【解決メモ】
以下のケースにおいて、ansの初期値が1のため、出力が3になるバグがあった。
ansの初期値を1にすると、A[i]が1を含んでいなかった場合に出力が1とならない。
>　 {vector<int> A = { 2 };
cout << solution(A) << endl; }

solution内の、ansの初期値を0にすることで、全ての正答ケースをパスすることを解決しました。

```c++
int solution(vector<int> &A) {
int ans=0;
int Asize=A.size();
sort(A.begin(),A.end());

//A[i]の最大値が0以下である場合は、1を返す。A={-1,-3}のケース;
if(A[Asize-1]<=0) return 1;

//A[]の最大値が1以上。A={-1,1,3,6,4,1,2};のケース
for(int i=0; i<Asize;i++){
if(ans>=A[i]){
}else if((ans+1) ==A[i]){
ans++;
}else{
return ++ans;
}
}

//A={1,2,2,3}のケース
return ++ans;
}
```

[actorbug]

一応、私がこちらのケースを思いついた時の流れを説明します。
・ソートされている前提なら、for文内の条件分岐に抜けはなさそう
・そうなると境界付近があやしい
・動作が変わる境界は 1 だから、1 をまたぐパターンをいくつか試してみよう
最初に思い付いたパターンは{0, 2}でした。

[ratera]

ありがとうございます。デキる方がどのような視点で原因を絞っていくのかは、とても参考になる情報です。

入力値であるA[i]の境界で考えると、0,1,2の境界を疑うのは仰るとおりでした。
１を飛ばした0,2のケースに気づけるかはまだ自信がもてていませんが、こちらもどうしたら気づけるか考えていこうと思います。

ご丁寧にアドバイスいただきありがとうございました！