Google Code Jam 2015 Round1Aに参加しました

結果はA-small + A-large + B-small = 26pts 2761位でした。
Round1B,Cで頑張ろうと思います。

Problem A「Mushroom Monster」

10秒間隔で皿に乗っているマッシュルームの個数が与えられて、２通りの方法で、食べたマッシュルームの個数の最小値を計算する問題。１番目は各時間で食べられる個数が自由な場合で、２番目は10秒間に一定数のマッシュルームを食べる場合です。
どちらもシミュレーションで解きました。1番目の方法は各時間のマッシュルームの個数の差をとって足すだけです。
2番目の方法では減っている個数の最大値が10秒間に食べる個数です。

ll mx(ll a, ll b) {
    return (a > b ? a : b);
}

int main() {
    int T;
    cin >> T;
    REP(t,T) {
        int n;
        cin >> n;
        vector<ll> m(n);
        REP(i,n) cin >> m[i];

        ll y=0,z=0;
        ll s=0;
        FOR(i,1,n) {
            y += mx(0, m[i-1] - m[i]);
            s = mx(s,m[i-1]-m[i]);
        }

        FOR(i,0,n-1) {
            z += (m[i]>s ? s : m[i]);
        }
        printf("Case #%d: %lld %lld\n",t+1,y,z);
    }
    return 0;
}

Problem B「Haircut」

※Smallしか解けない解法です（二分探索思いつかなかった）
N人目の客がどの理容師に髪を切ってもらうが求める問題。Nの制約が10^9であることに注意。
紙に書いてみると周期があることに気が付きました。周期は理容師の必要な時間の最小公倍数で求まります。その周期の範囲で何番目の客がどの理容師に当たるのかを求め、(N % 周期中の客の人数)番目を参照する、みたいな感じで解きました。

int gcd(int a, int b) {
    if(a<b) swap(a,b);
    while (b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int lcm(int a, int b) {
    return a / gcd(a,b) * b;
}

int lcm_n(vector<int> &numbers) {
    int l;
    l = numbers[0];
    for (int i = 1; i < numbers.size(); i++) {
        l = lcm(l, numbers[i]);
    }
    return l;
}

int main() {
    int T;
    cin >> T;
    REP(t,T) {
        int B,N;
        cin >> B >> N;
        vector<int> m(B);
        REP(i,B) cin >> m[i];

        int l = lcm_n(m);

        vector<int> a(1,-1);
        for(ll i=0;i<l;i++) {
            REP(j,B) {
                if(i % m[j] == 0) {
                    a.PB(j+1);
                }
            }
        }
        int k = (N % (a.size()-1));
        if(k==0) k=a.size()-1;
        int ans = a[k];
        printf("Case #%d: %d\n",t+1,ans);
    }
    return 0;
}