Yak!の日記: Google Code Jam 2011 Qualification Round
一応 GCJ は毎回書いてるようなので今回も書いてみます。一応無事全問正解でした。のんびり書いてたんであんまり意味はないですが。今回は C++0x で書いてみよう、というコンセプトで書いてます。共通分テンプレートは最後にあります。何となくマクロ使わない派だったのですが RNG だけ入れてしまいました。
Problem A. Bot Trust
まぁ、シミュレーションですね。そしてのっけから 0x 不要なコードです。珍しく読み取りながら計算してるコードで書きました。割と A 面倒みたいなコメントも見かけましたが結構きれいに書けたんじゃないでしょうか。ちなみに small 提出しようとしたら Case #x: の形式が違うって言われて慌てて時間内に修正して submit したりもしました。
inline UI absdiff(UI a, UI b) { return a > b ? a - b : b - a; }
int main(void)
{
ios_base::sync_with_stdio(false);
UI t; cin >> t;
for(UI i=0;i<t;++i) {
UI p[2] = { 1, 1 }, t[2] = { 0, 0 };
UI cur = 0, prev = 0;
UI n; cin >> n;
for(UI j=0;j<n;++j) {
char c; UI r; cin >> c >> r; cur = c == 'B' ? 0 : 1;
t[cur] = max(t[prev] + 1, t[cur] + absdiff(p[cur], r) + 1);
p[cur] = r; prev = cur;
}
cout << "Case #" << i+1 << ": " << t[cur] << endl;
}
return 0;
}
B. Magicka
これもまぁシミュレーションですね。とりあえず clear の意図がいまいちはっきりせず質問しましたが read more carefully みたいなこと言われました。言われるだろうとは思いましたが。他にも質問した人が居るようで問題文も途中で修正されたようです。コード的には素直に for ループで回せばいいのにあえて boost::irange とか使っちゃいました。カウンタ変数も使ってないのに(そういう警告も出ます)。C++0x だというなら unordered_set, unordered_map を使っても良かったかもしれません。後は、今回不要だったっぽいですが element list 中の base element の数をカウントしておいて毎回 list 舐めるのを回避してるくらい。そのせいもあってやたら長くなっちゃってますけど。
// Boost library can be retrieved from http://www.boost.org/
// I uses 1.46.1
#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>
template<class Integer>
inline boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer last)
{ return boost::irange(first, last); }
int main(void)
{
ios_base::sync_with_stdio(false);
vector<char> be = { 'Q', 'W', 'E', 'R', 'A', 'S', 'D', 'F' };
map<char, int> rbe;
for(auto i : IR(0U,be.size())) {
rbe.insert(make_pair(be[i], i));
}
UI t; cin >> t;
for(UI i=0;i<t;++i) {
map<pair<char, char>, char> comb;
UI c; cin >> c;
for(auto j : IR(0U,c)) {
string s; cin >> s;
comb.insert(make_pair(make_pair(s[0],s[1]), s[2]));
comb.insert(make_pair(make_pair(s[1],s[0]), s[2]));
}
multimap<char, char> opposed;
UI d; cin >> d;
for(auto j : IR(0U,d)) {
string s; cin >> s;
opposed.insert(make_pair(s[0],s[1]));
opposed.insert(make_pair(s[1],s[0]));
}
UI n; cin >> n;
string s; cin >> s;
// for(auto val: comb) { cerr << val.first.first << ',' << val.first.second << ':' << val.second << endl; }
// for(auto val: opposed) { cerr << val.first << ':' << val.second << endl; }
string result;
vector<int> count(be.size());
for(auto ch:s) {
//cerr << result << ':' << ch << endl;
if(!result.empty()) {
if(comb.count(make_pair(result.back(), ch))) {
char nch = comb[make_pair(result.back(), ch)];
--count[rbe[result.back()]];
result.back() = nch;
} else {
bool cleared = false;
//for(auto vv: count) { cerr << vv; } cerr << endl;
for(auto check: boost::make_iterator_range(opposed.equal_range(ch))) {
if(count[rbe[check.second]]) {
result.clear();
fill(RNG(count), 0);
cleared = true;
break;
}
}
if(!cleared) {
result.push_back(ch);
++count[rbe[result.back()]];
}
}
} else {
result.push_back(ch);
++count[rbe[result.back()]];
}
}
cout << "Case #" << i+1 << ": [";
bool flag = false;
for(auto v:result) { if(flag) cout << ", "; cout << v; flag = true; }
cout << ']' << endl;
}
return 0;
}
Problem C. Candy Splitting
今回、C++0x を使ったのはこのために有ったんだ!そんな問題(嘘)。Patrick は xor 計算しているので xor で総和とって 0 以外なら NO、そうでなければ(通常の和で)総和とったものから最小値を引けば OK。accumulate の初期値も make_tuple にして 戻り値を auto で受けるとさらに格好いい気がします、なんとなく。ここまで来ると lambda の引数の型指定も省略したくなってきますね。
int main(void)
{
ios_base::sync_with_stdio(false);
UI t; cin >> t;
for(UI i=0;i<t;++i) {
UI n; cin >> n;
vector<UI> v(n); for(auto &val:v){cin>>val;}
tuple<UI, UI, UI> tup(0, 0, v[0]); // xorsum, sum, min
tup = accumulate(RNG(v), tup, [](tuple<UI,UI,UI> t, UI n) {
return make_tuple(get<0>(t) ^ n, get<1>(t) + n, min(get<2>(t), n));
});
cout << "Case #" << i+1 << ": ";
if(get<0>(tup) != 0) {
cout << "NO" << endl;
} else {
cout << get<1>(tup) - get<2>(tup) << endl;
}
}
return 0;
}
Problem D. GoroSort
さて今回最大の鬼門。そもそも submit 数も少なくかつ small 正答率も少ない問題です。自分も本戦とかだと解けていないと思います。後付けで調べた用語も入れて自分の対処を説明すると、状態を置換とみなして、長さ n の巡回置換について期待値が n (n≧2)であることを計算で n=6 まで確かめた形になります。巡回置換(感覚的には「ばらばら」と表記される状態)の時には全部シャッフルが最良だろうという仮定の下で、ですが。n=3 の時は順列を書き下して 1,2,3 なら OK、一箇所だけ一致する 1,3,2、3,2,1、2,1,3 なら(exampleの説明と同様)後 2 回、2,3,1、3,1,2 ならもう一度やり直し。結果、期待値 a は a = 1/3! * 1 + 3/3! * (1 + 2) + 2/3! * (1 + a) と表され計算すると a = 3 になります。n=4 も書き下して計算すると期待値 4 になってひょっとしてと思い、n=5 はさすがに全部は書き下せなかったので、
- 5 箇所同じ場合
- 4 箇所だけ同じ場合(実際には無い)
- 3 箇所だけ同じ場合
- 2 箇所だけ同じ場合
- 1 箇所だけ同じ場合
- 残りが長さ2の巡回置換(swap)2つの場合
- 残りが長さ4の巡回置換の場合
として場合分け。実際にはこの辺までは巡回置換、のような発想はありませんでした。今回時間があるので n=6 でやろうとして k 箇所だけ同じ場合の数え方が思いつかず、(正確な用語としては脳内にはありませんでしたが)巡回置換という考え方に辿り着きました。
- 長さ1の巡回置換6個の場合
- 長さ1の巡回置換4個と長さ2の巡回置換1個の場合
- 長さ1の巡回置換2個と長さ2の巡回置換2個の場合
- 長さ2の巡回置換3個の場合
- …
という感じで場合分けして計算。長さ n の巡回置換の数は (n-1)! になります。円順列ってやつですね。これで計算して 6 になったのでこれは行くしかないな、と。ちなみに、n=5 辺りの計算でぴったり 5 になって正直感動してました。こういう考え方だったのでコードも無駄に素な巡回置換の積に分解して長さ 1 以外のものの長さを足す、という風になっています。実際には一致していない箇所を数えることに帰着されてしまうのですが。なお、巡回置換ではなく一致していない箇所の個数、をベースにして式を立てる場合だとその場合の数については Wikipedia の完全順列の項や、Wolfram Mathworld の Subfactorial、Partial Derangement の項にあるようです。
// Boost library can be retrieved from http://www.boost.org/
// I uses 1.46.1
#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>
template<class Integer>
inline boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer last)
{ return boost::irange(first, last); }
int main(void)
{
ios_base::sync_with_stdio(false);
UI t; cin >> t;
for(UI i=0;i<t;++i) {
UI n; cin >> n;
vector<UI> v(n); for(auto &val:v){cin>>val;--val;}
vector<char> flag(n);
UI result = 0;
for(auto idx : IR(0U,n)) {
if(!flag[idx]) {
flag[idx] = 1;
UI count = 1, idx_ = v[idx];
while(!flag[idx_]) {
flag[idx_] = 1; idx_ = v[idx_]; ++count;
}
if(count>1) result += count;
}
}
cout << "Case #" << i+1 << ": " << result << endl;
}
return 0;
}
共通テンプレート
#include <iostream>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <tuple>
#include <initializer_list>
#include <cmath>
typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;
#define RNG(v) (v).begin(), (v).end()
using namespace std;
Google Code Jam 2011 Qualification Round More ログイン