Regionals 2010 :: North America - East Central NA
練習会。
実装頑張る系が多かった。
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=401
http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=601
4900 - Cut It Out!
問題
三角形が3*n個与えられる。
最初のn個は穴で、後の2*n個はパーツである。
2*n個のパーツを２個ずつくっつけることにより、n個の穴に対応させる。
くっついたパーツが穴と合同な時だけ対応させることが出来る。
このときパーツをフリップさせることは認めない。
どのように対応させれば、全てのパーツを穴に対応させることが出来るか。
ただし答えは存在し、一意に定まるとする。
制約
n<=20
解法
ある穴が、ある２つのパーツで対応させることができるかを頑張って判定する。
あとは割り当て方を探索する。
4901 - Flip It!
実装を頑張る
4902 - Maze
３次元座標の各面への射影の式を紙で考える。
それが出来ればBFSするだけ。
4903 - Photo Shoot
問題
自分の座標とn人の人の座標が与えられる。
カメラでn人を撮影したい。
カメラはf度の視野角を持つ。
全員を１回以上撮影するとき、必要な撮影回数の最小はいくらか。
制約
n<=100
f<=180
解法
n人の座標を自分の座標からの角度でソート。
始点を決めて貪欲。
4904 - Polar Bear
シミュレーションするだけ。
4905 - Pro-Test Voting
問題
n個の町がある。
町pについて、Mドル費やすと、下の式で表されるだけ票を得ることが出来る。
このとき、mドルまでを使って得られる票を最大にせよ。
また、そのとき各町に何ドル費やすかも出力せよ。
ただし、一意でないときは、辞書順最大を出力するものとする。
制約
n<=100
m<=100
解法
solve(i,j) = i番目以降の町でjドル費やすときに得られる票の最大値
としてメモ化再帰した。
最初DPで書いたが、辞書順最大が出来なかった。
4906 - Vampires!
実装するだけ。
