Google Code Jam 2015 Round 2
こんにちは、お久しぶりのtatsyです。
本日はGCJ 2015のRound2に参加しました。
去年から1年、今日という日に賭けてきたにもかかわらず、今年は1217位という悲しい結果に終わってしまいました。
CのEasyが微妙に計算時間を短縮できなかったのが敗因です。そこらへんも含めて、
- A Small / Large
- B Small
- C small
を解説していきたいと思います。
A. Pegman (Small 5pt, Large 10pt)
問題
R×Cの大きさのグリッドが与えられている。グリッドの各セルは空か矢印のどちらかである。矢印のセルには上下右左のいずれかの方向を向いた矢印が書かれている。今、Pegmanさんはどこかのセルに立っている。
もし空のセルに立っていれば、そのままそこに留まり続ける。一方、矢印のセルに立っている場合には矢印の方向に歩き始める。もし歩いている途中で違う矢印にあたったら、その方向に向きを変えて再び歩き続ける。
このとき、Pegmanさんがどのセルに立っていたとしても、グリッドの外にはみ出さないようにするためには、最低何個の矢印の向きを変える必要があるか？不可能な場合にはIMPOSSIBLEと出力せよ。
解法
Pegmanさんが空のセルに立っている場合には外にはみ出すことはないので、これは考える必要がないです。
問題は矢印の上に立っているときですが、このときにPegmanさんがはみ出してしまうのは、矢印が向いている方向に別の矢印がないときです。
ですので、全ての矢印について、もし同じ行あるいは列に矢印があるのなら、その方向に向きを変えてやります。
もし矢印と同じ行あるいは列に別の矢印がなければ、どうやってもはみ出してしまうのでIMPOSSIBLEです。
計算量の見積もりですが、LargeでもRとCは高々100で、上記の計算の計算量はO(RC(R + C))くらいなので、計算時間は問題ないです。
正解のコードは以下の通りです。
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <list>
#include <stack>
#include <tuple>
#include <utility>
#include <complex>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <typeinfo>
using namespace std;
typedef long long lint;
typedef pair<int,int> pii;
typedef pair<lint,lint> pll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPA(i,s,e) for(int i=(s); i<=(e); i++)
#define REPD(i,s,e) for(int i=(s); i>=(e); i--)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a, b, c) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << ", " << #c << " = " << (c) << endl
template <class Ty> void print_all(Ty b, Ty e) {
cout << "[ ";
for(Ty p=b; p!=e; ++p) {
cout << (*p) << ", ";
}
cout << " ]" << endl;
}
// -----------------------------------------------------------------------------
// Code starts
// -----------------------------------------------------------------------------
int R, C;
int F[111][111];
int dr[4] = { 0, 0, -1, 1 };
int dc[4] = { -1, 1, 0, 0 };
void solve() {
cin >> R >> C;
char c;
REP(i, R) {
REP(j, C) {
cin >> c;
if (c == '.') F[i][j] = -1;
if (c == '<') F[i][j] = 0;
if (c == '>') F[i][j] = 1;
if (c == '^') F[i][j] = 2;
if (c == 'v') F[i][j] = 3;
}
}
int ans = 0;
REP(i, R) {
REP(j, C) {
if (F[i][j] == -1) continue;
int okdir = -1;
for (int k = 0; k < 4; k++) {
int ci = i + dr[k];
int cj = j + dc[k];
while (ci >= 0 && cj >= 0 && ci < R && cj < C) {
if (F[ci][cj] != -1) {
okdir = k;
break;
}
ci += dr[k];
cj += dc[k];
}
if (okdir == F[i][j]) {
break;
}
}
if (okdir == -1) {
printf("IMPOSSIBLE\n");
return;
}
if (okdir != F[i][j]) {
ans++;
}
}
}
printf("%d\n", ans);
}
// -----------------------------------------------------------------------------
// Code ends
// -----------------------------------------------------------------------------
void coding() {
int T;
cin >> T;
REPA(t,1,T) {
fprintf(stderr, "%3d / %d\n", t, T);
printf("Case #%d: ", t);
solve();
}
}
#define _LOCAL_TEST 2
int main() {
#if _LOCAL_TEST == 0
clock_t startTime = clock();
freopen("a.in", "r", stdin);
#elif _LOCAL_TEST == 1
freopen("../input/A-small-attempt0.in", "r", stdin);
freopen("../output/A-small0.out", "w", stdout);
#elif _LOCAL_TEST == 2
freopen("../input/A-large.in", "r", stdin);
freopen("../output/A-large.out", "w", stdout);
#endif
coding();
#if _LOCAL_TEST == 0
clock_t elapsedTime = clock() - startTime;
cerr << endl;
cerr << (elapsedTime / 1000.0) << " sec elapsed." << endl;
cerr << "This is local test" << endl;
cerr << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}
B. Kiddle Pool (Small 7pt, Large 18pt)
問題
今、N個の水源から水が溢れ出している。i番目の水源からは毎秒R[i]の勢いで温度がC[i]の水が流れ出している。あなたの目的は、この水源から水をくみ出して、量がちょうどVで温度がちょうどXの状態を作ることである。各水源は一度だけくみ出しとくみ終わりの操作ができる。このとき、目的の状態を作るための最小秒数は何秒になるか？
解法
この問題は、全ての水源を同時にくみ出し始めるという風に考えても一般性を失いません。ですので、各水源を時間が0の状態からくみ出し始めてi番目の水源を時刻t[i]にくみ終わるとします。
そうすると、満たすべき条件を等式で書き表すことが出来て、
$$ \displaystyle V = \sum_{i=1}^N R_i t_i $$
$$ X = \frac{\displaystyle \sum_{i=1}^N R_i C_i t_i}{\displaystyle \sum_{i=1}^N R_i t_i} $$
という水量と温度に関する制約式が得られます。ちなみに二つ目の式は1つ目の式をつかって、
$$ \displaystyle XV = \sum_{i=1}^N R_i C_i t_i $$
と書き直しておきます。
求めるべき解はt[i]の中で最大となるものです。
制約式が2つで未知数がN個なので、Nが2以下というSmallの条件なら連立方程式を解くだけで、t[1]とt[2]が求まります。なので、連立方程式をといて大きいほうを返してあげればいいです。
ただし、単に連立方程式を解く実装にすると、数値誤差の関係でC[1] = C[2] = Xの場合などがはじけなかったりするので、例外的なものは、連立方程式ではなくRやCの実際の値を使って評価してあげます。
これでSmallは解けます。Smallの解法コードは次の通りです。
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <list>
#include <stack>
#include <tuple>
#include <utility>
#include <complex>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <typeinfo>
using namespace std;
typedef long long lint;
typedef pair<int,int> pii;
typedef pair<lint,lint> pll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPA(i,s,e) for(int i=(s); i<=(e); i++)
#define REPD(i,s,e) for(int i=(s); i>=(e); i--)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a, b, c) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << ", " << #c << " = " << (c) << endl
template <class Ty> void print_all(Ty b, Ty e) {
cout << "[ ";
for(Ty p=b; p!=e; ++p) {
cout << (*p) << ", ";
}
cout << " ]" << endl;
}
// -----------------------------------------------------------------------------
// Code starts
// -----------------------------------------------------------------------------
int N;
double X, V;
double Rs[111];
double Cs[111];
double A[111][111];
double b[111];
double t[111];
void failed() {
printf("IMPOSSIBLE\n");
}
void solve() {
cin >> N >> V >> X;
REP(i, N) {
cin >> Rs[i] >> Cs[i];
}
if (N > 2) {
failed();
return;
}
if (N == 1) {
if (Cs[0] != X) {
failed();
return;
}
printf("%.8f\n", V / Rs[0]);
return;
}
if (Cs[0] == X && Cs[1] == X) {
printf("%.8f\n", V / (Rs[0] + Rs[1]));
return;
}
A[0][0] = Rs[0];
A[0][1] = Rs[1];
A[1][0] = Rs[0] * Cs[0];
A[1][1] = Rs[1] * Cs[1];
b[0] = V;
b[1] = V * X;
double det = A[0][0] * A[1][1] - A[1][0] * A[0][1];
t[0] = ( A[1][1] * b[0] - A[0][1] * b[1]) / det;
t[1] = (-A[1][0] * b[0] + A[0][0] * b[1]) / det;
if ((Cs[0] > X && Cs[1] > X) || (Cs[0] < X && Cs[1] < X)) {
failed();
return;
}
double ans = max(t[0], t[1]);
printf("%.8f\n", ans);
}
// -----------------------------------------------------------------------------
// Code ends
// -----------------------------------------------------------------------------
void coding() {
int T;
cin >> T;
REPA(t,1,T) {
fprintf(stderr, "%3d / %d\n", t, T);
printf("Case #%d: ", t);
solve();
}
}
#define _LOCAL_TEST 1
int main() {
#if _LOCAL_TEST == 0
clock_t startTime = clock();
freopen("b.in", "r", stdin);
#elif _LOCAL_TEST == 1
freopen("../input/B-small-attempt4.in", "r", stdin);
freopen("../output/B-small4.out", "w", stdout);
#elif _LOCAL_TEST == 2
freopen("../input/B-large.in", "r", stdin);
freopen("../output/B-large.out", "w", stdout);
#endif
coding();
#if _LOCAL_TEST == 0
clock_t elapsedTime = clock() - startTime;
cerr << endl;
cerr << (elapsedTime / 1000.0) << " sec elapsed." << endl;
cerr << "This is local test" << endl;
cerr << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}
C. Bilingal (Small 6pt, Large 24pt)
問題
今、N個の文章が与えられている。0番目の文章は英語のもの、1番目の文章はフランス語のものであることが分かっているが、2番目以降の文章はどちらの言語か分からない。このN個の文章から英語とフランス語のどちらにもある単語の数が知りたい。このような単語の数は最低でも何個になるかを答えよ。
解法
Smallの条件はNが20以下なので、ビットマスクを作って、どの文章が英語かフランス語かを全パターン試せばよさそうです。
最初、各単語をsetで管理して、英語のsetとフランス語のsetのunionを取るというコードを書いたのですが、時間がかかりすぎてしまいました。
冷静に計算量を見積もって見ます。今ビットマスクを考えないといけないのは最初の2つを除いた高々18個なので、全探索する計算コストは2^18 = 5 * 10^5くらいです。
問題の条件から最初の2つの文章は1000の単語を、2番目以降の文章は10の単語を含む可能性があるので、英語、フランス語のsetは最大で1200個くらいの単語を含む可能性があります。
set同士のunionを取る操作は各setの大きさがMの場合にO(M log M)ですので、M = 1200とすると、大体10^4くらいの計算量が係ることになります。
そうすると、全体では10^9くらいの計算コストがかかることになり、計算時間は足りなさそうであることが分かります。
今、unionを取る操作にO(M log M)をかけていたのですが、これをO(M)くらいにできれば何とかなりそうです。
そこで、まず最初に全ての単語に番号を付けておいて、ある番号の数字が英語とフランス語に現れるのかどうかをテーブルで管理することを考えます。
問題の条件から単語の総数は高々2400個くらいですので、定数が少なければギリギリ何とかなりそうです。
最初に各文章に番号が何番の単語が表れるのかを計算しておいて、各ビットマスクについては、テーブル上でビット演算をして英語に現れるのか、フランス語に現れるのかを記録していきます。
このやり方だと、大体25個のテストケースに対して30秒くらいで計算が終わりました。実際のコードは次のようになります。
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <list>
#include <stack>
#include <tuple>
#include <utility>
#include <complex>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <typeinfo>
using namespace std;
typedef long long lint;
typedef pair<int,int> pii;
typedef pair<lint,lint> pll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPA(i,s,e) for(int i=(s); i<=(e); i++)
#define REPD(i,s,e) for(int i=(s); i>=(e); i--)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a, b, c) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << ", " << #c << " = " << (c) << endl
template <class Ty> void print_all(Ty b, Ty e) {
cout << "[ ";
for(Ty p=b; p!=e; ++p) {
cout << (*p) << ", ";
}
cout << " ]" << endl;
}
// -----------------------------------------------------------------------------
// Code starts
// -----------------------------------------------------------------------------
int N;
vector<int> table;
vector<int> words[211];
int check(int mask) {
fill(ALL(table), 0);
mask = (mask << 2) + 2;
for (int i = 0; i < N; i++) {
if ((mask & (1 << i)) == 0) {
for (int k = 0; k < words[i].size(); k++) {
table[words[i][k]] |= 1;
}
} else {
for (int k = 0; k < words[i].size(); k++) {
table[words[i][k]] |= 2;
}
}
}
int ret = 0;
for (int i = 0; i < table.size(); i++) {
if (table[i] == 3) {
ret++;
}
}
return ret;
}
void solve() {
string dummy;
cin >> N;
vector<vector<string> > temp(N);
std::getline(cin, dummy);
vector<string> v;
for (int i = 0; i < N; i++) {
std::getline(cin, dummy);
string word;
stringstream sst;
sst << dummy;
words[i].clear();
while (sst >> word) {
temp[i].push_back(word);
v.push_back(word);
}
}
sort(ALL(v));
v.erase(unique(ALL(v)), v.end());
table.resize(v.size());
for (int i = 0; i < N; i++) {
words[i].clear();
for (int k = 0; k < temp[i].size(); k++) {
int id = lower_bound(ALL(v), temp[i][k]) - v.begin();
words[i].push_back(id);
}
}
int ans = 1 << 20;
int M = N - 2;
for (int mask = 0; mask < (1 << M); mask++) {
ans = min(ans, check(mask));
}
printf("%d\n", ans);
}
// -----------------------------------------------------------------------------
// Code ends
// -----------------------------------------------------------------------------
void coding() {
int T;
cin >> T;
REPA(t,1,T) {
fprintf(stderr, "%3d / %d\n", t, T);
printf("Case #%d: ", t);
solve();
}
}
#define _LOCAL_TEST 1
int main() {
#if _LOCAL_TEST == 0
clock_t startTime = clock();
freopen("c.in", "r", stdin);
#elif _LOCAL_TEST == 1
freopen("../input/C-small-practice.in", "r", stdin);
freopen("../output/C-small.out", "w", stdout);
#elif _LOCAL_TEST == 2
freopen("../input/C-large.in", "r", stdin);
freopen("../output/C-large.out", "w", stdout);
#endif
coding();
#if _LOCAL_TEST == 0
clock_t elapsedTime = clock() - startTime;
cerr << endl;
cerr << (elapsedTime / 1000.0) << " sec elapsed." << endl;
cerr << "This is local test" << endl;
cerr << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}
ちなみに、この実装では最初に単語に番号を割り振っていますが、ここで楽をしてmapとかで単語と数字の対応関係をとるような実装にしてしまうと、全然計算が間に合いませんでした。
感想
Cの計算時間のチューニングが間に合わなかったのは僕だけではなかったようで、結構この問題でつまづいている人は多かったです。
いずれにしてもCをチューニングしきれないという土壇場の弱さが出た結果でした。
去年からTopCoderのレートは200くらいはあがってるはずなので、今年こそはTシャツ取れると思ったんですけどね。
とはいえ、TopCoderみたいに時間の短いコンテストはあまり得意ではなくて、GCJみたいに時間の長いコンテストでは素の実力に近いものが元々出せていただけというのもありますが。
GCJより条件は厳しめなのですが、TCOの方でTシャツが取れるようにがんばります。
今回も最後までお読み頂きありがとうございました。