ABC_046C AtCoderくんと選挙速報

Question

#ABC_046C AtCoderくんと選挙速報

##ceilの使い方について
以下の問題を解いている中でceilの使い方で不明点があるためアドバイスをいただけると幸いです。

##ABC_046C

シカのAtCoDeerくんは選挙速報を見ています。

選挙には二人の候補高橋くんと青木くんが出ています。
速報では、現在の二人の得票数の比が表示されていますが、得票数そのものは表示されていません。
AtCoDeerくんは N回画面を見て、 i(1≦i≦N)回目に見たときに表示されている比は Ti:Aiでした。
ここで、AtCoDeerくんが選挙速報の画面を1回目に見た段階で既にどちらの候補にも少なくとも一票は入っていたことがわかっています。
N回目に画面を見たときの投票数(二人の得票数の和)として考えられるもののうち最小となるものを求めてください。ただし、得票数が途中で減ることはありません。

自力では解くことができず解答を参考にしながら以下のように実装をしました。
今回問題となっているのか解答が示すn=max([A/x], [B/y])をどのように実装するかという問題です。

##解答

次に満たすべき比率かx:yだとすると、 A<=nx && B <= nyなるような最小の自然数nを取れば次にあり得る最小の得票数はnx, nyだとわかります。

このようなnはmax([A/x], [B/y])で計算できます。

##私の実装

私はnをceilを用いた計算で実装をしましたがこれでは不正解となってしまいました。
このceilを用いた式のどこに問題があるのかアドバイスをいただけると幸いです。
またこの場合はどのように実装するべきなのかもアドバイスをいただけるとありがたいです。
よろしくお願いいたします。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;

int main(){
    int N;
    cin >> N;
    vector<ll> t(N), a(N);
    for(int i=0; i<N; i++) {
        cin >> t[i] >> a[i];
    }


    ll T = 1, A = 1;
    for(int i=0; i<N; i++) {
        ll n = max(ceil((double)T/t[i]),ceil((double)A/a[i]));
        T = n * t[i];
        A = n * a[i];
    }
    cout << T + A << endl;
}

Answer 1

このceilを用いた式のどこに問題があるのかアドバイスをいただけると幸いです。

一般的な環境ではlong longは64ビット整数なのに対して、doubleの仮数部は53ビット相当なので、doubleに変換した瞬間に精度が失われることがあります。「10の18乗以下」という計算する値に対して、doubleの53ビット相当では有効数字が16桁弱しかなく、足りません。

またこの場合はどのように実装するべきなのかもアドバイスをいただけるとありがたいです。

単純にlong longをlong longで割れば、正の整数同士の除算は小数点以下が切り捨てとなります。

Comments

[encho]

大変わかりやすい説明ありがとうございます。

Answer 2

ll n = max(ceil((double)T/t[i]),ceil((double)A/a[i]));

切り上げだけの話でしたら次のような公式が使えます。

// 切り上げの公式
// 5 / 2 の切り上げ例
// x = (a+b-1)/b
//     (5+2-1)/2 = 3

ll n = max((T+t[i]-1)/t[i]),((A+a[i]-1)/a[i]);

参考にしたAC回答

問題ページ画面上のメニュータブの提出結果から問題名とACと自分の使う言語で検索してコード長と実効時間の速いものを上から順に数個見ると簡潔なコードが見つかるのでおすすめですよ。
十人十色のコードの書き方から学べることは多いです。

自分も以前解こうとして自力で無理だったので解説と回答だけ見てすっ飛ばしました。

Comments

[mjk]

問題で正解が出るかどうかなどは未検証です。

[encho]

こちらの切り上げ方法でACが出せました。
ありがとうございます！！