【Python】classを使って競プロ用ライブラリを作りたい！【超初級】

　やだやだやだ作りたい作りたい作りたい～～～～～！

# この記事の目的

　競技プログラミングでは、問題を解くうえで便利なデータ構造というものがいくつかあります（セグメント木、UnionFind、優先度付きキューなどなど……名前だけは聞いたことのある方もいるのではないでしょうか）。これらのデータ構造は、**ライブラリ**として作成しておくと、使いたいときにさっと取り出してパッと使えるので非常に便利です。
　このライブラリ、Python では **class** を用いて作成することが多いのですが、class には機能が多く、イチから学ぶのは結構大変です。そのくせ、「競プロのライブラリを作る」という場面ではほとんど使わない機能も多いです。（継承、ゲッター/セッター、...）
そこで本記事では、class で競プロライブラリを作成するのに最低限必要な要素のみに絞って紹介したいと思います。
　さらに細かい仕様や機能については書籍[^1]や[公式ドキュメント](https://docs.python.org/ja/3/tutorial/classes.html)をご覧ください。

[^1]: O'REILLYの『入門 Python3』はオススメです。かなり詳細に書かれているため初学者には過剰でわかりづらいですが、持っておいて損はないです。

# classって何？

　皆さんが普段から使っている数値、文字列、リスト、……これらは**オブジェクト**と呼ばれるものです。オブジェクトには、整数を表す int 、文字列を表す string など、たくさんの**型**があります。これらは`type()`関数によって調べることができます。

```
>>> a = 7
>>> b = "onigiri"
>>> c = {2, 4, 6}
>>> type(a)
<class 'int'>
>>> type(c)
<class 'set'>
```


　各オブジェクトはそれぞれデータ（**属性**）を持っています。例えば、上の変数 $a$ は整数 $7$ を属性に持つ int オブジェクト、$c$ は「それぞれ整数 $2, 4, 6$ を持つ3つの int オブジェクト」を属性に持つ set オブジェクトです。

　また、オブジェクトにはその型ごとに固有の機能（**メソッド**）があります。例えばlist型なら

|メソッド名|機能|
|:--:|:--:|
|`list.append(x)`| 末尾にオブジェクト $x$ を追加   |
|`list.pop()` | 末尾のオブジェクトを取り出す|
|`list.sort()` | 配列をソートする            |
|`list.count(x)`| 配列中の $x$ の個数を数える     |


といった具合です。

　class は、独自の属性・メソッドを持つ**新たな型を定義する**ためのキーワードです。これを用いれば、「複数の頂点と辺を属性に持つグラフのオブジェクト」や、「名前、年齢、住所、……を属性に持つヒトのオブジェクト」など、もともと Python に存在しないオブジェクトを自由に作ることができます。


# 累積和を管理するクラス
　本記事では、二つの list オブジェクトとその長さ（ int オブジェクト）を属性に持つ型を作りたいと思います。


## 属性を定義しよう！

　型の定義は、`class （型の名前）`から始めます。
　とりあえず名前は`Ruiseki`として、まずは属性、つまりそのオブジェクトがどういうデータを持つのかを定義しましょう。

```Python
class Ruiseki:
    def __init__(self, l):
        self.lis = l
        self.N = len(l)
        self.rui = [0]*(self.N + 1)
```

　突然いろいろなものが出てきましたが、詳しくは後から説明するので、今はここに書かれた3つの`self.～`に注目してください。
　これらが**属性**です。属性は`__init__()`の中で定義します。各属性は、`self.（属性の名前）`という変数を用いて表します。
　まず、`lis`という名前の属性を定義します。ここでは、`__init__()`の引数`l`が、`self.lis`としてそのままあてがわれています。これは、後にオブジェクトを作成する際に引数として渡すもの（今回は配列を想定しています）がそのオブジェクトの属性の一つとなることを表しています。

　「オブジェクト作成時に引数を渡す」という操作に馴染みがなくても、競技プログラミングに触れたことがあれば誰でも一度はやったことがあるでしょう。

``` 
>>> x = int(input()) # intオブジェクト作成時に、引数として標準入力された文字列を渡している
>>> 
>>> l = [3, 1, 4, 1, 5]
>>> a = Ruiseki(l) # Ruisekiオブジェクト作成時に引数として配列を渡すと
>>> a.lis # オブジェクトの属性lisに登録されている
[3, 1, 4, 1, 5] 
```

　個別のオブジェクトの属性には`（オブジェクトを表す変数）.（属性の名前）`でアクセスすることができます。
　同時に定義されていた属性`N`は渡された配列`l`の長さ（整数）を持ち、`rui`は長さ`self.N + 1`の配列を持っています。

```
>>> a.N
5
>>> a.rui
[0, 0, 0, 0, 0, 0]
```

　ここで、
>あれ？`__init__()`の引数は`self`と`l`の二つあったのに、オブジェクトを作るときは`l`しか渡さなくていいの？

と思った人は鋭いです。これは後ほど説明します。


## メソッドを定義しよう！

　さて、属性が設定できましたが、このままではただリスト二つと整数を一つ持っているだけのただの箱です。次はこの箱に新しい機能、メソッドを追加していきましょう。今回欲しい機能としては

- 累積和を取る
- 元の配列の $i$ 番目の要素を知る
- $i$ 番目の要素までの累積和を知る
- 累積和が初めて $x$ 以上になるインデックス $i$ を知る

あたりでしょうか。順に実装していきましょう。

　まずは累積和を取るメソッド`build()`を作ります。これがないと始まりません。累積和を計算する上で必要な情報はすべて属性として持っているので、特に引数を取る必要はありません。

```Python
    def build(self):
        for i in range(self.N):
            self.rui[i+1] = self.rui[i] + self.lis[i]
```

　ここでは単純に、長さ`self.N`の配列`self.lis`の累積和を順に配列`self.rui`に格納していく、という気持ちで大丈夫です。変数の名前が見慣れないだけで、普段と変わりません。

```Python
n = 5
f = [3, 1, 4, 1, 5]
g = [0]*(n+1)
for i in range(n):
    g[i+1] = g[i] + f[i]
```

　では、このメソッド`build()`を実行したらどうなるでしょうか。

```
>>> l = [3, 1, 4, 1, 5]
>>> a = Ruiseki(l)
>>> a.rui # build前は初期状態のまま
[0, 0, 0, 0, 0, 0]
>>> a.build()
>>> a.rui
[0, 3, 4, 8, 9, 14]
```

　見事累積和が計算できました！最初に定義した属性`rui`に累積和が格納されています。

　では次に、元の配列の $i$ 番目の要素を返すメソッド`access()`を作りましょう。引数として $i$ を取ります。

```Python
    def access(self, i):
        return self.lis[i]
```

　元の配列は属性`lis`として持っているので、`self.lis[i]`を返すだけです。簡単ですね。
　本来は $i$ が`self.N`以上だった場合に例外を投げる、などの処理を行った方がよいのですが、どうせ配列`self.lis`にアクセスする際に Python が勝手に例外を投げてくれるので今回はよしとします。

```
>>> a.access(0)
3
>>> a.access(10)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\home\python\ruiseki.py", line 12, in access
    return self.lis[i]
IndexError: list index out of range
``` 

　同様に、$i$ 番目まで（ $i$ 番目は含む、つまり閉区間）の累積和を返すメソッド`cumulate()`は、

```Python
    def cumulate(self, i):
        return self.rui[i+1]
```


と書けますね。インデックスが $1$ ずれることに注意してください。



# で、結局`self`ってなんなのさ

　さて、そろそろずっと存在していた謎の引数`self`について説明します。わかりやすさを優先するため厳密には異なると思います。ご了承ください。
　あるオブジェクトがメソッドを呼び出すとき、**内部的に**そのメソッドを呼び出したオブジェクト自身が引数として渡されます。そして、そのオブジェクトはほかの引数を押しのけて第一引数として渡されます。
　これらの処理はあくまで内部的に行われるので、呼び出す際に明示的に引数として与えることはしません。ただし、メソッド側では、オブジェクト自身が引数として与えられることを考慮して記述する必要があります。これが`self`の正体です。
　つまり、`access()`を例にとると、
>「`access()`を呼び出したオブジェクトを`self`として、その`self`の持つ属性`lis`の $i$ 番目を返す」

という処理を行っている、ということです。オブジェクトの属性には`（オブジェクトを表す変数）.（属性の名前）`でアクセスすることができるので、`self.lis[i]`を返せばよいわけです。

>`a.access(3)`
↓
`access()`メソッドを呼び出したのはオブジェクト`a`
↓
オブジェクト`a`の属性`lis` (= `a.lis` = `[3, 1, 4, 1, 5]`)の $3$ 番目
↓
$1$

-------

　実は、以下のコードでも完全に同じように動きます。

```Python
    def access(hoge, i):
        return hoge.lis[i]
```

　この場合、このメソッドの中では第一引数として渡されるオブジェクトの名前を`hoge`として扱っています。何の問題もありません。[^2]

[^2]: 同一スコープ内に同名の変数があった場合は大問題ですが、今回注目しているのはそこではありません。

　ただし、ほとんどの場合において慣例的に`self`という名前が使われており、他人がコードを見た際に混乱が生じやすい、などの理由により、第一引数の変数名としては`self`を用いることが<font color="red">**極めて強く推奨**</font>されています。無意味な逆張りはしないようにしましょう。


# まだ説明してないことがあるだろ

　ここまでに書いたコードを振り返ると、最初に属性を定義した際の形式とメソッドを定義した形式がとても似ていることが分かります。実のところ、属性を定義する際に用いた`__init__()`はメソッドの一種であり、**特殊メソッド**と呼ばれるものの一つです。

特に`__init__()`は、
「オブジェクト作成時に、オブジェクトを初期化するために自動的に呼ばれるメソッド」です。

　この内部で属性を定義しておくことで、オブジェクト作成と同時にオブジェクトに属性が与えられるため、とても便利、というわけです。
　実際、`__init__()`を丸ごと削除してしまってもオブジェクトは作成できるものの、

```
>>> a = Ruiseki()
>>> a.lis
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'Ruiseki' object has no attribute 'lis'
```

このように、「属性`lis`なんてないよ」と怒られてしまいます。

## `__init__()` の活用
　ところで、上で書いたコードで、`cumulate()`を呼ぶ前に必ず`build()`を呼ばなくてはならないことに気付いたでしょうか。

```
>>> l = [3, 1, 4, 1, 5]
>>> a = Ruiseki(l)
>>> a.cumulate(3)
0
>>> a.build()
>>> a.cumulate(3)
9
```

　`build()`を呼ぶ前は`rui`の中身は全部0なので、見当違いな答えを返してしまいます。もしコンテストでうっかり`build()`を忘れて提出しようものなら、WAまっしぐらです。
　そこで、`__init__()`の中身を次のように変更してみましょう。

```Python
    def __init__(self, l):
        self.lis = l
        self.N = len(l)
        self.rui = [0]*(self.N + 1)
        self.build()
```

　こうすると、オブジェクトを作成すると同時に、初期化の一環として`build()`が呼ばれます。こうすれば、わざわざ自分で`build()`しなくてもよくなります。

```
>>> l = [3, 1, 4, 1, 5]
>>> a = Ruiseki(l)
>>> a.cumulate(3)
9
```

　あるいは、`build()`メソッドを削除して、``__init__()``を次のように書き換えても構いません。

```Python
    def __init__(self, l):
        self.lis = l
        self.N = len(l)
        self.rui = [0]*(self.N + 1)
        for i in range(self.N):
            self.rui[i+1] = self.rui[i] + self.lis[i]
```

　`build()`で行っていた処理を丸々`__init__()`の中に移しました。最初に一度だけ行う処理であれば、このように`__init__()`をうまく使うことでより楽にオブジェクトを扱うことができます。

----------------

　では最後に、まだ実装していなかった、累積和が初めて $x$ 以上になるインデックス $i$ を返すメソッド`lower_bound()`を作りましょう。$O(N)$での線形探索もいいですが、私は賢いので$O(\log N)$の二分探索をすることにします。

```Python
    def lower_bound(self, x):
        lo, hi = 0, self.N
        while hi - lo > 1:
            mid = (lo + hi) // 2
            if self.rui[mid] < x:
                lo = mid
            else:
                hi = mid
        return hi - 1
```

　インデックスのずれを考慮し、$-1$ してから出力しています。

　これで無事累積和をもつ新しいクラスの完成です！おめでとうございます。

<details><summary>コード全体を見る</summary><div>

```Python
class Ruiseki:
    def __init__(self, l):
        self.lis = l
        self.N = len(l)
        self.rui = [0]*(self.N + 1)
        self.build()

    def build(self):
        for i in range(self.N):
            self.rui[i+1] = self.rui[i] + self.lis[i]

    def access(self, i):
        return self.lis[i]

    def cumulate(self, i):
        return self.rui[i+1]

    def lower_bound(self, x):
        lo, hi = 0, self.N
        while hi - lo > 1:
            mid = (lo + hi) // 2
            if self.rui[mid] < x:
                lo = mid
            else:
                hi = mid
        return hi - 1
```

</div></details>

```
>>> l = [3, 1, 4, 1, 5]
>>> a = Ruiseki(l)
>>> a.access(2)
4
>>> a.cumulate(4)
14
>>> a.lower_bound(7)
2
```



# 作れたはいいけど、何がうれしいの？

　別にわざわざ慣れない class を使わなくても、

```Python
n = 5
f = [3, 1, 4, 1, 5]
g = [0]*(n + 1)
for i in range(n):
    g[i+1] = g[i] + f[i]
```

をコピペすれば十分じゃん、と思う方もいるかもしれません。
　確かに、 class を使わず main 関数内でいくつかの変数と関数を定義するだけで済む場合もあります。しかし、例えば累積和を取りたい配列が100個あったらどうでしょう？

```Python
n1 = 5
f1 = [3, 1, 4, 1, 5]
g1 = [0]*(n1+1)
for i in range(n1):
    g1[i+1] = g1[i] + f1[i]
n2 = 6
f2 = [9, 2, 6, 5, 3, 5]
```

腱鞘炎になる前にやめておきましょう。
　このように、同一の操作を行いたい対象が多数存在する場合、class を用いたライブラリは本領を発揮します。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">この前のコンテストでセグ木26本生やした時結構気持ちよかったんだけど、冷静に考えてセグ木を26本生やすことに快楽を覚えてるのヤバイな</p>&mdash; 煎茶 (@sentya7) <a href="https://twitter.com/sentya7/status/1235205701460307969?ref_src=twsrc%5Etfw">March 4, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>


　その他、一度 class を定義してしまえば、ブラックボックスのようにその中身を気にせずメソッドを使えるため、**コードがすっきりする**、という利点があります。競プロなど、超短時間でデバッグを行う場合、確認すべき箇所が少なくて済むのは大きなメリットです。

　ただ、先ほど挙げたような「累積和を取りたい配列が100個ある」場合は、二次元配列とfor文で簡単に実現することができます。何でもかんでも class 化すればいいってわけではないことは頭に入れておきましょう。


# 終わりに
　幸い競プロ（特に AtCoder）で Python を使う人は割と多く、先人たちがさまざまなライブラリを class 化して公開してくれています。ありがたく使わせてもらいましょう。
　ただ、その内部でどういった挙動をしているか把握していると、データ構造の応用やデバッグの際に大きく有利となります。理解を深めるためにも、コードを読み込む、あるいは一度自分で書いてみることをオススメします。また、この記事がその一助となれば幸いです。

　**君もPythonで変態データ構造を作ろう！**