プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プロコンで勝つための必須テクニック「アルゴリズム」と「データ構造」の基礎をマスター!

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』 (渡部 有隆 著、マイナビ、2015 年 1 月刊) は、プログラミングコンテストで問題を解くために必要なアルゴリズムとデータ構造の基礎を、オンラインジャッジでの演習と組み合わせて身につけるための入門書です。版元の紹介文は、プロコンで勝つための必須テクニックであるアルゴリズムとデータ構造の基礎をマスターする本と案内しています。競技に出ることを目標にする人だけでなく、整列や探索、グラフ、動的計画法を一通り自分で実装して、計算量を根拠に解き方を選べるようになりたい人に向いた一冊です。なお版元ドットコムの登録では、渡部 有隆 氏に加えて Ozy、秋葉 拓哉 の両氏の名前も並んでいます。

準備編、基礎編、応用編の 3 部構成

目次は 3 部に分かれています。1 部の準備編は、プロコンで勝つための勉強法として、オンラインジャッジを活用する学び方を扱います。2 部の基礎編はアルゴリズムと計算量から始まり、初等的整列、データ構造、探索、再帰と分割統治法、高等的整列と進んだあと、木、二分探索木、ヒープを経て、動的計画法、グラフ、重み付きグラフへ至ります。3 部の応用編はプロコン必携ライブラリと題され、高度なデータ構造、高度なグラフアルゴリズム、計算幾何学、動的計画法、整数論、ヒューリスティック探索を取り上げます。基礎編で単純な整列から始めて、木構造やグラフといった問題の表し方へ順に積み上げ、応用編でコンテストで繰り返し使う道具を揃える並びです。

計算量で解き方を選ぶ、競技に限らない読みどころ

競技プログラミング の問題は、正しい答えを出すことに加えて、決められた時間とメモリの範囲で答えを出すことが求められます。たとえば同じ並べ替えでも、要素を 1 つずつ挿入していく方法と分割統治で並べる方法では、入力の大きさが増えたときの処理時間の伸び方がまったく違い、入力の上限から逆算して許される計算量を見積もる力が解答の成否を分けます。基礎編が初等的整列と高等的整列を分け、その間に探索や再帰を挟んでいるのは、この見積もりの感覚を段階的に養うための並びと読めます。また、スタックやキュー、ヒープ、二分探索木といったデータ構造は、どの操作を速くしたいかで選び分けるものであり、その判断は検索や集計、スケジューリングのような業務のプログラムでもそのまま役に立ちます。解いたコードをオンラインジャッジに提出すると、正誤だけでなく時間超過も機械的に判定されるため、理解したつもりの箇所をすぐに確かめられるのが、この学び方の強みです。

前提になるプログラミングの力と類書との使い分け

読み進めるには、ひとつのプログラミング言語で配列や繰り返し、関数、再帰を使ったコードを書けることが前提になります。言語そのものの入門は扱わないため、文法から学ぶ段階であれば、まず入門書を一冊終えてから手に取るほうが効率的です。同じマイナビ系から出ている『プログラミングコンテストチャレンジブック』は、コンテストで使う技法を幅広く集めた本として知られており、基礎のデータ構造から順に積み上げたい人は本書を先に、手持ちの技法を広げたい人はそちらを、という使い分けが考えられます。アルゴリズムの本をコンテスト以外の目的で選びたい場合は、アルゴリズム本の選び方 で目的別の候補を比べておくと選びやすくなります。

一方で、2015 年刊の本であり、特定のコンテストサイトの出題傾向や、その後に広まったライブラリの使い方を追う内容ではありません。また文章で概念を読むだけで済ませたい人には、問題を解いて提出する前提の構成が重く感じられるはずです。

裏返せば、整列や探索の名前は知っていても、自分で書いたときに時間超過で落ちてしまう人や、木やグラフの問題になると手が止まる人にとって、本書は基礎から応用編の道具までを一本の筋で通せる教科書です。基礎編の各章で問題を解いて提出する習慣をつければ、計算量を見積もってから書くという、競技でも業務でも通用する手順が身につきます。