CodeChef August Challenge 2020 - Insanely Hard School Exam

• 問題
• AC

1つの色についてだけ考える。平行な2直線がないとすると、直線が$x$本ある時のtruly-geometric triangle（以下TGT）の総数は$\binom{x}{3}$である。これを元に、$\operatorname{dp}[x][y] =$色$x$まで見て消しゴムの残量が$y$である場合のTGTの総数、として全体で${O}(NK)$のDPが可能なのでsubtask2, 3が解ける。

平行線がある場合について考える。平行関係は同値関係なので、異なる同値類の総数を$p$とし、$i$番目の同値類に属する直線が$L_i$個あるとする。$L_1 \ge L_2 \ge ... \ge L_p$と仮定してよい。これらの直線を消していくとき、同値類の総数をできるだけ減らすように消すのが最善なので、後ろから消していくのがよい。そこで$f(c, z) =$色$c$の直線が$z$本残っている場合のTGTの総数、として$f$を事前に求めておけば、上と同じDPで解ける。順序が固定されているので$f$自体もDPで求まる。