AGC023-A 備忘録 p.45
itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。
考察の流れ
かの有名な Zero-Sum Ranges に挑戦！累積和と知っている以上、すんなり AC 可能（予定）
累積和 -> ソート -> nC2 とさらっと書いて、サンプルも通ったので意気揚々と投げたところ WA…
その後も WA を重ね、他の方々の解説やソースを見るも、さっぱり AC できず驚異の 21WA
そしてついに AC！原因は、ソートするときの compare 関数オーバーフローでした
#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
#define NC2(n) ((n)>1 ? ((n)*((n)-1)) / 2 : 0)
int compare_ll(const void *a, const void *b){
// return *(ll*)a - *(ll*)b; // オーバーフロー
return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;
}
int main(){
ll n, t, a[200005], cnt=1, ans=0;
scanf("%lld",&n);
a[0]=0;
for(ll i=1; i<=n; i++){
scanf("%lld", &a[i]);
a[i] = a[i] + a[i-1];
}
qsort( a, n+1, sizeof(ll), compare_ll );
a[n+1]=-1;
for(ll i=0; i<=n; i++){
if( a[i] == a[i+1] ){ cnt++; }
else{
ans = ans + NC2(cnt);
cnt = 1;
}
}
ans = ans + NC2(cnt);
printf("%lld\n", ans);
return 0;
}まとめ
・今まで使っていた long long 型 の compare関数がまさかオーバーフローするとは想定できず敗北
・WA 数最高新記録を達成してしまったが、諦めなかったのは偉い、ということに
引き続き、のんびり精進します。