動的(インタラクティブ)なグラフ図示(Jupyter + ipywidgets interact)

競技プログラミングの問題を解く上では、あたりをつける上で図示は有効となるケースが多い。この際に入力の値を変化させることでさらに効果的となることがおおい。jupyterを用いると以下のようなインタフェースをすぐに実現できる。

題材

Educational Codeforces Round 80 A.Deadline https://codeforces.com/contest/1288/problem/A
N,d,xが1以上の正の整数で、$ d \leq x $ のとき、以下を満たすxがあるか調べろ。
$$ n \geq \left\lceil \frac{d}{x+1} \right\rceil + x $$ ここで$\lceil a \rceil$ は（ガウス関数ではなく）a以上の最小の整数である(例: 3.1なら4, 3なら3)

静的な図示

問題のサンプルでNO, YESとなる例をそれぞれ左、右に示す。これは単にmatplotlibの機能を使えばよくすぐにかける。

青が$y=n$の線で黄が$ y= \left\lceil \frac{d}{x+1} \right\rceil + x $、緑は天井関数をかける前のプロットである。

このように示すことで、青の線と黄色の線の交点が存在するかでYES/NOが決まることが分かる。（もちろん、不等式なのだからこれは自明なのだが...)

%matplotlib inline
import matplotlib.pyplot as plt
from ipywidgets import interact
import numpy as np

fig, (axL, axR) = plt.subplots(ncols=2, figsize=(10,4))

n,d = 5,11
xaxis = yaxis = 8
x = np.linspace(1, n, num = 100)
y1 = [n] *100
y2 = np.ceil(d / (x + 1) ) + x
y3 = d / (x + 1) + x
axL.plot(x, y1)
axL.plot(x, y2)
axL.plot(x, y3)
axL.set_xlim(0, xaxis)
axL.set_ylim(0, yaxis)
axL.grid(True)

n2,d2 = 5,4
xaxis = yaxis = 8
x2 = np.linspace(1, n2, num = 100)
y21 = [n2] *100
y22 = np.ceil(d2 / (x2 + 1) ) + x2
y23 = d2 / (x2 + 1) + x2
axR.plot(x2, y21)
axR.plot(x2, y22)
axR.plot(x2, y23)
axR.set_xlim(0, xaxis)
axR.set_ylim(0, yaxis)
axR.grid(True)

fig.show()

動的な図示

interactを使うとn, dを可変に動かすスライダーができる。

%matplotlib inline
import matplotlib.pyplot as plt
from ipywidgets import interact
import numpy as np

d = 20
n = 20
import math

xaxis = yaxis = 20
nlimit = 20
dlimit = 100

@interact(n=(1, nlimit), d = (1,dlimit))
def f(n, d):
    x = np.linspace(1, n, num = 100)
    y1 = [n] * 100
    y2 = np.ceil(d / (x + 1) ) + (x)
    y3 = d / (x + 1) + x
    plt.xlabel("x-axis")
    plt.ylabel(" y-axis")
    plt.plot(x, y1)
    plt.plot(x, y2)
    plt.plot(x, y3)
    plt.xlim(0, xaxis)
    plt.ylim(0, yaxis)
    plt.grid(True)
    plt.figure(figsize=(1,1))
    plt.show()