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時間以上もかかったのは自分でも信じられないほど。
自分には解法を導き出す力が足りないと思っていたが、今回の結果をみるとコードを書く力自体も足りないようだ。
来週の本選ではその点にも気を付けて参加してみようと思う。