アルゴリズム実技検定 公式テキスト[上級]〜[エキスパート]編

書籍情報

発売日 : 2023年03月27日

著者/編集 : 大槻兼資/杉江祐哉/中村謙弘/AtCoder株式会社 高橋 直大

出版社 : マイナビ出版

発行形態 : 単行本

書籍説明

内容紹介

世界最高峰の競技プログラミングコンテストを運営するAtCoderが主催する検定試験PASTの公式本。

目次

序章 アルゴリズム実技検定と本書の構成について
0.1 試験要項
0.2 本書で使用するプログラミング言語“ Python ” について
0.3 本書の構成

[上級編]
第1章 二分探索 発展
1.1 二分探索を適用できる問題
1.2 最小値の最大化(最大値の最小化)
1.3 平均値最大化・中央値の最大化
1.4 まとめ

第2章 動的計画法 発展
2.1 動的計画法の復習(ナップサック問題)
2.2 前回の情報を持ちながら進めていく動的計画法
2.3 さまざまな「部分問題への分け方」の動的計画法
2.4 動的計画法の高速化のためのテクニック
2.5 木上の動的計画法
2.6 その他の動的計画法

第3章 頻出テクニック
3.1 変数を固定して考えよう
3.2 尺取り法
3.3 償却計算量(ならし計算量)
3.4 章末類題

第4章 頻出データ構造・アルゴリズム
4.1 グラフ理論の用語について
4.2 UnionFind(素集合データ構造)
4.3 最小共通祖先(Lowest Common Ancestor)
4.4 章末類題

第5章 ネットワークフロー
5.1 最大流問題
5.2 最小費用流問題

第6章 セグメント木
6.1 セグメント木(Segment Tree)
6.2 遅延評価セグメント木(Lazy Segment Tree)
6.3 章末類題

[エキスパート編]
第7章 セグメント木上の動的計画法
7.1 問題
7.2 まとめ
7.3 章末類題

第8章 平面走査
8.1 問題
8.2 まとめ
8.3 章末類題

第9章 難問にチャレンジ!
9.1 問題

著者情報

大槻兼資
大槻 兼資(おおつき けんすけ):1988年生まれ。2014年東京大学大学院情報理工学系研究科修士課程修了。修士(情報理工学)。現在、株式会社 NTTデータ数理システム顧問、モノグサ株式会社コンテンツアーキテクト。数学や情報科学の諸分野の啓蒙活動に従事。著書に『問題解決力を鍛える!アルゴリズムとデータ構造』講談社 (2020) がある。趣味は競技プログラミング、虫食算作り、国内旅行など。
杉江祐哉
杉江 祐哉(すぎえ ゆうや):20歳のときに競技プログラミングに出会い、以降ts u ta jというユーザー名でAtCoder等のコンテストに参加。北海道大学競技プログラミングサークル所属時、アルゴリズムやデータ構造に関する勉強会資料の公開やオリジナル問題の出題・プログラミング合宿の開催など精力的に活動した。現在はモノグサ株式会社でソフトウェアエンジニアとして従事する一方、競技プログラミングの作問支援ツールの開発も行っている。
中村謙弘
中村 謙弘(なかむら けんこう):ニートの時に競技プログラミングに出会い、AtCoderでプログラミングを学ぶ。ソフトウェアエンジニアとして国内外の企業に勤務する傍ら、kenkooooというユーザー名でAtCoder等のコンテストに参加している。好きなプログラミング言語はRust。
AtCoder株式会社 高橋 直大
高橋 直大(たかはし なおひろ):1988年生まれ。慶應義塾大学大学院政策メディア研究科修士課程修了。現在、AtCoder株式会社代表取締役社長。Microsoft主催のImagine Cupで世界3位、TopCoder Openで世界2位、2022年にはGoogle Hash Codeで優勝など、複数の世界大会で上位入賞を経験し、15年以上プログラミングコンテストに参加し続けている。