こんにちは、AWS事業本部コンサルティング部に所属している今泉(@bun76235104)です。
最近サボっていたのですが、また面白くなって競技プログラミングにハマりつつあります。（以前は以下のようなブログ記事をかいていました）
今は「文系」とか「数学が苦手」とかを意識しすぎていたなと少し反省しています。
数学が苦手なのは事実なのですが、そこと向き合った上で意識変えないと本当に一生苦手になっちゃうなと思い返しました。
ということで、上の記事でも少し触れているのですが、1年ちょっとガッツリ活用できていなかった（手計算の問題を飛ばしたり）していた以下の書籍をもう一度最初から最後までやりきってみたら、色々と感動ポイントがあったので紹介します。
| Key | Value |
|---|---|
| タイトル | 問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 |
| 発行所 | 技術評論者 |
| 著者(敬称略) | 米田優峻(@e869120) |
| 出版社の書籍情報URL | 問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本：書籍案内｜技術評論社 |
どんな本だったのか
本書では、「アルゴリズムと数学の関係とは」ということから始まり、「このアルゴリズムは具体的にこうやって使うんだよ」「数学的な考察には王道があって天才だから閃くというわけではないんだよ」ということを教えてくれます。
書籍の概要ページのサンプルを見てもわかるのですが、カラーで図解がふんだんに使ってあり、アルゴリズムの使い方がとてもわかりやすく書いてあります。
また、例題として書籍に記載されている内容はAtCoder上で実際に問題を解くことができ、「効率的で正しいプログラムが書けているのか」を楽しく確かめることができます！
手計算で理解力を確かめる問題と合計して200問の例題があるので、読み飛ばさずに丁寧に解いていくことで1年前には分からなかったことがわかるようになってきました！（まだ分からない分野がありますが）
書籍の構成
書籍の構成は以下のようになっています。
| 章 | 内容 | 感想や備考 |
|---|---|---|
| 第1章 | アルゴリズムと数学の密接なかかわり | なぜ数学的な知識や考察が必要か教えてくれます。書籍の進め方なども記載されています |
| 第2章 | アルゴリズムのための数学の基本知識 | N進法や剰余などの基礎的な知識から始まり、コンピュータの計算量やかかる時間について教えてくれます |
| 第3章 | 基本的なアルゴリズム | 高速な判定法から始まり再起関数やソートなどにも触れます。この章が2番目に面白かったです |
| 第4章 | 発展的なアルゴリズム | 1年前には難しくてちゃんと読めなかった章です。「1日1節」ではなく「1日1例題」の気持ちで行って正解でした |
| 第5章 | 問題解決のための数学的考察 | ここで「天才だから閃くんでしょ。そんなアプローチ。」という色眼鏡が取れました。一番面白かったです。 |
書籍の中でも「数学が苦手な方は1章->2章->3章->5章->4章という順番で進めるのがおすすめ」ということが書いてあったので、素直にそのように進めました。
感想：競プロの答えを見て「なんでそのアプローチを思いつくのかがわからない」という方に非常におすすめ
特に第5章では、「数学的考察はこんなパターンがあるんですよ」という形式で考察のパターンを言語化してまとめてくれています。
私にとって言語化というのが結構重要でして、「あ！こういうのって○○っていう考え方なのか〜」と認識することで、近しい問題や事象についてグルーピングしやすくなります。
グルーピングしやすくなると、一見未知の問題や事象にぶつかったとしても、「ん？これってアレとアレを組み合わせれば・・・！？」という発想に近づきやすい気がしています。
個人的には「規則性を考える」というテーマで小学生の時にやったような石取りゲームの問題を考える所がとても面白かったです。
例えば以下のような問題となります。
書籍のネタバレとなってしまうため、あまり詳しくは触れませんが「石が1個の時は先手の必勝？」では「2個の時は？」「3個の時は？」と積み上げて考えていくのが、私にはとっても楽しかったです。
頭の良い人がどのようにして答えを導いているのか、などと想像しながら答えに近づいていく感覚がたまりませんでした。
個人的にとっても感動した定理やアルゴリズム
ユークリッドの互除法（最大公約数の本質と高速な計算）
最大公約数とか最小公倍数という言葉は覚えているのですが、「どうやって効率的に求めていくか」ということを学生時代に考えたことがありませんでした。
特に最大公約数は「えいや！このくらいが共通の約数だろう！ちょっとずつ大きくしていこう」みたいに考えていました。
以下の記事でもとてもわかりやすく紹介してくれている、ユークリッドの互除法で効率的に計算することができます（プログラムで1から始まるfor文を書く必要がありません）
- 縦がAcm、横がBcmの長方形を考える
- この時長方形をできるだけ多くの正方形で敷き詰めることを考えると、その正方形の1辺の長さが最大公約数となる
- それを求めるには剰余（あまり）という考え方を使って・・・
とても分かりやすく図解して、ステップを細かく刻んでくれているので理解が捗りました！
エラストテネスのふるい
簡単に言うと（私の理解では）効率的に素数を列挙するアルゴリズムです。
以下の記事で紹介されているような考え方ですね。
書籍と記事の内容がすごく分かりやすいのであえて書くこともないのですが、以下のように考えていくという叡智を目にして「て、てんさいだ！」と部屋で独り言を言っていました。（実話）
- 3という数字があるけど、3に1以外の正の整数をかけたら絶対に素数じゃなくなるね
- だから3以外の3の倍数は全て素数じゃないマークをつけるね
- といった感じです（さらに数をどこまで数え上げるかという点で高速化の余地があります）
最後に
競技プログラミンをやらない人でも、アルゴリズムや数学的な考察力はどの時代でも色褪せない技術だと考えています。
ぜひ、これを気に勉強してみようかな！と思っていただけた方は本書をご検討ください。
以上、最後まで読んでいただきありがとうございました。今泉でした。
257
