2017-08

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 を充てた二部隣接行列はこのグラフの接続行列.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/19-b465995a

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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