2011 Google Code Jam 小记
好久没写这种类型的代码，感觉真是退步了很多。 这是我第一次参加Google Code Jam，以前有过报名可是没有做过。 我发现Google Code Jam的题目使用经典算法的几乎没有，都是模拟或者数学题（起码我目前做过的几题是这样）
首先是Qualification Round 四道水题，前两道模拟，后两道数学推公式。 第三道是位运算的，第四道由于那天没空了就没做，反正分数够了，听人说也是推公式的水题。 题目链接：http://code.google.com/codejam/contest/dashboard?c=975485
// Qualification Round -- A
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
namespace gcj {
using namespace std;
struct rebot {
int passTime;
int position;
};
queue<bool> all;
queue<int> qo, qb;
void solve () {
int t, n, pos, time, tt;
char rot;
scanf("%d", &t);
rebot o, b;
for (int i = 0; i < t; i ++) {
while(qo.empty() == false)
qo.pop();
while(qb.empty() == false)
qb.pop();
o.passTime = b.passTime = 0;
o.position = b.position = 1;
time = 0;
scanf("%d", &n);
while (n --) {
scanf(" %c %d", &rot, &pos);
bool isO = (rot == 'O');
all.push(isO);
if (isO)
qo.push(pos);
else
qb.push(pos);
}
while (all.size() > 0) {
bool isO = all.front();
all.pop();
if(isO) {
tt = max(0, abs(qo.front() - o.position) - o.passTime) + 1;
time += tt;
b.passTime += tt;
o.position = qo.front();
o.passTime = 0;
qo.pop();
} else {
tt = max(0, abs(qb.front() - b.position) - b.passTime) + 1;
time += tt;
o.passTime += tt;
b.position = qb.front();
b.passTime = 0;
qb.pop();
}
}
printf("Case #%d: %d\n", i + 1, time);
}
}
}
int main () {
freopen("d:/A-large.in", "r", stdin);
freopen("d:/A-large.out", "w", stdout);
gcj::solve();
return 0;
}// Qualification Round -- B
#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <set>
#include <cmath>
namespace gcj {
using namespace std;
string ls;
map<char, char> combine[256];
map<char, char>::iterator comItr;
set<char> opposed[256];
//set<char>::iterator oppItr;
//int charNumber[256];
void init() {
ls.clear();
for (int i = 0; i < 256; i ++) {
combine[i].clear();
opposed[i].clear();
}
//memset(charNumber, 0, sizeof(charNumber));
}
void solve() {
int t, c, d, n;
char comStr[5], oppStr[5];
char input[105];
scanf(" %d", &t);
for (int i = 0; i < t; i ++) {
init();
scanf(" %d", &c);
for(int j = 0; j < c; j ++) {
scanf(" %s", comStr);
combine[comStr[0]][comStr[1]] = combine[comStr[1]][comStr[0]] = comStr[2];
}
scanf(" %d", &d);
for(int j = 0; j < d; j ++) {
scanf(" %s", oppStr);
opposed[oppStr[0]].insert(oppStr[1]);
opposed[oppStr[1]].insert(oppStr[0]);
}
scanf(" %d", &n);
scanf(" %s", input);
for(int j = 0; j < n; j ++) {
char key = input[j];
bool run = true;
//oppItr = opposed[key].begin();
if (ls.size() > 0) {
if ((comItr = combine[key].find(ls.back())) != combine[key].end()) {
//charNumber[ls.back()] --;
ls.pop_back();
ls.push_back(comItr->second);
//charNumber[comItr->second] ++;
run = false;
}
if (run) {
for (int k = 0; k < ls.size(); k ++) {
if (opposed[key].find(ls[k]) != opposed[key].end()) {
//ls = ls.substr(0, k);
ls.clear();
run = false;
}
}
}
//while (run && oppItr != opposed[key].end()) {
// if (charNumber[*oppItr] > 0) {
// while(ls.back() != *oppItr) {
// charNumber[ls.back()] --;
// ls.pop_back();
// }
// charNumber[ls.back()] --;
// ls.pop_back();
// run = false;
// }
// oppItr ++;
//}
}
if (run) {
ls.push_back(key);
//charNumber[key] ++;
}
}
printf("Case #%d: [", i + 1);
for (int j = 0; j < ls.size(); j ++) {
if (j > 0) {
putchar(',');
putchar(' ');
}
putchar(ls[j]);
}
puts("]");
}
}
}
int main () {
//freopen("d:/GCJ/B-large.in", "r", stdin);
//freopen("d:/GCJ/B-large.out", "w", stdout);
gcj::solve();
return 0;
}// Qualification Round -- C
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
namespace gcj {
using namespace std;
void solve() {
int t, n, min_val, sum_val, number, sum_xor;
scanf("%d", &t);
for (int i = 0; i < t; i ++) {
min_val = 1<< 20;
sum_val = sum_xor = 0;
scanf(" %d", &n);
for (int j = 0; j < n; j ++) {
scanf(" %d", &number);
sum_xor ^= number;
sum_val += number;
min_val = min(min_val, number);
}
if (sum_xor)
printf("Case #%d: NO\n", i + 1);
else
printf("Case #%d: %d\n", i + 1, sum_val - min_val);
}
}
}
int main () {
//freopen("d:/GCJ/C-large.in", "r", stdin);
//freopen("d:/GCJ/C-large.out", "w", stdout);
gcj::solve();
return 0;
}然后是Round 1A 2011 状态不好，能力有限，我只看了第一和第二题 题目链接：http://code.google.com/codejam/contest/dashboard?c=1145485 第一题是告诉你一个今天最大比赛数量、今天胜率、总胜率，问数据是否可能达到. 我的想法是正确的，只有在计算符合今日胜率的最小局数和考虑总胜率为100和为0的情况即可，其他经过我简单的证明都是可行的，但是在获取最小的满足“今天胜率”的今日比赛数量的时候少打了一组括号，并且每注意到大数据范围到10^15，直接导致小数据PASS，大数据挂掉. 后来看了大牛的代码发现他用了最大公约数来解这个值，非常好。 贴小数据代码，大数据只要换到64位整数即可
#include <cstdio>
#include <algorithm>
namespace gcj {
void print(int t, char* str) {
printf("Case #%d: %s\n", t, str);
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void solve() {
int t, n, pd, pg, d, g, l, r;
scanf("%d", &t);
for (int i = 0; i < t; i++) {
scanf("%d %d %d", &n, &pd, &pg);
d = gcd(pd, 100);
if ((pd < 100 && pg == 100)
|| (pd > 0 && pg == 0)
|| n < 100 / d)
print(i + 1, "Broken");
else
print(i + 1, "Possible");
}
}
}
int main () {
freopen("d:/GCJ/Round1/A-small-practice.in", "r", stdin);
freopen("d:/GCJ/Round1/A-small-practice.out", "w", stdout);
gcj::solve();
return 0;
}第二题是猜字游戏 看了大牛的代码，用了DFS，两次精妙的索引排序解决了。太强大了，我还有差距呵。
然后是Round 1B 2011 题目链接：http://code.google.com/codejam/contest/dashboard?c=1150485 这个发挥得比较好，拿到了晋级名额。 我也只写了两道题，但是方法都对，而且都是1A，最后一道题我发现只剩下25分钟了，而且很晚了，反正写不完就懒得写了 第一题是模拟，按题目说的做就好了，这题在大数据的时候freopen的路径写错了，结果我一直在想为什么会TLE，还好在提交限时的两分钟前看到了，马上改掉就ok了。
#include <cstdio>
#include <cstring>
namespace gcj {
using namespace std;
const int maxn = 105;
char mat[maxn][maxn];
double WP[maxn];
double WP_par[maxn][2];
double OWP[maxn];
double OOWP[maxn];
void solve() {
int t, n, c = 0;
scanf("%d", &t);
while (t --) {
c ++;
scanf("%d", &n);
for (int i = 0; i < n; i ++)
scanf("%s", mat[i]);
// WP
for (int i = 0; i < n; i ++) {
double sum = 0.0, win = 0.0;
WP_par[i][0] = WP_par[i][1] = 0.0;
for (int j = 0; j < n; j ++) {
if (mat[i][j] == '.')
continue;
sum += 1.0;
if (mat[i][j] == '1')
win += 1.0;
}
WP_par[i][0] = win;
WP_par[i][1] = sum;
WP[i] = win / sum;
}
// OWP
for (int i = 0; i < n; i ++) {
double sum = 0.0, win = 0.0;
for (int j = 0; j < n; j ++) {
if (mat[i][j] == '.')
continue;
sum += 1.0;
if (mat[i][j] == '1')
win += (WP_par[j][0]) / (WP_par[j][1] - 1.0);
else
win += (WP_par[j][0] - 1.0) / (WP_par[j][1] - 1.0);
}
OWP[i] = win / sum;
}
// OOWP
for (int i = 0; i < n; i ++) {
double sum = 0.0, win = 0.0;
for (int j = 0; j < n; j ++) {
if (mat[i][j] == '.')
continue;
sum += 1.0;
win += OWP[j];
}
OOWP[i] = win / sum;
}
// Output
printf("Case #%d:\n", c);
for (int i = 0; i < n; i ++) {
printf("%.12lg\n", 0.25 * WP[i] + 0.50 * OWP[i] + 0.25 * OOWP[i]);
}
}
}
}
int main() {
freopen("A-large.in", "r", stdin);
freopen("A-large.out", "w", stdout);
gcj::solve();
return 0;
}第二题是一个数学题，又是数学题，问最少多久能让任意两个热狗店距离不小于d，计算的时候只要考虑往一个方向走，然后最后答案除以2即可，因为运动是对称的。中途需要考虑的是两个相邻组的距离问题，然后对分散时间进行合并取大值，并考虑交叉的情况加上分开交叉情况的时间即可。又是64位整形，不过这次我注意到了。不过那个maxn貌似我忘记改成大数据的数字了，为什么过了，神奇的。
#include <cstdio>
#include <cstring>
#include <algorithm>
namespace gcj {
using namespace std;
const int maxn = 206;
typedef long long lld;
struct node{
lld p;
lld v;
};
bool cmp(const node& l, const node& r) {
return l.p < r.p;
}
node venders[maxn];
void solve() {
int t, n, _case = 0;
scanf("%d", &t);
while (t --) {
_case ++;
int d, c;
scanf("%d %d", &c, &d);
for (int i = 0; i < c; i ++)
scanf("%lld %lld", &venders[i].p, &venders[i].v);
sort(venders, venders + c, cmp);
lld tmp, tl, last;
lld sum = (venders[0].v - 1) * d;
for (int i = 1; i < c; i ++) {
tmp = (venders[i].v - 1) * d;
tl = venders[i].p - venders[i].v * d;
if (tmp > sum) {
last = venders[i - 1].p - (tmp - sum);
if(tl >= last)
sum = tmp;
else
sum = tmp + last - tl;
} else {
last = venders[i - 1].p;
if (tl >= last) {
lld _m = min(tl - last, sum - tmp);
venders[i].p -= _m;
} else {
sum += last - tl;
}
}
}
printf("Case #%d: %.1lf\n", _case, sum / 2.0);
}
}
}
int main() {
freopen("D:/GCJ/Round2/B-large.in", "r", stdin);
freopen("D:/GCJ/Round2/B-large.out", "w", stdout);
gcj::solve();
return 0;
}Round2期间正碰上期末考试，但是我还是来做了一下，很失望的没拿到衣服。感觉我的编码能力还差得远呐，因为AC两题应该就能拿到衣服了，可是遗憾在第二题。 A很简单，大意是一个人在一条路上走，可以跑t秒，告诉走路和跑步的速度，再有的是路上有n个不重叠的walkway，在walkway上的速度等于walkway的速度+当前速度，问最少几秒钟到终点。思路非常简单，就是要在walkway上加速尽量多的时间。有两种情况，一种是在没有walkway的路上跑步跑完了t秒，这种情况时间很好算。另一种是walkway之外的路上t秒没用完，这时后要尽量在速度快的walkway上加速，所以对walkway的速度排序就可以了。需要注意的情况就是从头跑到尾的情况。 A题代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
namespace gcj{
using namespace std;
const int MAXN = 1005;
struct walkway{
int b, e, w;
friend bool operator< (const walkway& l, const walkway& r) {
return l.w < r.w;
}
};
walkway cors[MAXN];
void solve(int T) {
int x, s, r, t, n;
int wwlen = 0, rlen;
double res = 0.0, rt;
scanf("%d %d %d %d %d", &x, &s, &r, &t, &n);
for (int i = 0; i < n; i ++)
scanf("%d %d %d", &cors[i].b, &cors[i].e, &cors[i].w), wwlen += cors[i].e - cors[i].b;
rlen = x - wwlen;
rt = t;
sort(cors, cors + n);
if(rlen >= t * r)
res = 1.0 * (rlen - t * r) / s + t, rt = 0.0;
else
res = 1.0 * rlen / r, rt -= res;
for (int i = 0; i < n; i ++) {
if (rt <= 0.0) {
res += 1.0 * (cors[i].e - cors[i].b) / (s + cors[i].w);
continue;
}
if (1.0 * (cors[i].e - cors[i].b) / (r + cors[i].w) <= rt) {
res += 1.0 * (cors[i].e - cors[i].b) / (r + cors[i].w);
rt -= 1.0 * (cors[i].e - cors[i].b) / (r + cors[i].w);
} else {
res += 1.0 * (cors[i].e - cors[i].b - (r + cors[i].w) * rt) / (s + cors[i].w) + rt;
rt = 0.0;
}
}
printf("Case #%d: %.9lf\n", T + 1, res);
}
void solve() {
int t;
scanf("%d", &t);
for (int i = 0; i < t; i ++)
solve(i);
}
}
int main() {
freopen("E:/OWenT/GCJ/R2/A-large.in", "r", stdin);
freopen("E:/OWenT/GCJ/R2/A-large.out", "w", stdout);
gcj::solve();
return 0;
}B题是我的痛啊，如果是难题，我不会，那我无话可说，关键是简单的计算几何+简单的DP，方法对，思路对，写代码的时候犯了N个白痴错误，各种变量名写错，各种复制代码忘了改。以后要注意写代码宁愿慢一点结构严谨，也不要贪图方便Copy代码。 比赛的时候这题我首先理解题目花了40多分钟，花了10分钟推导，50多分钟编码竟然都没写出来，Sample都没过，赛后我完全重写了一下，写出来到过小数据和大数据花了大概40分钟不到。真是不甘心。
B题大意是给一个矩形钢板，要求先裁出一块正方形，边长大于等于3，再去掉四个角，要求最终的东西重心在形状上的中心。问是否存在如果存在给出最大的第一次裁出的正方形边长。题目难理解的地方在于开始输入的有r c d，而给的每个grid的重量是d+wij，这个地方我一直没理解然后用sample测理解。方法就是DP，对R和C进行DP，对K枚举就好。需要注意的地方是k可以为偶数。 B题代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
namespace gcj {
using namespace std;
const int maxn = 505;
typedef long long lld;
char inputStr[maxn];
struct grid{
lld r, c, w;
grid(): r(0), c(0), w(0){}
grid(lld a, lld b, lld c): r(a), c(b), w(c){}
friend grid operator+(const grid& l, const grid& r) {
return grid(l.r + r.r, l.c + r.c, l.w + r.w);
}
friend grid operator-(const grid& l, const grid& r) {
return grid(l.r - r.r, l.c - r.c, l.w - r.w);
}
};
grid grids[maxn][maxn];
grid sum[maxn][maxn];
void solve() {
int t, r, c, d, res;
scanf("%d", &t);
for (int tc = 0; tc < t; tc ++) {
scanf("%d %d %d", &r, &c, &d);
res = 0;
for (int i = 1; i <= r; i ++) {
scanf(" %s", inputStr);
for (int j = 1; j <= c; j ++) {
grids[i][j].w = d + inputStr[j - 1] - '0';
grids[i][j].r = i * grids[i][j].w;
grids[i][j].c = j * grids[i][j].w;
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + grids[i][j];
}
}
for (int i = 1; i <= r; i ++) {
for (int j = 1; j <= c; j ++) {
for (int k = max(3, res + 1); k + i - 1 <=r && k + j - 1 <= c; k ++) {
int ti = k + i - 1, tj = k + j - 1;
//if ((i + ti) % 2 || (j + tj) % 2)
// continue;
grid gd = sum[i - 1][j - 1] + sum[ti][tj] - sum[i - 1][tj] - sum[ti][j - 1]
- grids[i][j] - grids[i][tj] - grids[ti][j] - grids[ti][tj];
if (((i + ti) % 2 + 1) * gd.r % gd.w != 0 || ((j + tj) % 2 + 1) * gd.c % gd.w != 0)
continue;
if (2 * gd.r / gd.w != i + ti || 2 * gd.c / gd.w != j + tj )
continue;
res = max(res, k);
}
}
}
if(res)
printf("Case #%d: %d\n", tc + 1, res);
else
printf("Case #%d: IMPOSSIBLE\n", tc + 1);
}
}
}
int main() {
freopen("D:/GCJ/R2/B-large-practice.in", "r", stdin);
freopen("D:/GCJ/R2/B-large-practice.out", "w", stdout);
gcj::solve();
}唉，真心还需要学习提高水平啊。
Last updated