ferinの競プロ帳

競プロについてのメモ

CSA

FII Code Round #1 Sugarel in Love

問題ページ 解法 dp[i][j] = (頂点i以下の部分木で使用したパスにおいて頂点iの次数がjのときの最大値) としてdpする。(頂点vの部分木において)頂点vを端点とする辺を使用しない場合、子の部分木はどのような選び方をしていたとしても問題ないため遷移は dp[…

CSA Round #68 D Triangular Updates

問題ページ CS Academy 考えたこと 問題文の不等式を満たす範囲が何なのか (R,C)を左上で幅がLの下三角行列みたいな範囲になる クエリ先読みすると意味のあるクエリが少ないみたいなO(Q)の方をどうにかする改善ができるようには見えない 範囲加算の処理をO(L…

CSA Round #68 C Right Triangles

問題ページ CS Academy 概要 2次元座標上のN点(x, y)が与えられる。各点について3点(x,y)(0,0)(x,0)を結んでできる三角形の内部に他のN-1点のうち何個が含まれているか求めろ 2 <= N <= 10^5 1 <= x,y <= 10^5 xは全て異なる 原点と(x,y)を結んだ線上に他の…

CSA Round #68 B Integer Coords

問題ページ CS Academy 概要 0<=x<=N, 0<=y<=M の範囲の2次元座標で2点選んだ時の線分が通る格子点がちょうどK点となるような2点の組み合わせは何個あるか求めろ 1 <= N,M <= 50 1 < K <= 50 考えたこと 何か誤読してて20分くらい溶かす 気づくと2点全列挙で…