C++でcodelic（プログラミングサイト）のLesson5_4のMinAvgTwoSliceの問題の正解を参考に書いたコードで正解が出せない。

Question

codelic（プログラミングサイト）のLesson5_4のMinAvgTwoSliceの問題の正解したコードを参考に書き下したコードで正解が出せません。
答えに違いが出る理由を教えてほしいです。

このような場合は入力値をベースにデバッグするのが筋ですが、入力値がわからずどのように原因を探ればよいのか詰めの甘い状態です。宜しくお願いします。

問題

codelic（プログラミングサイト）のLesson5_4のMinAvgTwoSliceの問題

解き方のロジック補足

• 解き方は、２つまたは３つの連続する配列の平均値を測る。
• ４つ以上連続する配列においては、２つ連続または３つ連続の場合の方が必ず小さくなるため、平均値を確認する必要がない

入力と期待結果

明確なインプットはわかっていません。
以下のlarge_onesのケースだけ、誤った期待値が出力されています。（正答率90%です。)

比較すべき箇所のコードの抜粋

以下、 正解コード抜粋です

	//2・3つの連続する配列の平均値を求め、最小値を発見した場合に格納する。
	for (int i=0; i<A.size()-2; i++){
		float v1 = (float)(A[i]+A[i+1]+A[i+2])/3.0;
		float v2 = (float)(A[i]+A[i+1])/2.0;
		if(min>v1 || min>v2) {
			min=std::min(v1,v2);
			mi=i;
		}
	}
	//2要素で、配列の最後を足した場合のケースが漏れているため、追加している。
	if (min> (((A[A.size()-1]+A[A.size()-2])/2.0)))
	{
		return (A.size()-2);
	}

以下、不正解コード抜粋です

	//3つの連続する配列の平均値を求める。配列のサイズが2以下の場合は処理を行わないようにする
	if (A.size()>2){
	for (int i=0; i<A.size()-2; i++){
		float v1 = (float)(A[i]+A[i+1]+A[i+2])/3.0;
		if(min > v1) {
			min=v1;
			mi=i;
		}
	}
	}
	//2つの連続する配列の平均値を求める。
	for (int i=0; i<A.size()-1; i++){
		float v2 = (float)(A[i]+A[i+1])/2.0;
		if(min > v2) {
			min=v2;
			mi=i;
		}
	}

コード全体

以下、正解コードです

//回答url:https://app.codility.com/demo/results/trainingJ2X3EM-VKH/
//
// Task Score: 100%
// Correctness: 100%
// Performance: 100%
//Detected time complexity:

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#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>;

//2 <= int N <~10^6
//-10^5 <= int A[i] <=10^5
//Aはペア型ではなかった。 0 ≤ P < Q < N
	//A pair of integers (P, Q), such that 0 ≤ P < Q < N

//速度重視だと、こちらのコードの方が若干早いhttps://youtu.be/Xu_hTjFAauk=508
//解き方は、２つまたは３つの連続する配列の平均値を測る。
//４つ連続する場合においては、２つ連続または３つ連続の場合の方が必ず小さくなるため、平均値を確認する必要がない
int solution(vector<int> &A) {
	float min=INT_MAX;
	int mi=0;

	for (int i=0; i<A.size()-2; i++){
		float v1 = (float)(A[i]+A[i+1]+A[i+2])/3.0;
		float v2 = (float)(A[i]+A[i+1])/2.0;
		if(min>v1 || min>v2) {
			min=std::min(v1,v2);
			mi=i;
		}
	}
	//2要素で、配列の最後を足した場合のケースが漏れているため、追加している。
	if (min> (((A[A.size()-1]+A[A.size()-2])/2.0)))
	{
		return (A.size()-2);
	}
	return mi;
}

int main(){
	vector<int> B={4,2,2,5,1,5,8};
	cout << solution(B) << endl;
	return 0;
	vector<int> c={-1,-1,0,1,1,-1,-1};
	cout << solution(c) << endl;
	return 0;
}

以下、不正解コードです

//回答url:
//
// Task Score: 100%
// Correctness: 100%
// Performance: 100%
//Detected time complexity:

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
// #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>;

//2 <= int N <~10^6
//-10^5 <= int A[i] <=10^5
//Aはペア型ではなかった。 0 ≤ P < Q < N
	//A pair of integers (P, Q), such that 0 ≤ P < Q < N

//速度重視だと、こちらのコードの方が若干早いhttps://youtu.be/Xu_hTjFAauk=508
//解き方は、２つまたは３つの連続する配列の平均値を測る。
//４つ連続する場合においては、２つ連続または３つ連続の場合の方が必ず小さくなるため、平均値を確認する必要がない
int solution(vector<int> &A) {
	float min=INT_MAX;
	int mi=0;

	if (A.size()>2){
	for (int i=0; i<A.size()-2; i++){
		float v1 = (float)(A[i]+A[i+1]+A[i+2])/3.0;
		if(min > v1) {
			min=v1;
			mi=i;
		}
	}
	}
	for (int i=0; i<A.size()-1; i++){
		float v2 = (float)(A[i]+A[i+1])/2.0;
		if(min > v2) {
			min=v2;
			mi=i;
		}
	}
	return mi;
}

int main(){
	vector<int> B={4,2,2,5,1,5,8};
	cout << solution(B) << endl;
	return 0;
	vector<int> c={-1,-1,0,1,1,-1,-1};
	cout << solution(c) << endl;
	return 0;
}

Comments

[episteme]

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

[ratera]

ご指摘ありがとうございます。追加しました。
お手数おかけしてすみません。

Answer 1

問題によれば、平均が同じになったとき、一番若いindexを返す必要があります。不正解コードではそうならないことがありますね。
たとえば、3平均のmin, miが0, 100で、2平均のmin,miが0,10の時とかです。

Comments

[ratera]

ありがとうございます。理解できました！
その筋で考えてみてはいたのですが、早とちりで問題がないと誤った判断をしてしまっておりました。

貴重なお時間をいただき、ありがとうございます！

【解決したお話】
・計算中の値が、（3平均のmin, miが0, 100で、2平均のmin,miが0,10の時など）最小値は同じだが、最小となるインデックスが異なる場合に事象が発生する。
・不正解コードだと、3平均だけを扱った場合にmi(最小のインデックス)が100で更新され、2平均のmiの10で更新されるべき箇所が、最小値が同じ0であるため更新されずにバグとなる。

Answer 2

該当のロジックを追加し、ケースpathすることを確認できました。

	for (int i=0; i<A.size()-1; i++){
		float v2 = (float)(A[i]+A[i+1])/2.0;
		if(((min==v2) && (mi>i)) || (min > v2)) { //NG:このロジックに要注意
			min=v2;
			mi=i;
		}
	}