ferinの競プロ帳

競プロについてのメモ

2018-02-08から1日間の記事一覧

SRM647 div1 easy BuildingTowersEasy

考えたこと AtCoder Expressを思い出す x[i-1] から x[i] までの区間についてどこまで上げられるのかみたいなのを考える よくよく考えると前後それぞれから見ていけばいいだけ dp1[i] = (i以前の条件を満たす最大の高さ), dp2[i] = (i以後の条件を満たす最大…

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点全列挙で…