円板と多角形の共通部分の面積

アルゴリズム アルゴリズム-計算幾何 アルゴリズム-紹介 競プロ 競プロ-AOJ

問題. Circles - Intersection of a Circle and a Polygon

平面上の単純多角形 P と円板 C が与えられる．このとき， P \cap C の面積を求めよ．

単純多角形とは自己交差していない多角形で， P は P の頂点を反時計回りに訪れた頂点の列 (p_1, p_2, \ldots, p_n) で与えられ， p_i の座標を (x_i, y_i) で表す．
また，円板 C は中心 c で半径 r としたとき C = \{ \|p - c\| \le r \mid p \in \mathbb{R}^{2} \} を満たす領域である．

制約： 3 \le n \le 100，　 1 \le r \le 100，　 -100 \le x_i, y_i \le 100

続きを読む

2進数で有限小数となる10進有理数

数学 数学-数値計算

10進法で表記した有理数を2進法の小数で表記したときに，有限の桁数で表すことができる有限小数になるための特徴付けを与える．この応用として10進法で表記した有限小数が計算機上で誤差を含む数値かどうかの判定ができる．

続きを読む

ABC134 E問題：Sequence Decomposing

競プロ 競プロ-AtCoder アルゴリズム アルゴリズム-動的計画法

問題. Sequence Decomposing

長さ N の非負整数列 a = (a_1, a_2, \ldots, a_N) が与えれられる．各要素を色で塗ることを考える．ただし，同じ色で塗られたどの 2 要素 a_i と a_j \, (i < j) に対しても a_i < a_j が成り立つように塗る．このような塗り方の中で使用した色の種類の最小値を答えよ．

制約： 1 \le N \le 10^5，　 0 \le a_i \le 10^9

続きを読む

ICPC国内予選2019 C問題：天秤

競プロ 競プロ-ICPC アルゴリズム アルゴリズム-全探索

問題. 天秤

n 個の薬品と m 個の分銅の重さが与えられる． i 番目の薬品の重さは a_i で， j 番目の分銅の重さは w_j である．すべての薬品に対して天秤が釣り合うような分銅の置き方が存在するか判定せよ．ただし，釣り合わないときは任意の重さの分銅を 1 つだけ追加することができる．追加して釣り合うことができる分銅が複数ある場合は重さが最小のものを答えよ．

制約： 1 \le n \le 100，　 1 \le m \le 10，　 1 \le a_i \le 10^9，　 1 \le w_i \le 10^8

続きを読む

ARC016 C問題：ソーシャルゲーム

競プロ 競プロ-AtCoder アルゴリズム アルゴリズム-確率 アルゴリズム-動的計画法 アルゴリズム-ビット操作

問題. ソーシャルゲーム

N 種類のカードと M 種類のくじがある． i 番目のくじを引くのにかかる費用は c_i で，くじを引いたときに得られるカードの集合を D_i \subseteq \{1, 2, \ldots, N\} とする．また， i 番目のくじを引いて j \in D_i 番目のカードが当たる確率を p_{i, j} とする．
最適な戦略でくじを引いて全種類のカードをコンプリートするまでにかかる費用の期待値を答えよ．

制約： 1 \le N \le 10，　 1 \le M \le 4，　 1 \le c_i \le 3,000

続きを読む