kanpurin https://blog.hatena.ne.jp/kanpurin/ かんプリンの学習記録 https://kanpurin.hatenablog.com/ 競技プログラミング 解説 ABC 動的計画法 グラフ 問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 2次元上の点が与えらえれる. すべての点集合について, その集合のすべての点を含む最小の長方形の内部にある点の総数を998244353で割った値を求めよ. 思考の流れ 全列挙できない場合は寄与分を考える でいけそう. 一つの点に対してその点を含むような長方形を作る集合の数を求めればよい. その点を含む集合が作る長方形の内部にその点は必ずある. そのような集合の数は個ある. その点を含まない集合のうち, その集合が作る長方形の内部にその点があるような集合の数を求めたい. 以下の図のようにその点を中心にして左上, 左下, 右上, … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkanpurin.hatenablog.com%2Fentry%2F2020%2F04%2F25%2F205653" title="ABC136 F - Enclosed Points - かんプリンの学習記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%7B1%5Cle%20N%5Cle%2010%5E%7B5%7D%7D Hatena Blog https://hatena.blog 2020-04-25 20:56:53 rich https://kanpurin.hatenablog.com/entry/2020/04/25/205653 1.0 100%