AGC023-A 備忘録 p.45

itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。

A - Zero-Sum Ranges

考察の流れ

かの有名な 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 数最高新記録を達成してしまったが、諦めなかったのは偉い、ということに

引き続き、のんびり精進します。

#備忘録 #AtCoder #AGC #プログラミング #競プロ #C言語 #累積和 #組み合わせ