競プロやってて思ったことをば - じょん・どうのブログ

　昨日、AtCode Beginners ContestのD問題の過去問見てたんですよ。あ、もちろん解けませんでしたよww

一応URL張っときますね。

例のごとく、ここから下はネタバレ注意！

問題文は下の通り

$N$ 個の整数 $A_{1}, A_{2}, . . ., A_{N}$ があります。

このうち $2$ つを選んでペアにする方法はN(N-1)/2通りありますが、それぞれのペアについて積を求め、小さい順に並べ替えたとき、 $K$ 番目にくる数は何になるでしょう？

まあ、細かい設定等はリンクから飛んで確認してください♪

　さて、この問題を解く上で、二分探索と尺取り法というアルゴリズムを用いるのですが、今回は二分探索について思ったことを書くので、尺取り法はまた別の機会に。

ちなみに、二分探索の考え方は下の画像の通り。

f:id:John_Doekun:20200318152821p:plain

さて、これを見て僕は数学のある定理を思い出したんです。その定理とは、「有界な無限数列は必ず集積値をもつ」（ボルツァノ‐ワイヤストラスの定理）というものです。というのも、この定理の証明をする際に、この二分探索的な操作をしていたんです！

その証明はというと、有界な無限数列をA_nとおくと、

|A_n| < L (L>0)であるとし、区間[ - L , L ]をI_0とおく。
このI_0を二等分し、A_nの項が無限に含まれている方の区間をI_1=[ a_1, b_1 ]とする。
１と２の操作を繰り返していくと、①I_i+1 ⊂ I_i　②b_i - a_i = (b_i - a_i)/2 = L/2^(i-1)　③iそれぞれに対し、区間I_iはA_n項を無限に含む。

の３つを満たす閉区間の列 I_i ( iは自然数 )ができ、すべてのI_iが共通して持っている値をαとおけば、I_i内の任意の項は [ a_i, b_i ] 内にあり、a_iとb_iはどちらもαに近づくので、αが集積値のひとつになるというものです。

　こういった、数学とプログラミングの共通点を見つけられると、なんだかうれしい気持ちになるんですが、僕だけかな？

キモイとか言わないで

短いけど今日はここまで。さいなら～♪

参考：微分積分学要論　戸田暢茂