SRM449 DIV2 過去問

250 - MountainRoad

問題省略

一番左の始点から一番右の終点までの長さが直角三角形の斜辺になるので/sqrt(2)*2でおｋ
妙にさくっと解けたなと思ったら前やった問題だった。なんてこった

import java.util.*;
public class MountainRoad {
    public double findDistance(int[] s, int[] f) {
        int a = s[0];
        int b = f[0];
        for(int i : s){
            if(i<a) a = i;
        }
        for(int i : f){
            if(i>b) b = i;
        }
        return (b-a)*2/Math.sqrt(2);
    }
}

500 - OddDivisors

f()は、最も大きい奇数の約数を返す関数。整数Nが与えられるのでf(1)+f(2)+ ... f(N)求めろっていう問題。

計算量考えずにそのまんま求めようとしたらハイパーTLEタイム。お手上げだったのでtopcoder wikiの解説を参考にして書いた。
数学怖い

public class OddDivisors {
    public long findSum(int N) {
        return calc(N);
    }
    public long calc(long a){
        if(a==1) return 1L;
        if(a%2==1){
            return calc((a-1)/2) + oddSum(a);
        } else {
            return calc(a/2) + oddSum(a-1);
        }
    }
    public long oddSum(long a){
        return (a+1)/2 * (a+1)/2;
    }
}