I: Almost Same Polygon

First AC(全体): kotatsugame_arigatou (169:49)

First AC(オンサイト): kotatsugame_arigatou (169:49)

AC: 1/4

原案: amesyu

​

​

問題概要

対角線で切って捨てる操作を0回以上繰り返した後、

“2 × 捨てた面積 + C × 残った多角形の頂点数” の最小値を求めよ。

• 3 ≤ N ≤ 100
• 0 ≤ C ≤ 10⁶
• -1000 ≤ Xi, Yi ≤ 1000
• 与えられる多角形は単純多角形
• どの3点も同一直線上に存在しない

​

分割可能判定part

対角線が分割可能か？ = 線分全体が多角形内部 or 線上

=> 言われた通りに判定を行う。

符号付き面積を使うと楽

線分ABと線分PQが交差しているならば

sgn(△ABP) ≠ sgn(△ABQ) かつ�sgn(△PQA) ≠ sgn(△PQB) かつ�どの面積も0でない(0だと線上)

P

Q

B

A

分割可能判定part

交差だけを判定するだけでは不十分(内部判定が必要)�判定方法はいくつかあるが、

1. 分割された2つの多角形が面積正である�2. 適当に中点を取って内部かどうか判定

などがある。N(N-3)/2個の対角線それぞれに対して多角形の辺と交差判定を行うので O(N³) で判定可能。

Bonus! O(N²logN) で判定

分割可能判定part

ダメな例

多角形の辺をグラフに言い換えるpart

• 頂点i, 頂点jを結ぶ対角線で分割したとき(向き有り)

入力で与えられる多角形をPとしてP[i:j], P[j:i]の2つの領域に分けられる。P[i:j]を捨てて新たに i -> j の辺を追加するときにかかるペナルティの寄与を考えると、�Area(P[i:j]) - C × (捨てた頂点数)

• 頂点i, 頂点jで分割できないとき

† Infinity †

多角形の辺をグラフに言い換えるpart

​

• 分割しないとき(元々存在する辺)

頂点i, 頂点i+1を結ぶ辺は元々存在する。ペナルティへの寄与は0

​

これらの辺を用いると多角形のペナルティはiからiへのパスのコストの総和 + C × Nと表すことができる。

多角形の辺をグラフに言い換えるpart

​

​

細かい部分

• i -> j で分割した後に j -> i で分割する操作を行えない�(対角線では無くなっている為)��

区間DP(円環ver)

円環を扱うDPは主に２種類の実装方法がある、

1. N × N の配列で i -> hoge -> i を求める。
2. 2N × 2N の配列で i -> hoge -> i + N を求める。

�本質的には同じで

DP[i:j] = i -> j に行くパスでペナルティの最小値

区間DP(円環ver)

i -> j で分割した後の j -> i 分割をできないようする。

• パス長を持ってDP(長さ1,2,3以上を持って3以上が答え)�min{DP[0][0][3], … , DP[N-1][N-1][3]} + C × N が答え。�
• i -> j -> k -> i のパス長がNであるi, j, kを用いて�DP[i][j] + DP[j][k] + DP[k][i] + C × Nの最小が答え。

いずれの方法でもO(N³)を達成できた！

おもしろケース