PAST公式テキストを書きました

このたび、マイナビ出版から発行される「アルゴリズム実技検定 公式テキスト（エントリー～中級編）」の執筆をさせていただきました。kenkooooさんとの共著です。

アルゴリズム実技検定 公式テキスト[エントリー~中級編] (Compass Booksシリーズ)

アルゴリズム実技検定（通称PAST）のための学習参考書です。PASTに限らず、普段のコンテストのための学習教材としても使うことができます。

本記事では私個人の意見も交えつつ、執筆で重視したことや競技プログラミング（競プロ）を既にやっている人が気になっていそうな点などを書いていこうと思います。

本書の特徴

Amazonの商品ページなどにも本書の特徴が書かれていますが、特に次の2点が大きな長所だと考えています。

• Pythonの文法解説から始まってエントリー→初級→中級と順番に解説していくので、プログラミング自体が初めてという人でも段階を踏んで学習できる
• PASTとAtCoderの問題を合計で約50問解説し、その多くに図解が付いているので、実際の問題を用いて理解を深められる

競プロの学習に使える書籍は蟻本（通称）を筆頭にいくつか書かれていて、本書の執筆中にもけんちょん本（通称）という素晴らしい本が出版されました。それぞれの書籍では重視している内容や読者の想定レベルが少しずつ異なります。

本書はPAST公式テキストという位置付けなので、PASTの出題範囲や出題傾向に沿って構成を考えています。PASTで出題されにくい内容や、知らなくても問題が解けるような知識は思い切って省き、Pythonの文法解説や出題されやすいアルゴリズムの解説にページ数を使っています。そのため、

時間を掛けて手を動かせば、本書の内容だけでPAST中級が取得できる

とまで言える内容になっていると考えます。（もちろん複数の教材を併用したほうが学習効率が上がるのは言うまでもありませんが）

本書の掲載範囲

普段のコンテストでは出題範囲というものは存在しないも同然ですが、PASTには公式Webサイトに「出題範囲」という記載が存在します。本書の第4章がエントリー、第5章が初級、第6章が中級の出題範囲に対応しています。

本書は中級の出題範囲として記載されているアルゴリズムなどの解説に最も注力しています。Amazonの商品ページに掲載されているサンプルから第6章の目次を引用します。この第6章だけで約200ページ、本書の半分以上を占めています。

この後に第7章が続きますが、新しい知識やアルゴリズムは登場しません。第6章で解説したアルゴリズムを複数組み合わせる問題や、遷移が少し複雑な動的計画法の問題などを扱います。

扱っている問題について

なるべくPASTの過去問を扱うようにしましたが、該当する問題がない場合はAtCoder Beginner Contest（ABC）や他のコンテストの問題も使っています。特に動的計画法の解説ではEducational DP Contestの問題がとても使いやすくて助かりました。

解説に適した問題がAtCoderにないアルゴリズムについては、アルゴリズムをそのまま適用する問題をいくつかAtCoder上に作成しました。発売までには公開される予定です。Aizu Online Judgeなどには既に適した問題が存在するのですが、書籍で扱う全ての問題をAtCoderでジャッジできるようにしたいという方針からこのような形になりました。

Pythonについて

言語がPythonであることは執筆のお話をいただいた時点で決まっていました。私個人としてもPythonを用いて良かったと考えています。Pythonの文法などを解説する第4章は私が担当しましたが、動かすために間接的に必要となるコードが少ないことは大きなメリットだと書きながら思いました。

私もkenkooooさんも競プロでPythonを使っているわけではないので、結果的に解答例は技巧的でなく平易な実装になったと思います。例えばリスト内包表記や引数の複雑なスライス記法は本編では用いていません。その代わり付録で、これらの応用的な記法や本編で扱っていないPythonの関数などを紹介しています。

PyPyについても少しだけ触れています。解説で扱う問題のいくつかは、素直な実装で通常のPython（CPython）で提出しても通らなかったので、PyPyで提出するように注意書きを付けています。

AtCoderの色について

本書を競プロの学習教材として使いたい人は、「この本の内容でAtCoderの何色まで到達できるのか」という疑問を持つと思います。

一概に言えるものではないので完全に私個人の意見ですが、およそ水色くらいだと思っています。中級レベルの後半で解説しているアルゴリズムを素直に適用できる問題が、最近のABCで出題されたとき、AtCoder ProblemsのDifficulty計算では水色に判定されることが多いからです。

しかし数学的知識を筆頭に、本書でカバーできない内容はABCのB～C問題でも出題されます。また最近は計算誤差の扱いをテーマとする問題がしばしば出題されています。これらは過去問で学習したり、コンテスト中に検索して知識を得ることに慣れたり（実はこっちのほうが重要かも）する必要があります。

アルゴリズムを素直に適用する問題は、知識が広く浸透していて検索にも引っかかりやすいため、コンテストでも正答率が高い傾向があります。そうすると同点の参加者が増え、正答時刻とペナルティの個数がパフォーマンス値に大きく影響します。

本書の内容を網羅して速度と正確さを常に発揮し続ければ青までは届くのではないかと思いますが、それよりは数学的知識やセグメント木などのデータ構造にも触れていったほうが青までの効率は良いと思います。

最後に

IT技術者のスキル評価において、アルゴリズムの知識とそれを実装に落とし込む能力が、これまで競プロのコミュニティで名前が挙がることが少なかった企業からも注目されてきています。そうすると必然的に、これらを学習する手段にも注目が集まります。

私が競プロを始めた3年前と比べると、学習教材は増えていますしこれからも増えていくでしょう。競プロから入った人もPASTから入った人も何を使えばいいのか迷うかもしれませんが、本書はそのどちらにもオススメできる内容となっています。色々見比べて、本書が合いそうだなと思ったら是非ご購入いただければと思います。

以上、真面目な（？）書籍紹介記事でした。私個人の体験談は発売後に別の記事で書くつもりなので、そちらもよろしければどうぞ。