読者です 読者をやめる 読者になる 読者になる

1/30 発売!「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」

書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」が近日中に発売される予定です.会津大の渡部先生が著者で,Short Coding 本の Ozy さんと私が協力としての参加です.どうかよろしくお願いします.

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

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


本書はアルゴリズムとデータ構造の入門書です.整列,探索,木構造などをはじめとする基礎的なアルゴリズムとデータ構造を初学者向けに説明します.前提とするのは基礎的なプログラミング能力のみです.コード例では C++ を用いています.

これだけだと,よくある本のように思われるかもしれません.しかし,本書は非常にユニークな特徴として,オンラインジャッジシステムとの密な連携をしています.実装を行い,正しさのチェックを受けてから次に進むことで,基礎を着実に身に付けることのできる本になっています.

(Ozy さんのこちらの紹介記事も是非ご覧になって下さい.より簡潔に売りがまとまってます.)

オンラインジャッジシステムとは?

オンラインジャッジシステムとは,元々,プログラミングコンテストの過去問にオンラインで挑戦できるようにしたシステムです.プログラムを提出すると,自動でコンパイルと実行が行われ,テストケースに対する出力により正誤が判定されます.また,実行時間制限があり,正しいだけでなく,要求される効率で処理が行えるプログラムを作成する必要があります.

オンラインジャッジシステムは古くから UVA, POJ, SPOJ など世界中で多くのものが作られ運用されてきました.日本のものでは会津大の Aizu Online Judge (AOJ) が最も大きく有名なオンラインジャッジシステムの 1 つです.AOJ は以下のような特徴を持ち,日本人を中心として人気が高く,日々活発に用いられています.

  • 日本人が作成した問題が重点的に収録されている
  • API が公開されており,サードパーティ製のアプリケーション・サービスが数多く存在
  • コンテストの過去問のみならず,プログラミングやアルゴリズムの初学者向けの基礎問題コースを持つ



(AOJ の画面)

本書のオンラインジャッジシステムとの連携

さて,何を隠そう,本書の主著者は AOJ を作成され管理されている会津大学の渡部先生です.従って,言わずもがなですが,本書では AOJ と連携しています.しかも,AOJ 管理者の先生によって書かれた本ゆえに,非常に密な連携が実現されています.

本書は,前述した AOJ のアルゴリズム初学者向け基礎問題コースに沿っています.アルゴリズムの基礎的な説明と問題の紹介・解説を交互に繰り返して進んでいきます.できれば,AOJ 上で実際に問題を解きながら進めていってもらいたいと考えています.



(AOJ の基礎問題コース)

オンラインジャッジシステムを用いる意義

アルゴリズム入門書がオンラインジャッジシステムと連携する意義は非常に大きいと思います.実装をしてみることは,アルゴリズムをよりよく理解するための近道です.しかし,アルゴリズムやデータ構造の実装は,落とし穴だらけのことも多く,間違った実装で満足してしまう場合もしばしば見受けられます.一方,本書でアルゴリズムの学習を進めていけば,オンラインジャッジシステムとの連携により,正しく実装できたかをチェックしながら進むことができます.

ちなみに,タイトルでは「プログラミングコンテスト攻略のための」ということになっています.プログラミングコンテストでは,アルゴリズムを自在に応用できるよう十分理解すること,そしてアルゴリズムを正しく実装することが重要です.また,一部のアルゴリズムは,コンテスト本番で「ライブラリ」として用いられるように,自分で実装した後で蓄えておけるようなものとなっています.従って,この本はプログラミングコンテストを目指す初心者にお勧めだと思います.一方,個人的には,このブログでここまで紹介してきました通り,プログラミングコンテストには特に興味がないような方にも勧めできる本だと考えています.

目次

既存の本に対する位置づけ

プログラミングコンテストチャレンジブック

拙著「プログラミングコンテストチャレンジブック」はアルゴリズムとデータ構造の入門書ではありません.既存の本で説明されてこなかったプログラミングコンテストにおけるアルゴリズムの設計・活用に重点を置くため,入門書で解説されるような基礎知識の説明は省いていました.従って,アルゴリズムとデータ構造の基礎知識に自信がない方は,プログラミングコンテストチャレンジブックの前に本書を読んでいただけると良いと思います.

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

オンラインジャッジではじめるC/C++プログラミング入門

渡部先生の前著「オンラインジャッジではじめるC/C++プログラミング入門」では,オンラインジャッジを用いた同様のアプローチでプログラミング言語 C/C++ を学ぶことができます.本書はその続編とも言えますが,本書だけで独立して読んでいただけるようになっています.

オンラインジャッジではじめるC/C++プログラミング入門

オンラインジャッジではじめるC/C++プログラミング入門

Short Coding 〜職人達の技法

オンラインジャッジでは,解いた問題数などで努力が可視化されるため,つい競う心が生まれ学習が促進されるという一面があります.一方,本書のもう一人の協力者 Ozy さんの著書「ショートコーディング 職人達の技法」では,オンラインジャッジの変わった楽しみ方として,コードの長さをどれだけ短くできるかの競争を扱っています.