Atcorder Biginner Contest 156 C問題 Rally 座標上の平均値を求め、計算量を少なく解答したいです。

Question

Atcorder Biginner Contest 156 C問題 Rally　について

C言語で回答してみましたがテストケースが7/14個引っ掛かり、かつテストケースが非公開なためバグを発見できず困っています。

以下回答したコードです。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#pragma warning(disable : 4996) //_CRT_SECURE_NO_WARNINGS

int comp(const void* a, const void* b) {
	return *(int*)a - *(int*)b;
}

int main(void) {
	int n;
	int cnt = 0;
	int sum = 0;
	int* data;
	int list[100000];
	for (int i = 0;i < 100000;i++) {
		list[i] = 0;
	}
	scanf("%d", &n);
	data = (int*)malloc(sizeof(int) * n);
	for (int i = 0;i < n;i++) {
		scanf("%d", &data[i]);
		sum += data[i];
	}
	qsort(data, n, sizeof(int), comp);
	for (int i = sum / n;i <= data[n-1];i++) {
		for (int j = 0;j < n;j++) {
			list[cnt] += (data[j] - i) * (data[j] - i);
		}
		cnt += 1;
	}
	qsort(list, n, sizeof(int), comp);
	printf("%d", list[0]);
	free(data);
	data = NULL;
	return 0;
}

総当たりでも答えを出せるのですが、問題の構成上数直線上に並ぶ座標の平均値を求めた上で
計算した方がスマートだと考えました。

アルゴリズムに問題があるのか、はたまた凡ミスをしているのか不明なためご指摘いただけたら幸いです。宜しくお願い致します。

補足

OS windows 8 64bit

Comments

[SHOMI]

ABC156のテストケースは公開されていますが…
https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAA5YzjDimjUWN7gVj1AdykKa/ABC156?dl=0&subfolder_nav_tracking=1

[SHOMI]

https://atcoder.jp/posts/20
AtCoder 公式コンテストのテストケースは、今後すべて
https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=0
にアップロードされる予定です。

[SHOMI]

あなたの提出は以下だと思いますが、ケース名のin/outにテストケースのリンクがあります。
https://atcoder.jp/contests/abc156/submissions/13092059

Answer 1

qsort(list, n, sizeof(int), comp);

ココがダメかと．
list[]のうち使用した要素数がnを下回る場合に答えが0になる（list[]の使ってない要素には0が入っているからそれが最小値になる）．

---

座標の平均値を求めた上で計算

するのは良いのですが，その方法(forでたくさん計算している)が微妙に思います．
もしも「整数でない」Pを求めるとしたらそれは平均値そのものです．
なので，「整数縛りなP」の候補として考えるべきは２通りで済むのではないかと．