予鈴

アウトプットとメモ書きの中間みたいな記事がたくさん出ます。

Codeforces Round #544 (Div. 3)　D. Zero Quantity Maximization

問題

解き直すと一瞬で通って悔しすぎるので、ここで供養しようと思います。
codeforces.com

解法

問題文に与えられた式を整理すると、
$d = \frac{-b[i]}{a[i]}$

任意の正の有理数は、ただ一つの既約分数を用いて表せるという性質を用いる。
mapのkeyを
$b[i] / gcd(b[i],a[i]) + yebityon + a[i] / gcd(b[i],a[i])$
のような文字列としてカウントアップしていけば良い。
ただし、
$b[i] <0 \land a[i] < 0$ 　の時は $d$ は負になり、
$b[i] >0 \land a[i] < 0$ 　と $b[i] <0 \land a[i] >0$ は値的には等しくなるので、注意。
$b[i] == 0 \land a[i] == 0$ の時は任意の $d$ に対して0になるので、別途数えてあとで足すと良い。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
using ld  = long double;
template<class T> T gcd(T a,  T b) {return b ? gcd(b, a % b) : a;}
template<class U> U lcm( U m, U n ){if((0LL == m )||( 0LL == n ))return 0; return ((m / gcd(m, n)) * n); }
signed main(){
    int n;
    cin >> n;
    vector<int>a(n);
    vector<int>b(n);
    for(auto& e : a) cin >> e;
    for(auto& e : b) cin >> e;
    map<string,int>mp;
    int res = 0;
    for(int i = 0; i < a.size(); i++){
        if(a[i] == 0 and b[i] == 0){
            res++;
            continue;
        }
        if(a[i] == 0)continue;
        int div = gcd(abs(a[i]),abs(b[i]));
        if((long double)b[i] * -1 / a[i]  >= 0){
            // d >= 0
            mp[to_string(abs(b[i]) / div) + "yebityon!" + to_string(abs(a[i])/div)]++;
        }else{
            // d < 0
            //分子を 負　にすることに統一
            mp[to_string(-1 * abs(b[i]) / div) + "yebityon!" + to_string(abs(a[i])/div)]++;
        }
    }
    int ans = 0;
    for(auto itr : mp){
        cmax(ans, itr.second);
    }
    cout << ans + res << endl;
    
}