komiyam https://blog.hatena.ne.jp/komiyam/ komiyamの日記 https://komiyam.hatenadiary.org/ アルゴリズム 私はしゃくとり法を書くのが苦手です。なので、しゃくとり法について自分なりに考えてみました。 しゃくとり法って結局何？ 二分探索は「ある点を基準に真偽が入れ替わるとき、その基準となる点を見つけるアルゴリズム」と説明できるし、座標圧縮は「何かの境界となり得ない座標を潰す技法」等と説明できます。 じゃあ、しゃくとり法は何かという答も持っているべきです。今の私なら「ある条件を満たす極小な区間を全て列挙するアルゴリズム」と答えます。 もう少し詳しく言葉にしてみます。 ある関数fは区間X=[l,r](開とか閉とか半開とかは適当)を受け取って真偽値を返します。例えば数列のある区間和がS以上になるかどうか、み… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkomiyam.hatenadiary.org%2Fentry%2F20120802%2F1343894601" title="しゃくとり法 - komiyamの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-08-02 17:03:21 rich https://komiyam.hatenadiary.org/entry/20120802/1343894601 1.0 100%