ARC037 C-億マス計算

【問題】

arc037.contest.atcoder.jp

【方針】

K 番目に小さい値を求める問題 (CodeForces 191E) を最近やっていて、それと同じく二分探索でやるのかなと最初に思う。ちょっと考えたら、ある値 S より小さいようなマス目の値は std::set で簡単に求まりそうなので、実装する。難なく AC と思ったものの、なぜか 2 つのケースで落ちて通らない。コードを見直してみたけれど、致命的な欠点は見つからない。そこで同じようなミスをしてる人のコードを submission からいくつか見てみて、二分探索での upper_bound の値を 1e18+1 (1≦a,b≦10^9 なので、マス目の値がこれ以上になることはないはず) から 1e19 にしたところ AC。Twitter で聞いたところによると、e による指数演算は内部で数を double 型で持っていて、精度が高々 16 桁程度しか保証されていないらしい (いわゆる情報落ち誤差で +1 が無視されてた)。で、数をそのまま愚直にリテラルで書くか、1e18L+1 みたいに long double 型に変換してから加算すればちゃんと動く。C++ 使って 1 年くらいになるけど、全く知らなかった。

【コード】

1. int main() {
2. ios::sync_with_stdio(false);
3. ll n,k;
4. cin>>n>>k;
5. vector<ll> a(n);
6. vector<ll> b(n);
7. REP(i,n) cin>>a[i];
8. REP(i,n) cin>>b[i];
9. sort(ALL(a));
10. sort(ALL(b));
11. ll lb=1,ub=1e18L+1;
12. while(ub-lb>1) {
13. ll mid=(lb+ub)/2;
14. ll cnt=0;
15. REP(i,n) {
16. ll thr=(mid-1)/a[i];
17. auto ite=upper_bound(ALL(b),thr);
18. cnt+=n-(int)(b.end()-ite);
19. }
20. if(cnt<k) lb=mid;
21. else ub=mid;
22. }
23. cout<<lb<<endl;
24. }

【使ったアイデア】

K 番目に小さい値を二分探索で見つける (自分より小さい値が K 個未満しかないような最大の値が、K番目に小さい値)。

【得た知見】

e を使って指数演算をするときは型に気をつける。