2017-10

Latest Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Google Code Jam Round 2 2011

3000 人中 500 人通過,1000 人 T シャツ.
Round 1A より簡単だったと思うけれど,今回もできなかった.
本番中はすべて D 言語で C → B → A と通した.

A: Airport Walkways


一直線上の道の途中に,動く歩道が N 個ある.それらの位置 (重ならない) と速度が与えられる.
人の歩く速度と走る速度と走れる合計時間の上限が与えられるので,目的地までの最短時間を求める.
N <= 1,000.

速い方から走るか遅い方から走るかに違いない,と思って両方試してサンプルが通った方を送った.
直感がうまく働かなかったが,動く歩道に乗れる時間を増やす方がよさそう,と考えるとわかりやすい気がする.

B: Spinning Blade


R * C のグリッドが各マスの重さとともに与えられる.
K * K (K >= 3) の正方形から四隅を取り除いた形を考え,そのうちで重心が中央にくるもののうち K の最大値を求める.
R, C <= 500.

(重さ) * (座標) の部分和をもっておけばよい.

面倒なことに,K * K の中心とする相対座標における (重さ) * (座標) の和を計算していってしまった.
また,文字列をデフォルトで 110 文字までしか読み込めないようにしていたことを忘れていて,Large 実行時に事故が起こった.

C: Expensive Dinner


最初は食べ物の量が 0 である.
人 1 から人 N が何らかの順番で 1 人ずつやってくる.
人 a がやってきたとき,食べ物の量が a の倍数でなければウェイターを呼ぶ.
いる人 b であって食べ物の量が b の倍数でない人がいる限り,そのような誰かが食べ物の量を次の b の倍数まで増やす.
ウェイターが呼ばれうる回数の最大値と最小値の差を求める.
N <= 10^12.

b の選び方によらず,いる人たちの最小公倍数になる.最小公倍数はスキップされないから.
p を素数, e = [N^(1/p)] とすれば,最大は各 p に対して p^1, p^2, ..., p^e の順,最小は各 p に対して p^e がいきなり登場,あとは適当な順,であることがすぐ示せる (たぶん).
なので答えは e - 1 の和.e = 1 を無視していいので見るべき素数は √N まで.
N = 1 は特殊なので別途処理.

D: A.I. War


頂点数 P,辺数 W の無向グラフが与えられる.
・頂点 0 から頂点 1 の最短経路の長さを求める.
・最短経路のうち,通らなかったが最短経路中の頂点と隣接している頂点数の最大値を求める.
P <= 400,W <= 2000,50 ケース.

BFS 木を考えることで,隣接する外の点というのは,最短経路をたどってきたときの過去 2 つの点としか共有されないことがわかる.なのでそれを状態 (O(W) 個) にして DP.
隣接する外の点で共有されていないもの,を数えるときは適当に O(P) 回しても全体で O(P^2 W) で,1 分かからず回った.

コンテスト中はフローに違いないという方向に固執してしまった.
サンプルが弱いので積極的にいろいろなグラフを作って試すべきだったと思う.

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/5-2befac93

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。