[Python] 競プロをきっかけにアルゴリズムを勉強し始める [Paiza]

はじめに

競プロ（競技プログラミング）ってありますよね。AtCoder とか、Paiza とか、LeetCode とか。今まで、そういうの全然興味なかったんです。機械学習やらデータサイエンスやら何年もやってきたので、コーディング技術にはそれなりに自信があり、「今さらそんなものやらなくても...」と舐めていたというのもあるかもしれません。

ですが、つい最近知人の勧めで LeetCode をやってみて、これは意外と役に立つなと気づきました。というのは、競プロの問題は様々な範囲に及んでいるので知識の総復習に役立つだけでなく、何より「効率性」が必要となってくるからです。

競プロでそこそこ難しい問題をやったことがある方はわかると思いますが、単に「動作するプログラム」を書くだけではパスしないことも多々あります。めちゃめちゃ時間がかかるプログラムや、めちゃめちゃメモリを食うプログラムは効率が悪いのです。LeetCode では問題を提出するたびに Runtime Beats 20% of users とか、Memory Beats 30% of users のように、自分のプログラムが他人のものと比べてどれくらい効率が良いのかということを表示してくれます。これを見る度に、「あー、自分のコードってクソなんだな」ということを実感します。時間制限(TLE)に引っ掛かることもしばしばです。

競プロのある程度のレベルの問題を解くには、定番アルゴリズムの知識は不可欠だと断言します。私自身は物理学科の出身で、プログラム自体は学生時代からよく書いていたものの、ルンゲ・クッタ法などの微分方程式やフーリエ変換、波動シミュレーションなどいかにも物理なものしか扱ったことがなく、コンピュータ学科のように定番アルゴリズムを体系的に勉強したことはありませんでした。その結果高難易度の問題では撃沈しまくっています。

ただ、あくまでプログラマーである以上、「競プロをやるかどうかに関わらず」やはり最低限のアルゴリズムの知識は必要だろうということで、改めて勉強を始めた次第です。その内容をこうやって記事に残し人に伝えることは、自身の知識の整理にもなるので、これから何回かに渡ってやっていきたいと思います。（物理学者ファインマンのテクニックとしても有名ですね）

ターゲット層

この記事を読んで頂きたいのは、

• ある程度のプログラミングの知識はある
• 高校程度の数学の知識もある
• アルゴリズムの知識はあまりない
• Paiza でAランク以上を狙う人
• Python がメイン言語

といった方々です。特に最後は重要です、私は Python と JavaScript 以外はほぼ書けません。

上述したように私は情報系の専攻ではなく、アルゴリズムに関してはど素人からのスタートです。もし間違いなどありましたら指摘して頂けますと幸いです。

Paizaラーニング

最初に LeetCode を紹介しましたが、最近ハマっているのは Paizaのスキルチェック です。というのも、

• AtCoder は土日開催のコンテストに参加しないとレーティングされない（土日は予定が多い）
• LeetCode も同様。さらに問題は英語
• Paiza は、スキルチェック問題を任意のタイミングで解ける。ただし一発勝負

という時間的な都合からです。Paiza はマジで一発勝負なので、時間内に正解に辿り着くまで何度も提出するということはできません。自分のコードに誤りがないか、見逃しているケースはないか、入念なチェックが必要になります。提出時はいつもハラハラです。まあ AtCoder も LeetCode もレーティング関係なしに過去問を解くだけならいつでもできます。特に LeetCode はジャンル別になっているので練習のために活用しています。。

ちなみに、私の現在(2024/1/17)のレートはSランクで、レートは2100前後です。B問題は半分くらい解き、8割ほどは100点を取れていますが、A問題とS問題はそれぞれ10問も手を出していません。迂闊に手を出して間違えるのが怖いからです笑

B問題とA・S問題の一番の差は、上述した「効率性」が問われるところです。B問題では、ちゃんと動くコードさえ書いていれば、時間制限にはまず引っかかりません。ですが、A問題以上だと効率の悪いコードは即アウトになります。これもA問題でやらかした例です。

では効率性とは何でしょうか？

計算量のオーダー

アルゴリズムを学習する時に、一番最初に出てくるテーマです。私もこれだけは学部時代に授業で習いました。詳細に関しては他に良記事がたくさんあると思いますので簡単に話しますが、要するに「計算時間がどのような関数で増えるか？」「メモリ消費量がどのような関数で増えるか？」ということです。それぞれ、時間計算量 Time Complexity、空間計算量 Space Complexity と呼ばれます。

時間計算量に関して簡単な例を挙げますと、一番わかりやすいのは for ループです。$n$ 個の正の要素を持つ配列の中から、最大のものを探すために各要素をチェックしていく場合、$n$ に比例して時間が増えていきます。Python コードならこのような感じです。

L = [3,4,2,7,19,32,5,...]

max_num = 0
for num in L:
    max_num = max(num, max_num)

一方で、この配列の中から「足して最大となる2つの数の組」を探す場合、

L = [3,4,2,7,19,32,5,...]

max_sum = 0
for i in range(len(L)):
    for j in range(i+1, len(L)):
        max_sum = max(L[i]+L[j], max_sum)

のような二重 for ループで求めることができます。この場合、全ての組み合わせを見つけるためには $_nC_2 = n(n-1)/2$ 通りを調べる必要があります。

この2つの違いは、指数です。$n$ が小さい場合には気になりませんが、$n$ が大きくなるにつれて下のプログラムは二乗に比例して時間が増えていきます。実際の実行時間は演算以外の要素も含まれるので綺麗に二乗とはならず、あくまで理論値と考えて下さい。

計算量はオーダー（漸近的評価）で表記します。記法はランダウの$O$と呼ばれるものを使い、$O(n)$ のように書きます。数学の極限を学習したことがある方ならピンとくるかと思いますが、$n^2 + n$ は $n → \infty$ の極限では $n^2$ として扱われます。また、「どのような関数で増えていくか」だけが知りたいので、係数は全て無視です。今回の場合、上の例は一次関数なので $O(n)$、下の例は二次関数なので $O(n^2)$ となります。また、データの大きさに関わらず一定の時間で終了するもの（定数時間）は、$O(1)$ と表記します。for ループがネストされると、その分掛け算で増えていくことになります。

ちなみに、上述の「足して最大となる2つの数の組」を求める上で、和を直接計算するのではなく、以下のように「上位2つの数を保存しておく」方法もあります。これならば for ループは一つですので時間計算量は $O(n)$ となります。このように、問題を同値な関係で言い換えることでより効率の良いアルゴリズムを探すのは基本です。

max_num = 0
second_num = 0

for num in L:
    if num >= max_num:
        max_num, second_num = num, max_num
    elif num > second_num:
        second_num = num

print(max_num + second_num)

計算量のオーダーは、あくまで「$n$ が大きい時」に効いてくるものです。PaizaスキルチェックのB問題以下では、そこまで大きくないので、気にする必要はないとも言えます。例えば以下のような3種類のアルゴリズムがあった場合、$n=10$ 程度であれば、オーダーが大きいにも関わらずアルゴリズムCが一番速く計算可能になってしまいます。

	計算回数	オーダー
アルゴリズムA	$10000$	$O(1)$
アルゴリズムB	$200n^2+100n$	$O(n^2)$
アルゴリズムC	$n^3+n^2$	$O(n^3)$

計算時間が具体的にどれくらいになるか？を見積もる方法として、コンピュータは頑張っても1秒間に $10^7 〜 10^8$ 回程度の演算しかできない と考えておくと良いかと思います。配列の長さが 500万 ($5*10^6$) であっても、$O(n)$ の時間計算量のプログラムなら問題なく終わるでしょうし、配列の長さが 1000 しかなくても、3重 for ループで $O(n^3)$ のプログラムを書けば、結構な時間がかかってしまうだろうと予測できます。

もう一つの空間計算量に関しては、どれほどのメモリを占有するかというものです。例えば $n$ 個の配列として格納するのか、$n \times n$ の二次元配列として格納するのか、といったような感じです。こちらは時間計算量ほど問題になることは少ないですが、S問題で「文字列の長さ」を測るものがあり、こちらなどでは馬鹿正直に文字列として扱うと $10^{16}$ ほどの長さになって一瞬で破綻する、というものがありました。

計算量を減らすためには、定番アルゴリズムの利用が欠かせません。「動くんだからいいじゃん」の段階から一つステップアップするためにも、是非先人たちの知恵を活用させて頂きましょう。私自身も学習しながら、今後何回かに渡って成果をここに記載していく予定です。

わかりやすい例 - 二分探索

じゃあ具体的にどんなアルゴリズムを使って時間計算量を減らすんだ？となるわけですが、一番わかりやすい例としてして 二分探索 binary search を挙げます。まず、こちらの動画を見て下さい。

ソート済みの配列(ここ重要) があり、その中から特定の値を探したいとなった場合に、最初から一つずつチェックしていったのでは、最悪 $n$ の時間がかかります。一方で、探索範囲を半分ずつにしていけば、$16 → 8 → 4 → 2 → 1$ のように指数関数で減っていくので、$\log_2(n)$ の時間で終了することになります。

じゃあ実際に時間が違うのか？ということで、notebook 上で試してみましょう。まず、2千万個のランダムな要素をもった配列を用意し、ソートしておきます。これだけの数のソートはどうしても時間がかかりますが、大体10秒前後で終わるかと思います。

## 2千万個のリストを作成し、ソート(10秒程度かかる)
import numpy as np
np.random.seed(42) ## 乱数作成用のシードを固定
arr = np.random.randint(1,20_000_000, size=20_000_000)
arr = sorted(arr)

ここで、前から順に探索していき、1500万となるインデックスを見つけたらそこで終了します。普通に for で実装します。実行すると、1秒ほど時間がかかるのがわかるかと思います。私の Macbook M2でも 1.37秒かかっています。

線形探索

%%time
## n = 15_000_000 となるインデックスを前から順に探す
for i in range(len(arr)):
    if arr[i] == 15_000_000:
        print(i)
        break

CPU times: user 1.37 s

次に二分探索を試します。このような感じで関数を定義し、実行します。

二分探索

%%time
def binary_search(arr, target):
    left_i = 0  # 探索範囲の左端のインデックス
    right_i = len(arr)-1  # 探索範囲の右端のインデックス
    while left_i <= right_i:
        mid_i = (left_i + right_i) // 2  # 探索範囲の中央のインデックス
        mid_value = arr[mid_i]  # 探索範囲の中央の値
        if  mid_value == target: #　中央値が探索値と一致した場合
            return mid_i
        elif mid_value < target: # 中央値が探索値より小さい場合
            left_i = mid_i + 1 # 中央値の1つ右を左端にする
        else:
            right_i = mid_i - 1 # 中央値の1つ左を右端にする
    return None 

binary_search(arr, 15_000_000)

CPU times: user 32 µs

なんと 32 µs です。違いは圧倒的ですね。

Paiza のどの問題だったか忘れましたが、二分探索を使わないととんでもないことになる問題はいくつかありました。

ライブラリの活用

二分探索がわかったとはいえ、このコード量を競プロ中に一々書くのはめんどくさい！という意見もあるかと思います。でも大丈夫なんです。そう、Python ならね。 実行時間はCなどのコンパイル型言語と比べ劣る Python ですが、豊富なライブラリという強力な装備品があります。これらを活用することで、記述量を圧倒的に少なくして時間短縮が可能です。

特に、numpy のメソッドには何度お世話になったことでしょう。二次元配列を作って列を取り出したい時には必須ですし、「ブロックを回転してはめる」などでは np.rot90() を使うだけで一瞬です。ソート関連の場合は、pandas も非常に有効です。

二分探索も、bisect という組み込みライブラリを使うことで簡単に実装可能です。詳しくは以下の記事が参考になります。「ある数より大きい最小の数値を探す」なんて場合も、この bisect.bisect_right() を使うだけです。

次回予告

とりあえず今回はイントロダクションということで、次回から私が勉強したてホヤホヤの様々な手法を紹介していこうかと思います。とりあえず現時点で話そうと思っているのは、

• スタックとキュー
• 再帰、動的計画法、メモ化
• ソート
• 木構造
• 幅優先探索・深さ優先探索
• Greedy Search とナップサック問題
• バックトラック法
• ダイクストラ法、A*

などなどです。その他、Python のライブラリを使ったテクニックも紹介予定です。

参考文献

本としては、ブックオフでたまたま見かけたこの2冊を使っています。今後追加で買うこともあると思います。アルゴリズム図鑑の方は視覚的に理解できるので、かなりオススメです。

• Pythonで学ぶ アルゴリズムとデータ構造　藤原 暁宏, 森北出版
• アルゴリズム図鑑　 石田 保輝, 宮崎 修一, 翔泳社

競プロ御用達の通称「蟻本」というものもありますが、現在は競プロ自体が目的ではなく、あくまでアルゴリズムの理解のために勉強しているので、とりあえずは買う予定はありません。また、学術的すぎる本も多分手を出さないと思います。数学も基本以外はだいぶ忘れてしまっているので...