Google Code Jam 2014 Round 2

Tatsuya Yatagawa

2014-06-01

Programming Contest

こんにちはtatsyです。

昨日行われましたGCJ2014のRound2。まさかの2byteの違いに泣かされてTシャツを逃しました。

終了直後、悔しすぎて悔し死にするんじゃないかと思うくらい悔しかったです。

とりあえず、何言っているか分からないと思うので、そのあたりも交えながら解説をしていきます。

今回解説する範囲は

A Small / Large
B Small / Large
C Small
D Small

です。

A. Data Packing (Small: 5pt, Large: 8pt)

問題

ファイルがN個あり、それぞれのファイルの大きさがSiで与えられている。これらのファイルを容量がXのディスクに焼いていくのだが、1つのディスクに焼けるファイルの数は最大2つとする。このとき、与えられたファイルをすべて焼くのに必要なディスクの最小枚数は何枚か？

解法

この問題を読んだ感じのおおよその方針として、大きいファイルと小さいファイルを組みにしてディスクに焼いていくのが最小だろうと思いました。

ただし、容量の問題でファイルサイズが大きすぎるために1つのファイルに焼くしかない場合が出てしまうので、それをどう処理するかが問題になります。

なので方針としてはファイルサイズでファイルをソートしておいて、大きいファイルから順にペアにするディスクを探していけばいいことになります。

では、現在ディスクに焼かれていないファイルの中で最大のファイルを持ってきたとき、どのディスクをペアにすればよいでしょうか。実は、この際、ペアにした時に合計がXを超えないようなファイルならどれをペアにしても大丈夫です。

本来ならペアにできるものの中で最大のものとペアにするのが一番良いような気がしますが、一番小さいものとペアにしてもOKです。なぜなら、現在は大きなファイルから順にみているので、現在見ているファイルとペアにできるものは全てそれ以降に見るより小さいファイルとペアにできるのです。

したがって、ソートしたあとに左端と右端からだんだんと中央に向かってイテレータみたいなものを動かしていくという方針をとります。

このとき

左右のイテレータが指すファイルの合計がX以下なら、カウントを1つ増やして両方のイテレータを進める
左右のイテレータが指すファイルの合計がXを超えるときは、カウントを1つ増やして右側のイテレータだけを1つ進める
もし左右の指すイテレータが同じである時は、カウントを1つ増やして終了
左右のイテレータの順序が入れ替わったときは何もせず終了

という方針でイテレータを動かせば適切に解が求まります。

[sourcecode language=”cpp”]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#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) « “, " « (b) « “, " « (c) « endl

typedef long long lint;
typedef pair<lint,lint> pll;

int N,X;
int S[10011];

void solve() {
sort(S, S+N);
int lo = 0;
int hi = N-1;
int ans = 0;
while(lo < hi) {
if(S[lo] + S[hi] <= X) {
ans++;
lo++;
hi–;
} else {
ans++;
hi–;
}
}
if(lo == hi) ans++;
printf("%dn”, ans);
}

void coding() {
int T;
cin»T;
REPP(t,1,T) {
cin»N»X;
REP(i,N) cin»S[i];
printf(“Case #%d: “, t);
solve();
}
}

#define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
clock_t startTime = clock();
freopen(“A-large.in”, “r”, stdin);
freopen(“A-large.out”, “w”, stdout);
#endif

coding();

#ifdef _LOCAL_TEST
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
}

[/sourcecode]

A. Up and Down (Small: 7pt, Large: 11pt)

問題

互いに異なる自然数からなる数列が与えられる。この数列を並べ替えて、

$A_1$ «img src=“https://s0.wp.com/latex.php?latex=ldots&bg=ffffff&fg=000&s=0&c=20201002" alt=“ldots” title=“ldots” class=“latex” /> «img src=“https://s0.wp.com/latex.php?latex=A_m&bg=ffffff&fg=000&s=0&c=20201002" alt=“A_m” title=“A_m” class=“latex” /> > $ldots$ > $A_N$

となるようにしたい。これを実現するために隣り合う数を入れ替える操作をするとき、目的を実現するための最小操作回数はいくつか？

解法

もしLargeの解法が思いつかなければすべての並べ替えのパターンを試せばSmallは通ると思います。

Largeを通す場合には、適切な入れ替え方の戦略を考える必要があります。確か似たような問題が以前のTopCoderで出題されていたような気がしますが、数列の小さい数から順に場所を決めていけばOKです。

数列の中で現在並べ替えが済んでいない数の中で最小のものに注目します。これを並べ替える場合、この数は数列の左端か右端に来ることが保証されています(並べ替えられていないものの中で)。

なので、右端か、左端か移動回数が少なくて済む方に移動させてあげます。この操作をすべての数列が並び替え済みになるまで繰り返せばOKです。

typedef long long lint;
typedef pair<lint,lint> pll;

const lint INF = 1ll«55;
int N;
lint A[1011];

lint calc(vector v, int thr) {
lint ret = 0;
for(int i=0; i<thr; i++) {
for(int j=thr-1; j>=i+1; j–) {
if(v[j] < v[j-1]) {
swap(v[j], v[j-1]);
ret++;
}
}
}

for(int i=thr; i<N-1; i++) {
for(int j=N-2; j>=thr+1; j–) {
if(v[j] > v[j-1]) {
swap(v[j], v[j-1]);
ret++;
}
}
}
return ret;
}

void solve() {
vector v;

int le = 0;
int ri = N-1;
lint ans = 0;
REP(i,N) {
v.clear();
for(int j=le; j<=ri; j++) v.push_back(pll(A[j], j));
sort(ALL(v));

int p = v[0].second;
if(abs(p-le) < abs(ri-p)) {
for(int j=p; j>le; j–) {
swap(A[j], A[j-1]);
ans++;
}
le++;
} else {
for(int j=p; j<ri; j++) {
swap(A[j], A[j+1]);
ans++;
}
ri–;
}
}
cout « ans « endl;
}

void coding() {
int T;
cin»T;
REPP(t,1,T) {
cin»N;
REP(i,N) cin»A[i];
printf(“Case #%d: “, t);
solve();
}
}

#define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
clock_t startTime = clock();
//freopen(“b.in”, “r”, stdin);
freopen(“B-large.in”, “r”, stdin);
freopen(“B-large.out”, “w”, stdout);
#endif

coding();

[/sourcecode]

C. Don’t Break The Nile (Small: 10pt, Large: 20pt)

問題

グリッド上に区切られた長方形のマス目が与えられる。このマス目のそれぞれには水が流れていて、各々のマスでは隣り合ったマスのいずれかに1だけ水を流すことができる。今、エイリアンがやってきて、このマス目上に長方形のビルを建設した。建設した後の地図が与えられたとき、下の端から上の端まで流せる水の容量の最大値はいくつか？

解法

Smallだけを通すなら典型最大流問題です。アリ本にも似たような問題があります。

まず大前提として地図が何らかのグラフになっていて、下側のW個のマスがsourceに、上側のW個のマスがsinkにつながっているような最大流問題を考えます。あとは地図の中をどのようなグラフ構成にして水を流すかです。

ポイントは水が流れているマスではいずれかの方向にしか水が流せないということです。マス1つ1つをノードとしたグラフを作ってしまうと、テストケース1の答えが2になってしまうと思います。これは中央のマスに2回以上水が流れることが可能になってしまうからで、これを防ぐ必要があります。

やり方は簡単で、各マスに水が流入するノードと水が流出するノードの2つを持たせて、これらのノードの間を容量が1のエッジで結べばよいです。こうすれば同じマスが2回使われることはありません。

さて、ここまで考えて普通Ford-Fulkerson法のコードを書くと、1つ問題が起こります。それはグラフのサイズが500×100×2であるために、増加パスを探す深さ優先探索でStack too deepになってしまうということです。

今回の問題設定だと増加パスを探すのに最悪のケースですべてのノードを回らなくてはならず、再帰が深くなりすぎてしまいます。なのでコードをDinic法にしてあげます。Dinic法ならば深さ優先でたどるべき個所は事前に幅優先で計算した増加パスに限られるので、再帰の深さを減らすことができます。

この方針で行けばSmallは通せます。

typedef long long lint;
typedef pair<lint,lint> pll;

int W, H, B;
int F[111][511];

struct edge { int to, cap, rev; };

const int INF = 1«30;
const int MAX_V = 100011;
vector G[MAX_V];
int iter[MAX_V];
int level[MAX_V];

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

void add_edge(int from, int to, int cap) {
edge e1 = {to, cap, G[to].size()};
edge e2 = {from, 0, G[from].size()};
G[from].push_back(e1);
G[to].push_back(e2);
}

void bfs(int s) {
memset(level, -1, sizeof(level));
queue que;
level[s] = 0;
que.push(s);
while(!que.empty()) {
int v = que.front();
que.pop();
REP(i,G[v].size()) {
edge& e = G[v][i];
if(e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
}

int dfs(int v, int t, int f) {
if(v == t) return f;

for(int& i=iter[v]; i<G[v].size(); i++) {
edge& e = G[v][i];
if(e.cap > 0 && level[v] < level[e.to]) {
int d = dfs(e.to , t, min(f, e.cap));
if(d > 0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}

int maxflow(int s, int t) {
int flow = 0;
for(;;) {
bfs(s);
if(level[t] < 0) break;

memset(iter, 0, sizeof(iter));
int f;
while((f = dfs(s, t, INF)) > 0) {
flow += f;
}
}
return flow;
}

void solve() {
REP(i,MAX_V) G[i].clear();

int N = W * H;
REP(x,W) {
REP(y,H) {
if(F[x][y] != 0) continue;

int i1 = y * W + x;
add_edge(i1, N+i1, 1);
REP(k,4) {
int xx = x + dx[k];
int yy = y + dy[k];
if(xx >= 0 && yy >= 0 && xx < W && yy < H && F[xx][yy] == 0) {
int i2 = yy * W + xx;
add_edge(N + i1, i2, 1);
}
}
}
}

int S = N * 2;
int T = N * 2 + 1;
REP(x,W) {
if(F[x][0] == 0) add_edge(S, x, 1);
if(F[x][H-1] == 0) {
int i0 = (H-1) * W + x;
add_edge(N + i0, T, 1);
}
}
printf("%dn”, maxflow(S, T));
}

void coding() {
int T,x0,y0,x1,y1;
cin»T;
REPP(t,1,T) {
cin»W»H»B;
memset(F, 0, sizeof(F));
REP(i,B) {
cin»x0»y0»x1»y1;
REPP(x,x0,x1) {
REPP(y,y0,y1) {
F[x][y] = 1;
}
}
}
printf(“Case #%d: “, t);
solve();
}
}

#define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
clock_t startTime = clock();
// freopen(“c.in”, “r”, stdin);
freopen(“C-small-practice.in”, “r”, stdin);
freopen(“C-small.out”, “w”, stdout);
#endif

coding();

[/sourcecode]

D. Trie Sharing (Small: 9pt, Large: 30pt)

問題

現在1つのサーバーに複数の文字列が保存されている。保存する際、文字列はそれぞれの文字列が持つ接頭辞をすべて1回ずつ含むようなノードの集合により表現されている(詳しくは問題文を見てください)。このノードの数が増えてきたので、保存されている文字列をNこのサーバーに分割して保存することにしたい。各サーバーで同様にノードを作った時に、全サーバーでのノードの合計数が知りたい。このノード数が最大になってしまう場合いくつになるのか、そして、その最大のケースが起こる場合の数がいくつかを答えよ。

解法

この問題もSmallならば全探索で行けます。文字列の数が最大8個でサーバーが4個なので4^8の場合が存在します。

このそれぞれについて、Trieの大きさを調べる工程が必要で、文字列の長さが最大10であることから8×10くらいの計算量になります(もしふつうにsubstrするとコピーのコストがあるのでもう少し計算量が増える)。

これらをすべて考慮すると全体の計算量は5×10^6くらいになると思います。これを100回繰り返すので結構時間は厳しいですが何とかなりそうです。

問題文を良く読むと、各サーバーは少なくとも1つは文字列を持つようなのですが、1つも文字列を持たないサーバーが存在する場合はすべてのサーバーが少なくとも1つ文字列を持つ場合のいずれかよりも必ず少なくなるので、実はこれは考えなくても大丈夫です。

なので、ナイーブに深さ優先探索でサーバーの格納パターン4^8通りを作って、それぞれについてTrieの大きさを計算してやるという方針で行きます。

方針はこれでまったく問題ないのですが、実はこの問題には1つ落とし穴があり、この落とし穴にはまってTシャツを逃しました。というのはsubstrを使う時に、接頭辞の代わりに接尾辞をとってもテストケースでは答えが同じになるのです！！

本来、先頭からc文字をとるときにはstr.substr(0, c)としなくてはなりませんがstr.substr(c)でも答えが同じになるということです。

とりあえず、ここではあまり感情的な話はしないとして、答えのコードは次のようになります。

typedef long long lint;
typedef pair<lint,lint> pll;

int M, N;
string S[1011];
int sev[1011];

pll ans;

int cnt(vector& v) {
set st;
for(int i=0; i<v.size(); i++) {
for(int c=0; c<=v[i].size(); c++) {
st.insert(v[i].substr(0, c));
}
}
return (int)st.size();
}

void calc() {
vector v;
int ret = 0;
REP(i,N) {
v.clear();
REP(j,M) {
if(sev[j] == i) v.push_back(S[j]);
}

if(v.empty()) return;
ret += cnt(v);
}

if(ans.first < ret) {
ans = pll(ret, 1);
}
else if(ans.first == ret) {
ans.second++;
}
}

void dfs(int d) {
if(d == M) {
calc();
return;
}

for(int i=0; i<N; i++) {
sev[d] = i;
dfs(d+1);
}
}

void solve() {
ans = pll(0, 0);
dfs(0);
printf("%lld %lldn”, ans.first, ans.second);
}

void coding() {
int T;
cin»T;
REPP(t,1,T) {
cin»M»N;
REP(i,M) cin»S[i];
printf(“Case #%d: “, t);
solve();
}
}

#define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
clock_t startTime = clock();
//freopen(“d.in”, “r”, stdin);
freopen(“D-small-attempt3.in”, “r”, stdin);
freopen(“D-small.out”, “w”, stdout);
#endif

coding();

[/sourcecode]

まとめ

本番は1時間でAとBを通して、Dを読み終わった時点での順位と周りの出来から考えてTシャツいけると思いました。

実際、Dもsubstrの間違いを除けば正解のコードが1時間30分以内にはかけていましたし、substrの使い方をたった2byte分間違えただけで足元をすくわれた形になりました。

結果、絶対あっていると確信したまま1時間近く悩み続け、3回間違った答えを提出し、間違いに気づいたのは終了15分前でした。

提出した時点ではぎりぎり1000位に入っていましたが、Cが典型的な最大流問題だったので15分でみるみる抜かれて結果は1067位。

15分でCを実装する力があれば、これを回避できたわけですが、問題文を理解する速さ、タイピングのスピードなどを考えても、今の自分には15分は少なすぎました。

ただ、去年からかなり練習量を増やして、今回のGCJに掛けてきた分、Tシャツこそ取れませんでしたが、それなりの結果は出せたんじゃないかと思います。

これは完全に結果論ですが、もしsubstrの使い方を間違えていなければ十分にCのSmallは通せたと思います。今回のRound2突破のボーダーラインはA,BをSmall/Large両方通して、C,DはSmallだけ通すので2時間27分でした。ということは、この間違えさえなければ、Round2を突破できた可能性があった、ということです。

去年初めてRound2に出て、1問も解けずにコンテストを終えたことを考えれば大きな進歩だと思います。

1年間は長いですが、同じだけがんばれば来年はTシャツは普通に取れると思うので、また1年がんばりたいと思います。

と、最後の話はしめっぽくなってしまいましたが、これで解説を終わります。

気が向いたらC,DのLargeも解説しようかと思います。

最後までお読みいただき、ありがとうございました。