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;
}