不必要な直線を取り除く他に、先ほどの性質を満たすためには「不必要な直線を取り除く」という動作も適宜行う必要があります。それでは、どのようなとき、どうなっていれば「不必要」と判断することが出来るのか、それについて考えていきます。前提として直線集合がすでに不必要な直線を全て取り除いてあると仮定します。このように仮定してしまえば、次に直線が不必要になるときは、直線を追加する際であると分かります。よって、「直線の追加クエリ」を行うときに、「追加する事によって不必要になる直線を調べる」ようにすれば良いことが分かりました。次に、どのような直線が不必要かについてですが、ここで次の図を考えます。これは不必要な直線が無い状況です。青の点となっていることが分かります。これは不必要な直線がある状況です。直線の設定は先ほどと変わりません。赤の点となっていることが分かります。直線の交点の位置関係が変わっています。座標を比較することにより不必要かどうかを判断できることが分かりました。点を選んでも判断はできますが、蟻本*2と同じ選び方としておきます)。交点なので、次の連立方程式を解けば求めることが出来ます。あることが分かりました。交点なので、次の連立方程式を解けば求めることが出来ます。あることが分かりました。あとはこれらの大小関係について調べればよいことになります。ここでは、「不必要であるかどうか」という不等式を作ります。座標とすれば良いです。不必要であることが分かりました。直線を追加する位置を二分探索で求める。その際、追加によって不必要となる直線は取り除く。最小値を取る直線を二分探索で求める。なることが分かりました。上記では、どのようなクエリ群であっても最小値を求められるものを説明しました。ここでは、そのクエリ群がある条件を満たしているようなときに、より高速化が可能であるため、それについて解説していきます。)であることを指します。)であることを指します。進めると、直線集合の先頭の直線が最小値を取らなくなるときがあります。後戻りしないため、もうこの直線は使わないことが分かります。単調」であるようなときを指します。分速くクエリをこなすことが出来ます。コード(C++)※注:このコードは追加クエリが単調であると仮定したものです。(力不足で一般的な状況のものが出来ていません...。x);}}};コードの説明ほぼ先ほどの議論をそのままコードに書いています。ときの最小値を返すとなっています。cht(true);といった感じで宣言します。することでそれぞれ最小値(最大値)クエリが単調であるか否かを指定することが出来ます(省略可)。});とすることで最大値クエリをこなすことが出来ます。実際に直線を追加していって、その後の最小値クエリの違いを見ていきます。-2上記例で行ったクエリを図にしてみると、次のようになっています。これで、確かに正しく出力出来ていることが分かりました。前述のように、上記コードは全ての状況に対応出来るものではないので注意してください。あとがき使える機会は式を見て割と分かりやすいですが、実装は慣れていないと難しそうです。そのため、問題を色々調べてみました(まだ全て解いてないです)。高速化出来るため、覚えておくとどこかで役に立つと思います。Game問題のURLはこちらです。問題のURLはこちらです。問題のURLはこちらです。問題のURLはこちらです。問題のURLはこちらです。検索プロフィールid:satanic0258C++、競プロ、数学に興味があります。質問やおかしな所、記事内に間違いなどありましたらコメントを頂けると嬉しいです。Round月別アーカイブTwitter@satanic0258さんのツイートはてなブログをはじめよう!satanic0258さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。