2017-07

Latest Entries

スポンサーサイト

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

Google Code Jam Round 3 2011

500 人中 25 人オンサイト.
D-Small → A → B → C で終わった.
A, B が簡単,D が難しく,C が速く解けるかどうか.2 位と同じ点数だが 43 位.

A: Irregular Cakes


2 本の折れ線と x = 0,x = W で挟まれた領域を,縦線で切って G 等分するときの切る x 座標を求める.
座標は整数,W <= 1,000,(折れ線の頂点数) <= 100,G <= 100.

整数座標に対して縦の長さを求めておき,面積については部分和をとっておけば二分探索できる.二分探索を整数の範囲でやって残りは 2 次方程式を解いても良い.

B: Dire Straights


10000 以下の正の整数が N 個与えられる.グループ分けして各グループを連続する整数 1 つずつにするとき,最小のグループの大きさを最大化する.
0 <= N <= 1,000.

グループを作りつつ小さい方から順になめていって,見ている数をどこかに加えられるならば最小サイズのものに加える,ということを繰り返せばよい.

とりあえず答について二分探索した.手間はほぼ同じ.

C: Perpetual Motion


R * C の各マスについて,| \ - / いずれかの方向が指定されている.各マスについて向きを定めて,各マスからその向きに従って動けるマス (はみ出したら mod) への写像が全単射,というような向きの付け方が何通りか,mod 1,000,003 で求める.
3 <= R, C <= 100.

元のマスを左,移動先を右の頂点とみた,2RC 個の頂点を持つ二部グラフで考える.右側の頂点で次数 0 があったら不可能.次数 1 があったらその辺を確定させることでまた制約がつき,次数 1 以下の右側の頂点をなくせる.この部分は修正 BFS あたりで実装.すべて次数 2 以上ならば,左側の頂点がすべて次数 2 なので,すべて次数 2,よってサイクルの集まり.連結成分ごとに 2 通りとなる.

解があるかどうかは二部マッチングでも求まる.
また,二部隣接行列について,左側の頂点からの 2 本に +1 と -1 を充てることにすれば,解があるときは答は 2^(RC - rank) となる模様.疎行列のランクを求める必要が生じる.

(追記)
左側の頂点を辺だと思って頂点数 RC 個のグラフで見れば,辺が RC 本.連結成分ごとに頂点数が辺数でなければ不可能,そうでなければそれぞれサイクルに木がついた形.葉の方から確定していき,サイクルが 1 つ残るので,BFS を経なくても 2^(連結成分の個数) で解ける.
+1 と -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 分かからず回った.

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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