Google Code Jam Japan 2011 予選

Google Code Jam Japan 2011 予選に出場。
スコアは全問正解、誤答なし、ペナルティ5:31:41、918人中の145位でした。
ちなみに参加が遅かったわけではなく、ほぼ最初から参加してこのタイムです、コーディング遅いなぁ。

問題A. カードシャッフル

概要:1~Mまで順に並んだカードの山があり、上から何枚目から何枚目までを1番上に移動させる操作をなんどか行った後、上から指定枚数眼のカードの数字は何か、という問題。
提出したソースコード:

001 
002 #include <stdio.h>
003 #include <stdlib.h>
004 #include <math.h>
005 #include <limits.h>
006 
007 #include <iostream>
008 #include <fstream>
009 #include <string>
010 #include <vector>
011 #include <list>
012 #include <map>
013 #include <set>
014 #include <iterator>
015 #include <numeric>
016 #include <functional>
017 #include <algorithm>
018 #include <utility>
019 
020 // using boost C++ library Version 1.47.0>=
021 // http://www.boost.org/
022 #include <boost/assert.hpp>
023 #include <boost/foreach.hpp>
024 
025 typedef std::pair<unsigned int, unsigned int> cut;
026 
027 std::list<cut>::iterator CutFirst(std::list<cut> &card_list, unsigned int pos) {
028     unsigned int cur_pos = 1;
029     std::list<cut>::iterator it = card_list.begin();
030     while(it != card_list.end()) {
031         const unsigned int cur_size = 1 + it->second - it->first;
032         if(cur_pos <= pos && pos < cur_pos + cur_size) {
033             break;
034         }
035         cur_pos += cur_size;
036         ++it;
037     }
038     BOOST_ASSERT(it != card_list.end());
039     if(cur_pos != pos) {
040         it = card_list.insert(it, std::make_pair(it->first, it->first + (pos - cur_pos - 1)));
041         ++it;
042         it->first = it->first + (pos - cur_pos);
043     }
044     return it;
045 }
046 
047 void CutEnd(std::list<cut> &card_list, std::list<cut>::iterator start_it, unsigned int size) {
048     std::list<cut>::iterator it = start_it;
049     std::list<cut> insert_cut;
050     unsigned int cut_size = size;
051     while(cut_size > it->second - it->first + 1) {
052         cut_size -= it->second - it->first + 1;
053         insert_cut.push_back(*it);
054         it = card_list.erase(it);
055         BOOST_ASSERT(it != card_list.end());
056     }
057     const unsigned int cur_cut_size = it->second - it->first + 1;
058     if(cut_size == cur_cut_size) {
059         insert_cut.push_back(*it);
060         card_list.erase(it);
061     } else if(cut_size < cur_cut_size) {
062         insert_cut.push_back(cut(it->first, it->first + cut_size - 1));
063         it->first = it->first + cut_size;
064     } else {
065         BOOST_ASSERT(false);
066     }
067     card_list.insert(card_list.begin(), insert_cut.begin(), insert_cut.end());
068 }
069 
070 unsigned int GetCardNumber(unsigned int card_max, unsigned int get_index, const std::vector<cut> &cut_list) {
071     std::list<cut> card_list;
072     card_list.push_back(std::make_pair(1, card_max));
073     BOOST_FOREACH(const cut &cut_pair, cut_list) {
074         const std::list<cut>::iterator it = CutFirst(card_list, cut_pair.first);
075         CutEnd(card_list, it, cut_pair.second);
076     }
077     const std::list<cut>::iterator it = CutFirst(card_list, get_index);
078     return it->first;
079 }
080 
081 int main(unsigned int argc, const char * const *argv) {
082     if(argc != 2) {
083         return 0;
084     }
085     std::ifstream ifs(argv[1]);
086     if(!ifs.is_open()) {
087         return 0;
088     }
089     unsigned int t;
090     ifs >> t;
091     for(unsigned int i = 0; i < t; i++) {
092         unsigned int m, c, w;
093         ifs >> m >> c >> w;
094         std::vector<cut> cut_list(c);
095         BOOST_FOREACH(cut &ab, cut_list) {
096             ifs >> ab.first >> ab.second;
097         }
098         std::cout << "Case #" << (i+1) << ": " << GetCardNumber(m, w, cut_list) << std::endl;
099     }
100     return 0;
101 }

カードが最大で10^9枚になるので、配列ではメモリーが足りません。
しかしカット回数は最大でも100回なので、連番が維持されている物は最初と最後の番号だけ残して省略することで表現が可能です。
後は特に難しい所はないので、そのまま解くだけです。

問題B. 最高のコーヒー

概要:毎日珈琲を飲む人がいます。 各種珈琲について満足度/残量/賞味期限が与えられたとき、最大の満足度はいくつか。
提出したソースコード:

001 
002 #include <stdio.h>
003 #include <stdlib.h>
004 #include <math.h>
005 #include <limits.h>
006 
007 #include <iostream>
008 #include <fstream>
009 #include <string>
010 #include <vector>
011 #include <list>
012 #include <map>
013 #include <set>
014 #include <iterator>
015 #include <numeric>
016 #include <functional>
017 #include <algorithm>
018 #include <utility>
019 
020 // using boost C++ library Version 1.47.0>=
021 // http://www.boost.org/
022 #include <boost/assert.hpp>
023 #include <boost/foreach.hpp>
024 #include <boost/tuple/tuple.hpp>
025 
026 #define EMPTY_COFFEE    UINT_MAX
027 
028 struct coffee_tuple {
029     unsigned long long int count;
030     unsigned long long int last_time;
031     unsigned int manzoku;
032 };
033 struct nissuu_tuple {
034     nissuu_tuple(unsigned long long int start, unsigned long long int size, unsigned int coffee_id) : start(start), size(size), coffee_id(coffee_id) { }
035     unsigned long long int start;
036     unsigned long long int size;
037     unsigned int coffee_id;
038 };
039 
040 std::list<nissuu_tuple>::iterator GetEmptyPos(std::list<nissuu_tuple> &nissuu_list, unsigned long long int last, unsigned long long int max) {
041     std::list<nissuu_tuple>::iterator last_empty_it = nissuu_list.end();
042     for(std::list<nissuu_tuple>::iterator it = nissuu_list.begin(); it != nissuu_list.end(); ++it) {
043         if(it->start <= last && last < it->start + it->size) {
044             if(it->coffee_id == EMPTY_COFFEE) {
045                 if(it->start + it->size > last + 1) {
046                     const unsigned long long int start = it->start;
047                     const unsigned long long int insert_size = last - start + 1;
048                     it->start = start + insert_size;
049                     it->size -= insert_size;
050                     it = nissuu_list.insert(it, nissuu_tuple(start, insert_size, EMPTY_COFFEE));
051                 }
052                 last_empty_it = it;
053             }
054             break;
055         }
056         if(it->coffee_id == EMPTY_COFFEE) {
057             last_empty_it = it;
058         }
059     }
060     if(last_empty_it == nissuu_list.end()) {
061         return nissuu_list.end();
062     }
063     std::list<nissuu_tuple>::iterator ret = last_empty_it;
064     if(max < ret->size) {
065         const unsigned long long int insert_size = ret->size - max;
066         ret = nissuu_list.insert(ret, nissuu_tuple(ret->start, insert_size, EMPTY_COFFEE));
067         ++ret;
068         ret->start += insert_size;
069         ret->size = max;
070     }
071     return ret;
072 }
073 
074 void Drink(std::list<nissuu_tuple> &nissuu_list, coffee_tuple coffee, unsigned int coffee_id) {
075     while(coffee.count > 0) {
076         std::list<nissuu_tuple>::iterator it = GetEmptyPos(nissuu_list, coffee.last_time, coffee.count);
077         if(it == nissuu_list.end()) {
078             break;
079         }
080         it->coffee_id = coffee_id;
081         coffee.count -= it->size;
082     }
083 }
084 
085 struct SortManzoku {
086     bool operator()(const coffee_tuple &left, const coffee_tuple &right) const {
087         return left.manzoku > right.manzoku;
088     }
089 };
090 
091 unsigned long long int GetManzoku(unsigned long long int nissuu, std::vector<coffee_tuple> &coffee_list) {
092     std::sort(coffee_list.begin(), coffee_list.end(), SortManzoku());
093     std::list<nissuu_tuple> nissuu_list;
094     nissuu_list.push_back(nissuu_tuple(1, nissuu, EMPTY_COFFEE));
095     unsigned int id = 0;
096     BOOST_FOREACH(coffee_tuple &coffee, coffee_list) {
097         Drink(nissuu_list, coffee, id);
098         id++;
099     }
100     unsigned long long int ret = 0;
101     BOOST_FOREACH(nissuu_tuple &nissuu, nissuu_list) {
102         if(nissuu.coffee_id == EMPTY_COFFEE) {
103             continue;
104         }
105         ret += nissuu.size * coffee_list[nissuu.coffee_id].manzoku;
106     }
107     return ret;
108 }
109 
110 int main(unsigned int argc, const char * const *argv) {
111     if(argc != 2) {
112         return 0;
113     }
114     std::ifstream ifs(argv[1]);
115     if(!ifs.is_open()) {
116         return 0;
117     }
118     unsigned int t;
119     ifs >> t;
120     for(unsigned int i = 0; i < t; i++) {
121         unsigned int n;
122         unsigned long long int k;
123         ifs >> n >> k;
124         std::vector<coffee_tuple> coffee_list(n);
125         BOOST_FOREACH(coffee_tuple &coffee, coffee_list) {
126             unsigned long long int c, t;
127             unsigned int s;
128             ifs >> c >> t >> s;
129             coffee.count = c;
130             coffee.last_time = t;
131             coffee.manzoku = s;
132         }
133         std::cout << "Case #" << (i+1) << ": " << GetManzoku(k, coffee_list) << std::endl;
134     }
135     return 0;
136 }

intでは収まりきらない数値を扱うのでオーバーフローに注意が必要。
Aと同じく日数が2*10^12なので、配列ではなく期間の始点と長さの形で表現しています。
問題自体は満足度の高い珈琲から順に出来る限り賞味期限ぎりぎりに飲むようにするだけで解くことができます。

問題C. ビット数

概要:数値Nが渡されたとき、a+b=Nが成り立つaとbにおいて、二進数表記した時に1が現れる個数が最大の組み合わせを探し、その1の個数を返せ。
提出したソースコード:

001 
002 #include <stdio.h>
003 #include <stdlib.h>
004 #include <math.h>
005 #include <limits.h>
006 
007 #include <iostream>
008 #include <fstream>
009 #include <string>
010 #include <vector>
011 #include <list>
012 #include <map>
013 #include <set>
014 #include <iterator>
015 #include <numeric>
016 #include <functional>
017 #include <algorithm>
018 #include <utility>
019 
020 // using boost C++ library Version 1.47.0>=
021 // http://www.boost.org/
022 #include <boost/assert.hpp>
023 #include <boost/foreach.hpp>
024 
025 unsigned int GetMaxBitNumber(const std::vector<unsigned long long int> &ans_list, unsigned long long int n) {
026     for(unsigned int i = 0; i < ans_list.size(); i++) {
027         if(ans_list[i] > n) {
028             BOOST_ASSERT(i > 0);
029             return i - 1;
030         }
031     }
032     return ans_list.size() - 1;
033 }
034 unsigned int GetBit(unsigned long long int n) {
035     unsigned int ret = 0;
036     for(; n > 0; n /= 2) {
037         if(n%2 == 1) {
038             ret++;
039         }
040     }
041     return ret;
042 }
043 unsigned int GetMinBitNumber(const std::vector<unsigned long long int> &bit, unsigned long long int n) {
044     for(unsigned int i = 0; i < bit.size(); i++) {
045         if(bit[i] == n) {
046             return i;
047         }
048         if(bit[i] > n) {
049             BOOST_ASSERT(i > 0);
050             return i - 1;
051         }
052     }
053     return bit.size() - 1;
054 }
055 unsigned int GetBitNumber(const std::vector<unsigned long long int> &bit, const std::vector<unsigned long long int> &ans_list, unsigned long long int n) {
056     const unsigned int max = GetMaxBitNumber(ans_list, n);
057     if(ans_list[max] == n) {
058         return max;
059     }
060     const unsigned int min = GetMinBitNumber(bit, n);
061     unsigned int ret = 0;
062     for(unsigned int i = 0; i <= min; i++) {
063         ret = std::max(ret, i + GetBit(n - bit[i]));
064     }
065     return ret;
066 }
067 
068 int main(unsigned int argc, const char * const *argv) {
069     std::vector<unsigned long long int> bit;
070     for(unsigned int i = 0; i < 64; i++) {
071         if(i == 0) {
072             bit.push_back(0);
073             continue;
074         }
075         bit.push_back(bit.back()*2+1);
076     }
077     std::vector<unsigned long long int> ans_list;
078     for(unsigned int i = 0; i <= 124; i++) {
079         if(i == 0) {
080             ans_list.push_back(0);
081             continue;
082         }
083         const unsigned int index = i / 2;
084         if(i%2 == 1) {
085             ans_list.push_back(bit[index] + bit[index + 1]);
086         } else {
087             ans_list.push_back(bit[index] * 2);
088         }
089     }
090 
091     if(argc != 2) {
092         return 0;
093     }
094     std::ifstream ifs(argv[1]);
095     if(!ifs.is_open()) {
096         return 0;
097     }
098     unsigned int t;
099     ifs >> t;
100     for(unsigned int i = 0; i < t; i++) {
101         unsigned long long int n;
102         ifs >> n;
103         std::cout << "Case #" << (i+1) << ": " << GetBitNumber(bit, ans_list, n) << std::endl;
104     }
105     return 0;
106 }

Nが最大で10^18になるのでオーバーフローに注意が必要。
なぜかNの下限が制約に記されていませんが、問題文中に正の整数とあるので0<=N<=10^18と解釈していいと思われる。 aかbのうち片方を全て1が並ぶ数値にし、もう片方を余りとして計算する総当たりで解いている。 中途半端に枝刈りをしているが、計算量から考えて明らかに無駄、総当たりでも何ら問題はない。 (どんなに大きくても64回計算すれば答えが出る計算、一回当たりの計算量もたかが知れているため、最適化するだけ無駄) どれも問題を読んで大まかな流れを決めるまではすぐだったが、実際組んでみたらボロが出るの連続。 たとえばデータ構造にしても、あとからメンバーを足したり減らしたり、まるで違うクラスにしたりといったミスが目立った。 正直、この内容で5時間以上もかかったのは自分でも信じられないほど。 自分には解法を導き出す力が足りないと思っていたが、今回の結果をみるとコードを書く力自体も足りないようだ。 来週の本選ではその点にも気を付けて参加してみようと思う。