2011-09 << 2011-10 >> 2011-11

2011-10-01 (土)

*Google Code Jam Japan 2011 予選

Tシャツ欲しいのでやりました.

https://code.google.com/codejam/japan/

この日記読んでも雰囲気が伝わるかすら怪しいので,気になる人は自分で問題読むことをお勧めします.問題はcode jamのサイトで誰でも見れます.

13時開始だったけど,目が覚めて時計を見ると14時過ぎ…….まだ眠かったけど,14:20くらいに問題読み始める.

予選なので問題は簡単.しかも日本語だし楽勝.と思ったけど,Bで結構時間かかってしまった.

終わったのが15:48.

コンテスト終了後にスコア見たけど,全問大丈夫だった.始めたのが遅かったので順位は56位.来週も頑張れば一応Tシャツもらえそうだな.

A イカサマシャッフル

カードを指定された通りにシャッフルした場合,ある場所のカードが元々どこにあったかを答える問題.

カードの枚数が,10億(10^9)枚まであり得るので,実際にカードに番号を振って操作するのは危険.ただ,答えるのは指定された1枚なので,シャッフルが終わった状態から逆順に辿れば簡単.

最初に1引いておいて最後に1足しているのは,カードの番号が1から始まるのが気持ち悪かったからってだけです.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;
    
    for (int i=0;i<T;i++) {
        int m,c,w;
        cin >> m >> c >> w;
        
        vector<int> aa,bb;
        for (int j=0;j<c;j++) {
            int a,b;
            cin >> a >> b;
            aa.push_back(a-1);
            bb.push_back(b);
        }
        
        w -= 1;
        while (aa.size()) {
            int a = aa.back();
            int b =  bb.back();
            aa.pop_back();
            bb.pop_back();

            if (w<b) {
                w += a;
            } else if (w < a+b) {
                w -= b;
            }
        }

        cout << "Case #" << (i+1) << ": " << w+1 << endl;
    }

    return 0;
}

B 不老不死な人のコーヒーの悩み

複数種類のコーヒーについて,賞味期限と満足度と何杯分飲めるかが与えられて,1日一杯ずつ飲んだときの,満足度の合計の最大値を求める問題.

しかし,2兆(=2*10^12)日くらいコーヒーを飲み続ける不老不死な人が抱える問題のようなので32ビット整数に収まらないし,1日ごとに計算してたら間に合わない気がします.

2兆日っていうと,そろそろ太陽が燃え尽きて地球が無くなってるころですね.確かにたとえ不老不死であっても地球が無いとコーヒー飲んでる場合ではない…….

特に方針を決めないまま書き始めたら,少し面倒なプログラムになってしまった.コーヒーを飲むことが出来なくなる最期の日から,まだ飲めるコーヒーのうち満足度が最大なものを調べて,その前に賞味期限が切れるコーヒーと比べつつ,どの期間にどのコーヒーを飲むか決めるだけのプログラム.

事前に賞味期限と満足度でソートしたほうが多少短くなったかも.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;
    
    for (int i=0;i<T;i++) {
        unsigned long long n,k;
        cin >> n >> k;
        
        struct Coffee {
            unsigned long long c,t;
            int s;
        };
        vector<Coffee> cc;
        for (int j=0;j<n;j++) {
            Coffee c;
            cin >> c.c >> c.t >> c.s;
            cc.push_back(c);
        }
        
        unsigned long long d = k;
        long long ss = 0;
        while (d>0) {
            int ms = 0;
            int pos = 0;
            for (int j=0;j<n;j++) {
                if (cc[j].c > 0 && cc[j].t>=d && cc[j].s > ms) {
                    ms = cc[j].s;
                    pos = j;
                }
            }

            if (ms==0) {
                unsigned long long  md = 0;
                for (int j=0;j<n;j++) {
                    if (cc[j].c > 0 && cc[j].t < d && cc[j].t>md ) md = cc[j].t;
                }
                d = md;
                continue;
            }

            unsigned long long dd = d ,md = 0;
            for (int j=0;j<n;j++) {
                if (cc[j].c > 0 && cc[j].t<d && cc[j].t> md) {
                    dd = d-cc[j].t;
                    md = cc[j].t;
                }
            }
            
            if (dd > cc[pos].c) {
                dd = cc[pos].c;
            }
            if (dd > d) {
                dd = d;
            }
            
            ss += cc[pos].s * dd;
            cc[pos].c -= dd;
            d-=dd;
        }
        
        cout << "Case #" << (i+1) << ": " << ss << endl;
    }

    return 0;
}

C 64ビット整数扱えない言語とかもう使ってないよね?

整数 N が与えられて,a+b=N を満たす 0 以上の整数 a,b を選んで,aとbを2進表記した場合に1がたくさん含まれるようにする問題.

二進法の計算できるかというだけ?

A~Cの中で妙に簡単というか,本当にこれで良いのか疑って問題を何度も見直してしまった.

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    
    for (int i=0;i<T;i++) {
        int b = 0;
        unsigned long long n;
        for (cin>>n;n;n >>=1) {
            if ((n&1) == 0) {
                n--;
                b++;
                if (n&1) b++;
            } else {
                b++;
            }
        }
        cout << "Case #" << (i+1) << ": " << b << endl;
    }

    return 0;
}
2011-09 << 2011-10 >> 2011-11