yosupo https://blog.hatena.ne.jp/yosupo/ よすぽの日記 https://yosupo.hatenablog.com/ 競技プログラミング 概要 直線n本から成るグラフが与えられる、これと直線y=kとの交点の数の最大値を求めよ(kは任意の実数) サンプル {0, 1, 0} 2 {1, 0, 2, 0} 3 {0, 1, 0, 1} 3 参考にならない参考画像 解法 僕は座標圧縮で、頂点と頂点の間の数を通る線の数を数えましたが、どうやら 座標をy軸方向に2倍して頂点とその上下の点を通る本数を数えるという方法もあるようです class PiecewiseLinearFunction { public: int maximumSolutions(vector<int> Y) { int count[100] = {}; //辺と辺の間… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosupo.hatenablog.com%2Fentry%2F2013%2F07%2F28%2F235507" title="TopCoder SRM586 Div1 Easy PiecewiseLinearFunction - よすぽの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://cdn-ak.f.st-hatena.com/images/fotolife/y/yosupo/20130728/20130728233934.png Hatena Blog https://hatena.blog 2013-07-28 23:55:07 rich https://yosupo.hatenablog.com/entry/2013/07/28/235507 1.0 100%