![Dutta[2]](https://cdn.slidesharecdn.com/ss_thumbnails/dutta2-120730051551-phpapp02-thumbnail.jpg?width=560&fit=bounds)
More Related Content
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
会津合宿2015顿补测3：贰问题
- 1. 2015/09/23 会津大学競技プログラミング合 宿 day3 E E:How To Make Stars ～星の作り方～ 原案：鈴木 解答：鈴木?栗田?井上 解説スライド：鈴木
- 2. 2015/09/23 会津大学競技プログラミング合 宿 day3 E 問題概要 以下を満たす特別な多角形を「星」と呼ぶ 頂点数10 内角が30度～60度の部分と240度～270度の部 分が交互に現れる n個の整数S_i（S_i > S_{i+1}）が与えられる 面積がS_1以上の星を1級星、S_{i-1}未満S_i以上の 星をi（2 ≤ i ≤ n）級星と呼ぶ 各k（1 ≤ k ≤ n）について、k級星を作り2次元平面上に 重なりなく配置せよ 座標値の絶対値は5000以下
- 3. 2015/09/23 会津大学競技プログラミング合 宿 day3 E 星の作り方① 正5角形を考え、各辺 についてそれに重な る直線を引き、それら の交点を頂点とすれ ば良い よくある星の内角は、小さい方が 36度、大きい方が252度である
- 4. 2015/09/23 会津大学競技プログラミング合 宿 day3 E 星の作り方② 正5角形を作り各辺の 中点を新たに頂点と し、その頂点を中心に 向かわせるように潰 すと星になる ※内角の制約を満たせればよい ので、きれいに潰す必要はない
- 5. 2015/09/23 会津大学競技プログラミング合 宿 day3 E 星の作り方 その他 手書きでうまく作る ベースとなる図形を考えて、数式を立てる などが考えられる いずれも、星となる制約を満たせば良いので、 きれいに作る必要はない
- 6. 2015/09/23 会津大学競技プログラミング合 宿 day3 E k級星を作る 作った星をベースに拡大 縮小し、面積S_{k-1}未満 S_k以上にする √（S_k / ベースの面 積） で倍率をとったり、 倍率を二分探索したり
- 7. 2015/09/23 会津大学競技プログラミング合 宿 day3 E 星の並べ方 星の外接円や、外接す る長方形を考えて、そ れを接触なく敷き詰め るように考えると楽 （AOJに円の配置に関 する類題があるけど、 どの問題か忘れた） ※余裕を持って配置できる制約になっている また、計算量は星の作成含めてO（n）を達成可能
- 8. 2015/09/23 会津大学競技プログラミング合 宿 day3 E Writer解 鈴木（C++）：151行 栗田（C++）：112行 井上（C++）：86行