尺取り法と二分探索の「本当の」違い【ゆっくり解説】
Рет қаралды 2,090
3 ай бұрын#ゆっくり解説
#競技プログラミング
#atcoder
競技プログラミングの問題で、尺取り法が使われる問題は多くあります。そのような問題は「余計な log はつくものの、二分探索でも解けることが多い」とされることが多いです。しかし、「尺取り法を二分探索で代用できない」問題も存在します。そのような問題に見られる特徴は果たして何なのか。尺取り法と二分探索、この 2 つの手法の「本当の」違いは何なのかに焦点を当てる形で、解説していきます。
------------
当チャンネルでは、競技プログラミング（コンテスト参加・作問など）についての発信を行っていきます！
AtCoder アカウントはこちら→atcoder.jp/users/AngrySadEight
X はこちら→ / sad_eight
@AngrySadEight 3 ай бұрын
0:16 ここの部分について、「尺取り法」と「二分探索」が逆です。訂正いたします。
@user-eh3oi5rh7g Ай бұрын
オーダーがより小さいのでお得、みたいな話かと思っていたらもっと実践的でためになる話だった！
@user-fh6xi3xr7r 21 күн бұрын
ためになった。 BGMでっか。
@AngrySadEight 21 күн бұрын
BGMについては、他の方からもご指摘を受け、最近の動画ではボリュームを落としています。ご理解をよろしくお願いします。