tsutaj です。このたび、マイナビ出版から発行される 「アルゴリズム実技検定 公式テキスト[上級]~[エキスパート]編」 の執筆をさせていただきました。kenkoooo さん と けんちょんさん との共著です。2023/3/27 に発売予定です!
この本は PAST 本[エントリー]〜[中級]編の続編です。そのため、メインとする想定読者は「PAST で上級以上を目指したい人」ですが、AtCoder で青色・黄色を目指したい人にもぜひオススメしたい内容になっています。前回と同様、書籍内のサンプルコードは Python で書かれていますが、サポートページでは C++ にも対応しています(後述)
本記事では、本書の特徴と構成について書いていこうと思います。
本書の特徴
上級・エキスパートを目指すための発展的な内容を収録
前回の本は、「アルゴリズム自体の解説をしたあとに、そのアルゴリズムを使う問題を実際に解いて定着させる」という流れで解説していました。これは本書でも大切にしている部分です。
本書では合計で約 70 問の問題演習とその解説を通して、アルゴリズム技術の向上をサポートします。大半の問題は AtCoder 上にある既存のものになりますが、解説に適した問題がないものについては、アルゴリズムをそのまま適用すれば解けるオリジナル問題を AtCoder 上に新たに作っています。
本書の前半では、前回の本でも解説されていた「二分探索」や「動的計画法」をさらに掘り下げ、どのような問題設定でも確実に解けるように網羅的に解説しています!
また、前回の本では登場しなかったアルゴリズム・データ構造も多数解説しています。詳しくは後述する「本書の構成」をご覧ください。
豊富な図表による解説
当然ながら、本書で扱う内容は前回の本よりも難しくなります。読者の理解の助けになるよう、図表をできるだけ入れています。図表を見ながらソースコードを読むことで、何をしているのかが追いやすくなれば良いなと思っています。
非再帰かつ抽象化されたセグメント木の解説
以前、私は「セグメント木をソラで書きたいあなたに」という記事でセグメント木の構造について解説したことがありました。遅延セグメント木も同様に解説していました。この記事の内容はもちろん今でも通用はしますが、6 年前 (2017 年) に書いたこともあり、実装方針が少々古い内容になっています。
今回は「セグメント木をソラで書きたいあなたに 2023 年版」を目指し、非再帰かつ抽象化されたセグメント木・遅延評価セグメント木の解説を行いました!ブログ記事のようなくだけた表現を使わず、かつ分かりやすくなるように工夫を凝らして書きましたので、ぜひこの本でもう一度セグメント木を学んでいただければうれしいです。
また、本書後半のエキスパート編では、セグメント木の応用例である「セグメント木上の動的計画法」と「平面走査」についても解説しています。
網羅的な動的計画法の解説
上級やエキスパートを目指すにあたって、点の取りこぼしは致命的です。解ける問題は確実に解くのが大事です。
しかし確実に解くのは簡単ではありません。特に動的計画法 (DP) は汎用的に使えるテクニックなので、押さえておきたいパターンは何種類もあります。本書の上級編では、この動的計画法を網羅的に解説しており、基本形を一気に学習することができます!(けんちょんさんが頑張って書いてくださったパートです)
Python と C++ に対応
本書の紙面に掲載されているソースコードは Python のみとなっています。しかし、他のプログラミング言語で学習を進めたい方もいると思うので、サポートページには Python だけでなく C++ のソースコードも掲載しています。
サポートページはこちらです。
本書の構成
序章
アルゴリズム実技検定 (PAST) の紹介や、検定システムの使い方を紹介します。また、上級およびエキスパートのランク獲得に向けた対策方法についても解説しています。
1章〜6章
「上級」ランクを獲得するために、とくに押さえておきたい高度なアルゴリズムやテクニックを紹介します。また、例題や類題を通して実際にプログラミングすることで、ただ知っているだけでなく、問題に応じて正しくアルゴリズムを適用できるようになることを目指します。
7章〜9章
「エキスパート」ランクを獲得するために、学んできたアルゴリズムを組み合わせて、より発展的な問題を解いていきます。
詳しい目次
テキストで読みたい方は マイナビ出版の商品紹介ページ もご覧ください。
その他
前回の[エントリー]〜[中級]編では Python の基本的な使い方に関する解説がありましたが、本書にはありません。Python の基本的な文法を学びたい方は、前回の PAST 本など他の書籍を参考にしてください。
さいごに
競技プログラミングに関する書籍は近年多く登場していますが、PAST で上級・エキスパートを取るために必要となる内容を徹底解説した本は初めてではないかと思っています。このような内容について書籍媒体で解説できる機会はそうそうないと思うので、熱意を持って書きました。
本書が検定対策のみならず、アルゴリズム・データ構造の知識を深めたい人の助けになれば幸いです。
最後になりますが、共著者の kenkoooo さんとけんちょんさん、監修してくださった AtCoder 社様、本書の企画・進行をされた畠山さん、書籍編集でお世話になりました山口さん・伊佐さん、今回の書籍出版にご協力いただいたすべての関係者の皆様に深く感謝いたします。