[Codeforces] Round #544 D. Zero Quantity Maximization

Zero Quantity Maximization

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

方針

\( d \) を求める

\( 0 = da_i + b_i \) を満たす \( d \) を考えます。

  • \( a_i = 0\) かつ \( b_i = 0 \) のとき

\( d \) は任意の実数となります。

  • \( a_i = 0\) かつ \( b_i \neq 0 \) のとき

上記を満たす \(d\) は存在しません。

  • \( a_i \neq 0 \) のとき

\( d = -\dfrac{b_i}{a_i} \) となります。

\( d \) の頻度を求める

\( d \) をキーとして頻度を求めることにします。このとき、\( d \) は既約分数として表すことに注意します。また、\( d \) は任意の数を取るので、求めた頻度の最大値に任意の数を取るときの頻度を足す必要があります。

コード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする