Yak!の日記： Google Code Jam 2011 R1A, R1B
なんとか R1B 枠で通過しました。
R1A Problem A. FreeCell Statistics
数学。結構悩んでました。辿りついた考え方は次の通り。その日の勝利数/その日の試合数=PD/100⇔100×その日の勝利数=PD×その日の試合数となるのでPD×その日の試合数は100=2^2*5^2の倍数になる必要があります。PD と 100 の公約数を調べてその数で 100 を割ってやるとその日の試合数の最低値 nn が出ます。これが n より大きい場合、条件を満たすことは不可能です。なお↓のコードだと PD = 0 のケースを特別扱いしていませんがたまたまうまく行っているだけ(ちゃんと nn = 1 になります)でそこまで考えていたわけではないです。次にその日の試合数が nn だった場合のその日の勝利数 w を求めています。PG = 100 の場合、全て勝利である必要があり、PG = 0 の場合、勝利数 0 である必要があります。PG が 0 でも 100 でもない場合、PG / 100 の分母・分子にものすごく大きい数をかけてやれば (w + k) / (nn + l) (但し 0 ≦ k ≦ l, k はその日以外の勝利数、l はその日以外の試合数) で k, l を適当に設定して合わせることが必ずできます。ということで判断しているのですが、実際には w を求めなくても、PD = 0 か PD = 100 で判断すればいいだけですね。
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
ULL n, pd, pg; cin >> n >> pd >> pg;
string s;
if(pd == 0) {
if(pg != 100) s = "Possible";
else s = "Broken";
} else {
ULL d2 = 0, d5 = 0, pd_ = pd;
if(pd_ % 2 == 0) { ++d2; pd_ /= 2; }
if(pd_ % 2 == 0) { ++d2; pd_ /= 2; }
if(pd_ % 5 == 0) { ++d5; pd_ /= 5; }
if(pd_ % 5 == 0) { ++d5; pd_ /= 5; }
ULL nn = 1 * (d2 == 2 ? 1 : d2 == 1 ? 2 : 4) * (d5 == 2 ? 1 : d5 == 1 ? 5 : 25);
//cerr << "nn: " << nn << endl;
if(nn > n) {
s = "Broken";
} else {
ULL w = pd * nn / 100;
//cerr << "w: " << w << endl;
if(w != 0 && pg == 0) s = "Broken";
else {
if(w != nn && pg == 100) { s = "Broken"; }
else { s = "Possible"; }
}
}
}
cout << "Case #" << casenum+1 << ": " << s << endl;
}
return 0;
}
R1A Problem B. The Killer Word
シミュレーション的に実装しようとしてごりごり書いていてぎりぎりの時間くらいでコンパイルが通るようにはなったのですがロジックが間違っていました。文字候補リスト上で最後に確定される単語を返すように書いていて、明らかに使われない文字候補はスキップしてポイントが入らない、という点が抜けていました。全単語についてポイントを計算して最大値になる単語を返すよう修正すると通りました。Large についても手元の環境では 4 分くらいで実行できています。
実装的にはデータ構造をどうしようかで multimap とふらついたりして時間をロスしてしまいました。基本的には区別できない単語群を set として持って区別できるようになったら分割していく、1 つになったらそこで終了、という処理になっています。contest analysis で記述されているのもこれと同じような方法のようですね。Union-find の逆、みたいなイメージなのですがこれを効率的に実装できるデータ構造とかあるんでしょうか？各単語10文字以下なので単語中の各文字の使用位置をビットフラグで持って高速化しています。
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
UL n,m; cin >> n >> m;
vector<string> dic(n); for(auto &v : dic) { cin >> v; }
vector<vector<UL>> len(10);
REP(i, n) {
len[dic[i].size()-1].push_back(i);
}
vector<vector<UL>> pos(n, vector<UL>(26));
REP(i, n) {
REP(j, 26) {
UL temp = 0;
REP(k, dic[i].size()) {
if(dic[i][k] == 'a' + j) temp |= (1U << k);
}
pos[i][j] = temp;
}
}
vector<string> result;
REP(i, m) {
string l; cin >> l;
vector<UL> temp(n); iota(RNG(temp), 0);
set<UL> candidate(RNG(temp));
map<UL, UL> group, newgroup;
UL gidx = 0;
for(auto &v1 : len) {
for(auto &v2 : v1) {
group.insert(make_pair(v2, gidx));
}
++gidx;
}
vector<UL> points(n);
for(auto &ch : l) {
map<pair<UL, UL>, set<UL> > check;
vector<UL> gflag(gidx);
for(auto &v : candidate) {
//cerr << v << ':' << group[v] << ':' << pos[v][ch - 'a'] << endl;
check[make_pair(group[v], pos[v][ch - 'a'])].insert(v);
gflag[group[v]] |= pos[v][ch - 'a'] != 0;
}
for(auto &v : candidate) {
if(gflag[group[v]] && pos[v][ch - 'a'] == 0) ++points[v];
}
gidx = 0;
set<UL> removed;
for(auto &v : check) {
if(v.second.size() == 1) {
removed.insert(*v.second.begin());
} else {
for(auto &v2 : v.second) {
newgroup.insert(make_pair(v2, gidx));
}
++gidx;
}
}
for(auto &v : removed) { candidate.erase(v); }
swap(group, newgroup); newgroup.clear();
}
result.push_back(dic[max_element(RNG(points)) - points.begin()]);
}
cout << "Case #" << casenum+1 << ':';
REP(i, m) {
cout << ' ' << result[i];
}
cout << endl;
}
return 0;
}
R1A Problem C. Pseudominion
未着手
R1A まとめ
Qualification がゆるゆるだったのでその流れで行くのかと思ったらいきなり頬はったかれたかのような感じでした。コンディション的に寝不足でへろへろのひどい状態で、B のコード書いてる間に訳が分からなくなることもしばしば。最終的には A-Small、A-Large の 20 pts 1257 位で通過ならず。ただ B の基本方針は外れておらずボーダー的にも近いところではあったので R1B で通過できるんじゃないかな、という希望は残りました。
R1B Problem A. RPI
やるだけ。OWP が正しく解釈できたかどうかにかかっている気がします。ある意味英語ゲー。Large にしても計算量的に問題になるところもないでしょう。R1A 出た人の中にはこれでいいのか、と深読みしちゃった人も居るんじゃないでしょうか。
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
UL n; cin >> n;
vector<string> table(n); for(auto &v : table) { cin >> v; }
vector<long double> wp(n), owp(n), oowp(n);
REP(i, n) {
int num = 0, won = 0;
REP(j, n) {
if(table[i][j] == '1') {
++num; ++won;
int num2 = 0, won2 = 0;
REP(k, n) {
if(i != k) {
if(table[k][j] == '0') { ++num2; ++won2; }
else if(table[k][j] == '1') { ++num2; }
}
}
owp[i] += (long double)won2/num2;
}else if(table[i][j] == '0') {
++num;
int num2 = 0, won2 = 0;
REP(k, n) {
if(i != k) {
if(table[k][j] == '0') { ++num2; ++won2; }
else if(table[k][j] == '1') { ++num2; }
}
}
owp[i] += (long double)won2/num2;
}
}
wp[i] = (long double)won/num;
owp[i] /= num;
}
REP(i, n) {
int num = 0;
REP(j, n) {
if(table[i][j] != '.') {
++num;
oowp[i] += owp[j];
}
}
oowp[i] /= num;
}
cout << "Case #" << casenum+1 << ":" << endl;
REP(i, n) {
cout << fixed << setprecision(12) << 0.25*wp[i]+0.5*owp[i]+0.25*oowp[i] << endl;
}
}
return 0;
}
R1B Problem B. Revenge of the Hot Dogs
これも結構考えてました。当初はある位置での点の個数を n として必要な幅は (n-1)*d。左右に振り分けてこれがぶつからないグループに分けてグループ毎に計算すればいける？みたいなことを考えていましたが玉突き的にぶつかっていくケースがあるので独立に計算できないことに気づき考え込んでしまいました。で降ってきたのが光円錐のイメージ(光である必要は全然ないのですが)。速度は 1m/s で決まっているのである時刻 t のとき、ある位置を起点にした点群が移動可能な範囲は決まってしまいます。逆にこの範囲内なら自由に移動可能です。基本的にはこれが (n-1)*d の幅を持てばいいわけです。隣とぶつかるケースがあるのでその分だけ移動可能な範囲を制限してやるとある時刻 t で条件を満たすか判定できます。ということで二分探索で解くことが可能です。これに気付いた時にはキターって感じになりました。
実際には B-Large に落ちました。提出しようとするときに絶対誤差だけ見てループを回していて無限ループしていたのを相対誤差も見るようにして(8分以内に)直して提出したのですがそれでも落ちました。原因は check() の中の wall の初期値です。二分探索の初期値を大きくした分、この初期値も絶対値的に大きな値に変更する必要がありました。意味的には -inf なので -numeric_limits::max() にしておくべきだったかもしれません。浮動小数点に対する numeric_limits の意味ってどうだったっけ？というのがあって即値で書いてしまいました。
題意を満たすだけなら絶対誤差と相対誤差の両方が閾値を越えている(r - l > diff && (r -l) / r > diff)間 回せばいいのですが、出力結果的に切りが悪い数値が出るので固定回数回す分も入れた形になっています。こうするぐらいなら単に固定回数回してしまえばいいでしょうけど。
bool check(long double time, vector<LL> &pos, vector<LL> &num, UI d)
{
long double wall = -1.0e+20;
REP(i, pos.size()) {
if(pos[i] + time - max(wall, pos[i] - time) < (num[i]-1) * d) return false;
wall = max(wall, pos[i] - time) + num[i] * d;
}
return true;
}
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
UI c, d; cin >> c >> d;
vector<LL> pos(c);
vector<LL> num(c);
REP(i, c) {
cin >> pos[i] >> num[i];
}
const long double diff = 0.000000001;
long double l = 0, r = 1.0e+13, cent;
int i = 0;
while(r - l > diff && ++i < 1000) {
cent = (l+r)/2;
// cerr << l << ' ' << cent << ' ' << r << endl;
if(check(cent, pos, num, d)) {
r = cent;
} else {
l = cent;
}
}
cout << "Case #" << casenum+1 << ": " << fixed << setprecision(8) << cent << endl;
}
return 0;
}
R1B Problem C. House of Kittens
分割された各部屋の最小頂点数が答えになる、というのまでは当たりづけ。ただしこれもすぐに OK という話ではなくて隣接している部屋で共有するのは 2 点のみ、隣接している部屋を辿って同じ部屋に再び戻ってくることはない(言い換えると双対グラフが閉路を持たず木になっている)ため色の塗り分けを(双対グラフの葉側で)調整できて 4 頂点なのに 3 色でしか塗れない、といった状態が発生しないから、とまで考えての結果です。実は双対グラフどうこうも後付けで最初からそう考えられていれば多角形内部に点がないから双対グラフに閉路なくて当然だよね、という話でした。
で、各部屋をどうやって確認しようかということで自前で頑張ってコードを書こうかとしたのですがそこではたと気づきました。「これ、Google Code Jam じゃん」 そう、外部ライブラリが使用可能なわけです。ということで Boost Graph を確認すると正にそういう目的の関数 planar_face_traversal() がありました。これを使って色数を出力するところまではできたのですが、色分けまでできませんでした。planar embedding とか知らなかったので最初から BGL 使おうとしても辿り着けなかった可能性は高いです。しかも色塗りのコードで色々と思い違いをして試行錯誤しました。以下のコードでは双対グラフ(前述のように木になる)上を辿りつつ、最初は出来る限り色を使いつつ全色使った後は辺の両端が異なる色になるようにして塗っています。結局 contest analysis の方法に辿り着いた、という形でしょうか。
template<typename Graph>
struct dual_graph_visitor : public planar_face_traversal_visitor
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::edge_descriptor Edge;
void begin_face() {
vertices.push_back(vector<Vertex>());
edges.push_back(vector<Edge>());
}
void end_face() { }
void next_vertex(Vertex v)
{
vertices.back().push_back(v);
}
void next_edge(Edge e)
{
edges.back().push_back(e);
links[e].push_back(edges.size()-1);
}
vector<vector<Vertex>> vertices;
vector<vector<Edge>> edges;
map<Edge, vector<UI>> links;
};
template<typename T>
T absdiff(T a, T b) { return a > b ? a - b : b - a; }
int main(void)
{
ios_base::sync_with_stdio(false);
typedef adjacency_list
< vecS,
vecS,
undirectedS,
property<vertex_index_t, int>,
property<edge_index_t, int>
>
graph;
typedef graph_traits<graph>::vertex_descriptor Vertex;
typedef graph_traits<graph>::vertex_iterator VIterator;
typedef graph_traits<graph>::edge_descriptor Edge;
UI cases; cin >> cases;
REP(casenum, cases) {
int n, m; cin >> n >> m;
vector<int> u(m), v(m);
for(auto &val : u) { cin >> val; --val; }
for(auto &val : v) { cin >> val; --val; }
graph g(n);
REP(i, m) {
add_edge(u[i], v[i], g);
}
REP(i, n) {
add_edge(i, (i+1)% n, g);
}
property_map<graph, edge_index_t>::type e_index = get(edge_index, g);
graph_traits<graph>::edges_size_type edge_count = 0;
graph_traits<graph>::edge_iterator ei, ei_end;
for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
put(e_index, *ei, edge_count++);
typedef std::vector< Edge > vec_t;
std::vector<vec_t> embedding(num_vertices(g));
int idx = 0;
VIterator vi, vi_end;
for(tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
auto p = out_edges(*vi, g);
embedding[idx].assign(p.first, p.second);
sort(RNG(embedding[idx]), [&](Edge e1, Edge e2) { return target(e1, g) < target(e2, g); });
++idx;
}
dual_graph_visitor<graph> v_vis;
planar_face_traversal(g, &embedding[0], v_vis);
auto it = find_if(RNG(v_vis.vertices), [&](vector<Vertex> &v) { return v.size() == n; });
if(it == v_vis.vertices.end()) cerr << "Not found" << endl;
for(auto &v : v_vis.edges[it - v_vis.vertices.begin()]) {
v_vis.links[v].push_back(0); // 0 is dummy
}
for(auto it = v_vis.links.begin(); it != v_vis.links.end();) {
if(it->second.size() == 3) {
v_vis.links.erase(it++);
} else ++it;
}
v_vis.edges.erase(v_vis.edges.begin() + (it - v_vis.vertices.begin()));
v_vis.vertices.erase(it);
vector<UI> sizes(v_vis.vertices.size());
transform(RNG(v_vis.vertices), sizes.begin(), [](vector<Vertex>&s) { return s.size(); });
int colors = *min_element(RNG(sizes));
vector<int> color(n);
vector<bool> visited(v_vis.edges.size());
function<void(UI)> traverse = [&](UI face) {
if(visited[face]) return;
visited[face] = true;
vector<bool> used(colors);
auto colorize = [&](Vertex v, int idx) {
if(color[v] != 0) return;
REP(j, colors) {
if(!used[j]) {
color[v] = j+1;
used[j] = true;
break;
}
}
if(color[v] == 0) {
int vn = v_vis.vertices[face].size();
int c1 = color[v_vis.vertices[face][(idx+1)%vn]];
int c2 = color[v_vis.vertices[face][(idx+vn-1)%vn]];
if(c1 > c2) swap(c1, c2);
color[v] = c2 <= 2 ? c2 + 1 : c1 <= 1 ? 2 : 1;
}
};
for(auto vertex : v_vis.vertices[face]) {
if(color[vertex] != 0) used[color[vertex]-1] = true;
}
REP(i, v_vis.vertices[face].size()) {
colorize(v_vis.vertices[face][i], i);
}
for(auto edge : v_vis.edges[face]) {
if(v_vis.links.count(edge)) {
if(v_vis.links[edge][0] == face) {
traverse(v_vis.links[edge][1]);
} else {
traverse(v_vis.links[edge][0]);
}
}
}
};
traverse(0);
cout << "Case #" << casenum+1 << ": " << colors << endl;
REP(i, n) {
if(i != 0) cout << ' ';
cout << color[i];
}
cout << endl;
}
return 0;
}
R1B まとめ
A-Small、A-Large、B-Small の 35 pts で 828 位。B-Large も取っておきたかったところではありますが教訓を得た上で通過できたのでまぁ良しとしましょう。あれ？と引っかかったところを安易にスルーしない、といったところでしょうか。後、グラフ関連は弱いのでもう少し BGL を確認しておきたいです。
まとめ
なかなか C++0x ぽいコードが書けないですね。特に誘惑に負けて REP マクロを導入してしまったため余計にそちらに頼ってしまう感じです。Range-based for もそれなりに使えることは使えるんですが REP マクロの単純明快さには勝てないというか。型名無かったら自動的に auto とかにならないですかね。後、要素だけではなくて添字も欲しいケースが結構あるので。アダプタを噛ませるべきなのかもしれませんが。後、auto func = [&](...) {...} や function<...> func = [&](...) {...} はヘルパ関数作成用に結構有用なイディオムだと思うので今後とも使える時には使いそうです。
テンプレ
#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 <functional>
#include <cmath>
// 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>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/ref.hpp>
#include <boost/graph/planar_face_traversal.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
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()
#define REP(v, e) for(UI v = 0U; v < e; ++v)
#define REP_(v, s, e) for(UI v = s; v < e; ++v)
#define REPV(v, e) for(v = 0; v < e; ++v)
#define REPV_(v, s, e) for(v = s; v < e; ++v)
using namespace std;
using namespace boost;
template<class Integer>
inline boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer last)
{ return boost::irange(first, last); }
Google Code Jam 2011 R1A, R1B More ログイン