2005/Practice/冬合宿

このページを編集する

Problem A: Eyeball Benders †

方針：puzzle image 内のすべての線分の端点に対し、その端点が solution image の端点の一つであると仮定し、拡大率を求め、solution image をトリミングして照合。

　まず選んだ端点からの距離が最も近い線分のいずれかの端点へのベクトルを見つけ *1、solution image の線分の端点から、そのベクトルの方向へ半直線を延ばす。　ベクトルの長さを、端点から半直線とsolution image 内の他の線分との交点への距離の最小値で割った値が、拡大率となる。　この拡大率が 1.0 未満の時は、別の端点を選んで再試行。

　拡大率と、puzzle image 内の端点の座標と、solution image 内の端点の座標から、solution image の切り取り線を計算する。　solution image をトリミングした image と、puzzle image を拡大したものが等しければ、yes を出力。

　オーダーは、O(m^2 n) 。*2 　　m : puzzle image 内の線分の数 　　n : solution image 内の線分の数

Problem B: Simplified GSM Network †

Problem C: The Traveling Judges Problem †

1. 選択する点の集合を{取る|取らない}^(20-ジャッジ-1)した集合を作る 2. その点でMSTを構成して、同時に連結成分であるかを判定する 3. 連結成分であれば正解として出力する。

C問題に関する諸考察.ppt

Problem D: cNteSahruPfefrlefe †

1. 正しくシャッフルした山との照合を行って、シャッフル回数を調べる。(シャッフルの周期が11以上であることと、一回のスワップで間違った場所に移るカードは2枚までであることからシャッフル回数は一意に定まる)
2. シャッフル後の山から初期状態まで、スワップ回数について反復深化しながら逆向きに探索する。なるべく答えに近づくものを優先的に探す。

ソースコード by nya@qoo

Problem E: Lots of Sunlight †

部屋の下端と各建物の上端の角度の最大値から時間を求める．

Problem F: Crossing Streets †

私の考えた解法: 全ての道路を内側と外側の線分に分ける。 家から大学へ線を引き、その途中で交わった線分と線分を繋ぐ。 線分を辿って大学まで行く。 その際、内側の線分から外側の線分に移ったり、線分が交差した時は 道路を一回またいだ事にする。

もう一つの解法: メッシュを生成して、全体を塗りつぶす。

Problem G: Tiling the Plane †

Problem H: The Great Wall Game †

1. 全通りの結果を生成する(2n+2通り) 2. その集合に対して元の石の位置からのマンハッタン距離で重み付きマッチングを行う. Thanks to combat!

Shanghai2005H.ppt

Problem I: Workshops †

最小費用最大マッチングで解ける。
貪欲法でも解けるような気もします。 nyaによるソースコードと証明(らしきもの):
http://qoo.pcbsoft.net/wiki/?%A4%E2%A4%CE%A4%AA%A4%AD%2F20060224%20Winter%20Camp%20day1 ツッコミよろしくおねがいします。

Problem J: Zones †

n<=20なので，全探索で十分。