[Codeforces 1133D] Zero Quantity Maximization

[Codeforces 1133D] Zero Quantity Maximization - 1500

그닥 어려운 문제는 아니지만 stl을 잘 사용하는게 중요한 문제이다. 문제는 c=d*a+b=0을 만족시키는 특정 d값이 있을 때 그 d를 가지는 (a,b) pair가 최대 몇 개인지를 구하는 문제이다. 간단하게 생각해보면 a/b를 실수형으로 구해서 해당 a/b와 동일한 값을 가지는 pair가 총 몇개인지 구하면 되는데 a,b의 범위가 최대 10억씩이기 때문에 소수의 정밀도 오차문제가 생긴다. 따라서 단순하게 a에서 b를 나누는 방식은 위험하다. 그래서 나는 소수형태가 아닌 분자와 분모형태로 표현할 수 있는 분수로 표현해야 한다. 분수로 표현을 하기 위해서는 모든 분수를 기약분수의 형태로 표현해야 한다. 1/2나 2/4나 100/200 모두 같은 값을 가지기 때문이다. 그래서 a와 b의 최대공약수를 구해서 각각 나눠주어야 한다. 그리고 또 한가지 해결해야 할 점은 분수를 저장할 자료구조이다. 단순 2차원 배열로 저장한다면 10억*10억개를 차지하므로 메모리가 초과된다. 이럴 때 사용하는 stl이 바로 map<pair<int,int>,int>이다. map의 first로 pair<int,int>를 두는 것인데 pair의 first를 분자, second를 분모로 두면 되고 map의 second가 개수가 되는 것이다. 이렇게 하면 분수를 저장하거나 검색할 때마다 O(logN)이 소요된다.

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
#define SIZE 200009
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
 
 
 
int a[SIZE],b[SIZE];
map<pii,int> mmap;
 
int gcd(int a,int b){
    return (b==0)?a:gcd(b,a%b);
}
 
int main(){
    int n;  scanf("%d",&n);
 
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&a[i]);
    }
    for(int i=1 ; i<=n ; i++)
        scanf("%d",&b[i]);
 
    int zero=0;
    for(int i=1 ; i<=n ; i++){
        if(a[i]==0 && b[i]!=0) continue;
        if(a[i]<0){
            a[i]*=-1,b[i]*=-1;
        }
 
        if(a[i]==0 && b[i]==0){
            zero++;
            continue;
        }
        int G=gcd(abs(a[i]),abs(b[i]));
        mmap[{a[i]/G,b[i]/G}]++;
    }
 
    int ans=0;
 
    for(auto here:mmap){
        ans=max(ans,here.second);
    }
 
    printf("%d\n",ans+zero);
    return 0;
}