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から始まるのが気持ち悪かったからってだけです．

#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 不老不死な人のコーヒーの悩み

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

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

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

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

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

#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を２進表記した場合に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