尺取り法，二分探索.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "-1//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "low 0 high 6 mid 3\n",
      "low 4 high 6 mid 5\n",
      "low 6 high 6 mid 6\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "### シンプル二分探索\n",
    "### ref https://qiita.com/Brutus/items/5653c6d3683d25e2cf89\n",
    "def binary_search(lst, item):\n",
    "    low = 0\n",
    "    high = len(lst) - 1\n",
    "    \n",
    "    while low <= high:\n",
    "        mid = (low + high)// 2\n",
    "        guess = lst[mid]\n",
    "        print('low', low, 'high', high, 'mid', mid)\n",
    "        if guess == item:\n",
    "            return mid\n",
    "        if guess > item:\n",
    "            high = mid - 1\n",
    "        else:\n",
    "            low = mid + 1\n",
    "    \n",
    "    return None\n",
    "my_list = [-4, -2, 2, 3, 6, 8, 9]\n",
    "binary_search(my_list, 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### abc155 D\n",
    "### ref https://atcoder.jp/contests/abc155/submissions/10189956\n",
    "def main():\n",
    "    import numpy as np\n",
    "    from bisect import bisect_left,bisect_right\n",
    "    n,k=map(int,input().split())\n",
    "    A=list(map(int,input().split()))\n",
    "    A=np.array(A)\n",
    "    A=np.sort(A)\n",
    "    Ap=A[A>0]\n",
    "    Az=A[A==0]\n",
    "    Am=A[A<0]   \n",
    "    lm,lz,lp=len(Am),len(Az),len(Ap)\n",
    "    Am2=Am**2\n",
    "    Ap2=Ap**2\n",
    "    #print(Ap,Am,Az,Ap2,Am2)\n",
    "    def cnt_product(x): #ある数字の組であってその積がx以下となるものの数\n",
    "        if x<0:\n",
    "            X=np.searchsorted(Am,x//Ap,side='right')\n",
    "            #print(X)\n",
    "            return X.sum()\n",
    "        \n",
    "        else:\n",
    "            ans=lz*(n-lz)+lz*(lz-1)//2+lp*lm\n",
    "\n",
    "            X=np.searchsorted(Ap,x//Ap,side='right')\n",
    "            Xd=np.count_nonzero(Ap2<=x)\n",
    "\n",
    "            Y=np.searchsorted(Am,(-x-1)//(-Am),side='right')\n",
    "            Yd=np.count_nonzero(Am2<=x)\n",
    "            \n",
    "            ans+=(X.sum()-Xd+lm**2-Y.sum()-Yd)//2\n",
    "            return ans\n",
    "\n",
    "    left=-10**18\n",
    "    right=10**18\n",
    "    while right-left>1:\n",
    "        mid=(left+right)//2\n",
    "        if cnt_product(mid)<k:\n",
    "            left=mid  ### left は必ずk個未満になる\n",
    "        else:\n",
    "            right=mid ### right　は必ずk個以上になる\n",
    "    print(right)\n",
    "\n",
    "if __name__=='__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 2], dtype=int64)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.searchsorted([1,4,7], [2,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from bisect import bisect_left, bisect_right\n",
    "n, k = map(int, input().split())\n",
    "A = list(map(int, input().split()))\n",
    "A = np.array(A)\n",
    "A = np.sort(A)\n",
    "Ap = A[A>0]\n",
    "Az = A[A==0]\n",
    "Am = A[A<0]\n",
    "lm, lz, lp = len(Am), len(Az), len(Ap)\n",
    "Am2 = Am**2\n",
    "Ap2 = Ap**2\n",
    "def cnt_product(x): #ある数字の組であってその積がx以下となるものの数\n",
    "    if x<0:\n",
    "        X=np.searchsorted(Am,x//Ap,side='right')\n",
    "        #print(X)\n",
    "        return X.sum()\n",
    "\n",
    "    else:\n",
    "        ans=lz*(n-lz)+lz*(lz-1)//2+lp*lm\n",
    "\n",
    "        X=np.searchsorted(Ap,x//Ap,side='right')\n",
    "        Xd=np.count_nonzero(Ap2<=x)\n",
    "\n",
    "        Y=np.searchsorted(Am,(-x-1)//(-Am),side='right')\n",
    "        Yd=np.count_nonzero(Am2<=x)\n",
    "\n",
    "        ans+=(X.sum()-Xd+lm**2-Y.sum()-Yd)//2\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}