Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2100-e6dd350e
この記事にトラックバックする(FC2ブログユーザー)

Timus 1875 - Angry Birds (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1875

問題概要

y軸の正の方向が上,つまり,重力はy軸の負の方向に働く.
5匹の猿の座標が与えられる.x座標y座標共に正.
原点からボールを投げて全ての猿に当てたい.(あたっても軌道は変わらない)
最小で何回ボールを投げればいいか求める問題.
ボールは,x軸方向に等速度,y軸方向に重力の力によって等加速度運動を行う.
原点と2匹の猿が同一直線上にあることはないとする.

解法

原点を通り,上に凸な2次関数を何個書けば点を覆えるかという問題.
原点と2点を選んだ時,2次関数は一意に定まるので,それで当てれる猿を列挙する.
後は,例えばDPして,各部分集合に対応する猿を全部当てるのに必要なボールの数を求める.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2100-e6dd350e
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。