perogram

D. Zero Quantity Maximization 〜doubleの精度〜

Quiz

https://codeforces.com/contest/1133/problem/D

Submit

https://codeforces.com/contest/1133/submission/50980508

Note

  • b/aが一致するものの個数の最大値が答え
  • a==0は別対応する

落とし穴

  • コンテスト中、test 37でWA
  • doubleを使っていたが精度に疑いあり
  • floatで逆に精度を落としてみる→WA
  • コンテスト後、long doubleを試す→AC
    • そこかぁ・・・

学び

  • ほぼ通っている&小数を使っているなら精度の可能性あり
  • long doubleを試してみよ

追記:比はGCD

  • kmjpさんの提出を見てみると、gcdをとって割っている
    • 4:12
    • 1:3
    • 23: 69
    • どれもGCDをとって割れば同一
  • なるほど、こうすれば小数は出てこないので精度におびえる心配もない
int A[202020],B[202020];

void solve() {
    int i,j,k,l,r,x,y; string s;
    
    cin>>N;
    FOR(i,N) cin>>A[i];
    FOR(i,N) cin>>B[i];
    FOR(i,N) {
        if(B[i]==0) {
            Z++;
            if(A[i]==0) Z2++;
        }
        else if(A[i]) {
            if(A[i]<0) A[i]=-A[i],B[i]=-B[i];
            int g=__gcd(abs(A[i]),abs(B[i]));
            A[i]/=g;
            B[i]/=g;
            M[{A[i],B[i]}]++;
        }
    }
    
    int ma=Z;
    FORR(m,M) ma=max(ma,Z2+m.second);
    cout<<ma<<endl;
}