Google Code Jam Japan 2011決勝

Google Code Jam

結果

rankalee 29位
34点 ペナルティ3:08:46
25:00 25:36 / - - / 2:56:46 - / 2:13:16 - / - -


微妙。Largeが全然解けなかったので悔しい。

問題A. アンテナ修復

K本の線分を、1点を共有し、隣り合う線分同士の角度が全て360/K度の角度をなすよう、好きな順に並べる。
このとき、隣り合う線分によって作られる三角形の面積の総和の最大値を求めよ。

制約条件

n≦1000

試行錯誤

えーと、二本の線分の長さをa,bとすると面積は(1/2)absinΘで、Θは固定だから、
要するに数列を、Σa[i]*a[(i+1)%n]が最大になるように並べ替えろということか。


これは、Greedyでいいのでは？大きい順に単にソートすれば。
あ、違う。円形に並べるので端と端がつながるのか。


じゃあこの前のJAG合宿で見た問題みたいに両端から配るようなDPしていけばいい。


書いた。サンプル合わない。
漸化式間違ってる。


訂正。サンプル合わない。
また漸化式間違えてる。てかみんな提出してる。ええーこのDPってそんなに簡単でもないだろー。


訂正。サンプル合った。small提出。
WA.
何だろう。見直す。最後に答えを求める部分が間違ってる。
サンプルは偶然合ったっぽい。


提出。手間取ったけどようやく正解。ついでにLargeも提出しておく。

問題B. バクテリアの増殖

x個のバクテリアがいる。1秒後にはx^x個に増える。
このバクテリアがA秒後には何個になっているか、mod Cで求めよ。

試行錯誤

うーん……なんか難しそうな問題の予感。
オイラーの定理とかを使うんだろうか。
あーでも、AとCが互いに素じゃない場合なんか厄介。
AとCが互いに素な部分とそうじゃない部分に分けて計算したりするんだろうか。


数十分考えたが、難しくてよくわからない。パス。

問題C. ワイルドカード

ワイルドカードは、任意の長さ0以上の文字列にマッチする文字列である。


二つの文字列A,Bが与えられたとき、
Aにマッチし、Bにマッチしないような文字列のうち、長さ最短のものをもとめよ。
長さが最短のものが複数ある場合、ワイルドカードの個数が最も少ないものを求めよ。
それが複数ある場合は、ASCIIコード順で最小のものを求めよ。

試行錯誤

えー、今回大分問題むずくね？
さっぱりわからない。
ワイルドカードって途中に何回も現れる？現れるなあ。
しかもBどの部分にマッチさせるかって一意に決まらないし。


smallだけ解こうか。まあそれは後回しにしてとりあえず全部問題を読もう。

問題D. クローゼットルーム

hxwマスのグリッドで表される部屋が与えられる。
部屋の一部のマスは'X'で表される柱がある。また、部屋のどこかに'S'で表されれる入り口がある。
この部屋に1x2マスのクローゼットをできるだけ多く置きたい。


クローゼットは以下の制約を満たして置く必要がある。

  • クローゼットには扉があり、正面の左側についている
  • 扉の前のマスには他のクローゼットや柱があってはならない
  • 扉の前のマスまで、Sから移動できるような通路が一つ以上存在しなければならない

このとき、置けるクローゼットの数の最大数を求めよ。

制約条件

w≦5
h≦20

試行錯誤

これはどうみても接続関係をもつDP.
んだけどどう実装するんだろうなあ。
状態としては dp[行][接続関係][部分が入り口につながっている必要があるか][部分が入り口につながっていうるか]としてやればよさそうだけど、実装やばそう。

とりあえずEを見てこよう。

問題E. 無限庭園

明らかにヤバい。

D(再）

接続関係のDPを考える。
考える。


考える。実装どうやっていいのか全然わからない。


考える。残り時間が結構やばいことに。
とりあえずTシャツ欲しいし、small解けるだけ解いていくか。
ということでD-small解く。


全探索により置けるクローゼットを全部試す。
結構実装しんどい。
書いた。バグる。
なんかクローゼットの扉の位置とかが斜めについていることになっている。
一から直した。


サンプル通った。
small投げる。WA.
なんでだろ。
あ、扉を正面左側じゃなくて正面右側として処理してるっぽい。


訂正。small投げる。正解。
続いてCへ。

C(再）

とりあえずこれもsmallだけ解いておこう。
まず、Aにマッチするようなワイルドカードを含む文字列を全生成して、それがBにマッチしないかを見ていけばよさそう。


ワイルドカードは連続しても意味がないので連続はしないように。
深さ優先で適当に生成すればOK


マッチするかは、貪欲に見ていけばいい？
書いた。サンプル合った。
もう時間ないしあんま確認せず投げる。


WA.あらら。
テストケースを除いてみると、１番目から明らかにおかしいことになってる。
マッチするかの判定が間違ってる。
これ貪欲じゃダメなんだー。

どうしよ。DPにしよう。
dp[i][j]をパターンのi番目まで、文字列のj文字目までがマッチできるかという表にして、
更新していく。O(n^3)くらいのDP.


書いた。さっきおかしかったケースも正常ぽくなっている。
投げる。正解。残り3分。スコアボード眺めて終了。

結果発表

A-Largeが通っていた。