こんにちは、大学 1 年生になったばかりの E869120 です。
私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックに出場しています。ちなみに、2021 年 5 月 19 日現在、AtCoder では赤（レッドコーダー）です。

本記事では、アルゴリズムが実生活と結びつくトピックについて紹介したいと思います。

【シリーズ】

1. はじめに

21 世紀となった今、生活の中にはたくさんの問題があふれており、そのうちいくつかは、皆さんも考えたことや悩んだことがあると思います。

しかし、それらすべてが解けない問題というわけではなく、下図に書かれているもののように、「アルゴリズム（計算の手順）の効率化」によって解ける問題もあるのです。

そこで本シリーズでは、このようなトピックを紹介することで、「あの実生活の問題はこうやって解けるのか！！！」という感動を伝えること、そしてアルゴリズムの面白さを伝えることを最大の目標にします。¹

章	タイトル	備考
1.	はじめに
2.	最終回で扱う内容
3.	ケース A｜どんな方法で切っても良い	本記事のメインです
4.	ケース B｜一度完全に切られたピースは二度と切れない	少し難しいです
5.	最終回のまとめ
6.	全 3 回の総まとめ　～アルゴリズムとは何か？～	最も伝えたいことです
7.	アルゴリズムを学ぶ意義
8.	アルゴリズム構築能力を身に付けるためには？
9.	おわりに

2. 最終回で扱う内容

詳しくは 3 章・4 章で述べますが、今回は以下の問題を扱います。

立方体のゼリーを何回か切ることで、同じ大きさの正六角柱形のゼリーを 1000 個作りたい。できるだけ少ない回数で切る方法を考えよ。

この問題を読んで、「プログラミングに関係ないのでは？」と思った方がいるかもしれません。確かにアルゴリズムはコンピュータの文脈で使われることが多いので、疑問に思うのは当然です。

しかし、広い意味では、プログラミングに限らず

何か物事を行うときの「やり方」、つまり「手順」のこと

だと言って良いと思います。

さて、最終回では「アルゴリズムの改善」というものを直感的に理解してほしいと思い、プログラムを書かなくても解けるトピックを取り入れることにしました。

記事の前半では、「ゼリーを切る問題」のいろいろな解法を紹介し、アルゴリズム効率化とはどういうものかを理解してもらうことを目標にします。

後半では全 3 回の総まとめとして、今まで競技プログラミングを 5 年間やってきて感じた「アルゴリズムの面白さと学ぶ意義」について熱く語り、壮大なフィナーレを飾りたいと思います。

3. ケース A｜どんな方法で切っても良い

最初に、同じピースを二度切っても良い場合を考えてみましょう。
厳密に述べると以下の通りです。

立方体のゼリーがある。あなたは包丁を 1 回使うことで、長方形の切れ目を入れることができる。切れ目を奥まで入れないこと（左から 2 番目）、同じピースを複数回切ること（左から 3 番目）、同時に複数のピースを切ること（左から 4 番目）も可能である。

できるだけ少ない包丁の使用回数で、同じ大きさの六角柱ピースを 1000 個作りたい。その方法を求めよ。

これはどうやって解けばいいのでしょうか。5 分くらい考えてみましょう。

3-1. 1005 回で切る方法

まず、以下のような方法が考えられます。

「6 回包丁を使って六角柱のピースを作ること」を 1000 回繰り返す

しかし、6 × 1000 = 6000 回の切断が必要で、あまり効率的ではありません。

そこで、切り方の手順、つまり「ゼリーを切るアルゴリズム」を次のように改善しましょう。

手順1　最初に六角柱のピースを 1 つ作る。
手順2　手順 1 で作られた六角柱を輪切りにすることで、1000 個のピースに分ける。

そのとき、6 + (1000 - 1) = 1005 回の切断しか必要ありません。

このように、手順を少し変えるだけで、切断回数を 6 分の 1 にできるのです。アルゴリズムの威力はすごいですね！！！

3-2. 16 回で切る方法

前節では 1005 回のアルゴリズムを紹介しましたが、「一度に複数のピースを切れる」ことを使えば、さらに回数を減らせます。例えば、

手順1　最初に六角柱のピースを 1 つ作る
手順2　今あるすべての六角柱ピースを横に並べ、横から真っ二つに切断する。
※手順 2 はピース数が 1000 以上になるまで繰り返す。

という方法を使うと、切断回数 16 回が実現できるのです。

ではなぜ 16 回なのでしょうか。手順2の途中経過を考えてみましょう。

何回目の操作か	1st	2nd	3rd	4th	5th	6th	7th	8th	9th	10th
操作前のピース数	1	2	4	8	16	32	64	128	256	512
操作後のピース数	2	4	8	16	32	64	128	256	512	1024

このように、1 回の操作でピース数が倍々になっていくため、たった 10 回で 1000 個以上のピースが作られるのです。3-1. 節で述べた通り、手順1には 6 回の切断を行うので、合計すると 10 + 6 = 16 回になります。²

3-3. 計算量とは何か　～対数 log の速さ～

次に、3-2. 節で述べた方法がどの程度効率的かを見積もりたいと思いますが、そこで重要になってくるのが計算量オーダーという概念です。本節では最初にこれを紹介します。

まず、以下のプログラムを考えてみましょう。

int cnt = 0;
for (int i = 1; i <= N; i++) {
    for (int j = i; j <= N; j++) {
        cnt++;
    }
}

一体計算回数はどの程度なのでしょうか。$N$ に対するループ回数 cnt の値は、

$$
1 + 2 + 3 + \cdots + N = \frac{N(N+1)}{2} = \frac{1}{2} N^2 + \frac{1}{2} N
$$

で表され、$\frac{1}{2}$ などの定数倍を無視すると、「だいたい $N^2$ 回の計算」を行っていることが分かります。したがって、このアルゴリズムの計算量オーダーは、ランダウの $O$ 記法を使って $O(N^2)$ と書き表せます。（詳しく知りたい方はこちらの記事をお読みください）

このように、計算量オーダーには「大ざっぱな計算回数を見積もることができる」というメリットがあります。

さて、本題に戻りましょう。3-2. 節で述べたアルゴリズムにおける操作回数は、作るピースの数 $N$ に対してどのくらいなのでしょうか。

手順2だけを考えたとき、$1$ 回の切断で $2^1 = 2$ 個のピース
手順2だけを考えたとき、$2$ 回の切断で $2^2 = 4$ 個のピース
手順2だけを考えたとき、$3$ 回の切断で $2^3 = 8$ 個のピース
手順2だけを考えたとき、$4$ 回の切断で $2^4 = 16$ 個のピース
$:$
手順2だけを考えたとき、$i$ 回の切断で $2^i$ 個のピース

ができるので、$N$ 個以上のピースを作るために必要な（手順 2 での）最小の切断回数 $x$ は、$2^i \geq N$ となる最小の非負整数 $i$ です。そこで、対数の定義

$$
2^p = q \ (\Leftrightarrow) \ p = \log_{2} q
$$

より、$x = \lceil \log_{2} N \rceil$ だと分かります³。手順1と合わせると、操作回数は $f(N) = \lceil \log_{2} N \rceil + 6$ であり、これを計算量オーダーで表すと $O(\log N)$ となります。

さて、$O(\log N)$ はどの程度高速なのでしょうか。$O(N^2), O(2^N)$ などと比較してみましょう。（$10 \ 000 \ 000 \ 000 = 10^{10}$ 回以上のものは ERROR となっています）

N	$O(\log N)$	$O(N)$	$O(N^2)$	$O(2^N)$
10	4 回程度	10 回程度	100 回程度	1 024 回程度
20	5 回程度	20 回程度	400 回程度	1 048 576 回程度
100	7 回程度	100 回程度	10 000 回程度	ERROR
1 000	10 回程度	1 000 回程度	1 000 000 回程度	ERROR
10 000	14 回程度	10 000 回程度	100 000 000 回程度	ERROR
100 000	17 回程度	100 000 回程度	ERROR	ERROR
$10^9$	30 回程度	1 000 000 000 回程度	ERROR	ERROR
$10^{18}$	60 回程度	ERROR	ERROR	ERROR
$10^{100}$	333 回程度	ERROR	ERROR	ERROR

たとえピースの数が $10^{9}$ 個でも、30～40 回程度しか切断を行わないのが分かると思います。恐ろしいほど効率的ですね。

これはプログラミングでも同じことがいえます。一般的な家庭用コンピュータの計算速度は $1$ 秒間に $10^{8} \sim 10^{9}$ 回程度なので、例えば $N = 10^{18}$ では次のような状態になります。

$O(2^N)$：「うわああああああああああああああ」
$O(N^2)$：「うわああああああああああああああ」
$O(N)$：「うわああああああああああああああ」
$O(\log N)$：「余裕。コンピュータどころか手でも計算できるくらいの回数さ。」

分かりましたでしょうか。たとえ $N = 10^{100}$ であっても唯一倒れず、しかも数百回程度の計算しか必要ない。これが $\log$ の強さなのです。

3-4. ＜参考＞計算量が log となる例　～二分探索法～

本章の最後に、計算量に慣れていただくため、計算量に $\log$ が付くアルゴリズムの一例である二分探索法を紹介します。以下の問題を考えてみましょう。

Qiita 君は $1 \sim 16$ のうちどれか 1 つの整数を思い浮かべている。
あなたは「思い浮かべた整数は $X$ 以上ですか？」という形式の質問をすることができる。$4$ 回以内の質問で Qiita 君が思い浮かべた整数を当てよ。

まず、次のように聞いていくと $16$ 回の質問が必要です。

思い浮かべている数は 1 以上ですか？
思い浮かべている数は 2 以上ですか？（ここで初めて No が出たら答えは 1）
思い浮かべている数は 3 以上ですか？（ここで初めて No が出たら答えは 2）
　$:$
思い浮かべている数は 16 以上ですか？（ここで初めて No が出たら答えは 15）
※全部 Yes だったら答えは 16

しかし、次のフローチャートの通りに「真ん中を聞く質問」をすると、$1$ 回の質問で「あり得る答えの候補」が半分になるので、たった $4$ 回で答えが分かるのです。（このように、探索範囲を半分に絞っていくアルゴリズムを「二分探索」といいます）

より分かりやすく説明するため、具体例を 1 つ挙げましょう。もし答えが 11 だった場合、

最初、答えの範囲は 1～16（16 通り）
1 回目：「(1 + 16 + 1) / 2 = 9 以上ですか？⁴」という質問をする
- Yes なので答えの範囲が 9～16（8 通り）に絞られる
2 回目：「(9 + 16 + 1) / 2 = 13 以上ですか？⁴」という質問をする
- No なので答えの範囲が 9～12（4 通り）に絞られる
3 回目：「(9 + 12 + 1) / 2 = 11 以上ですか？⁴」という質問をする
- Yes なので答えの範囲が 11～12（2 通り）に絞られる
4 回目：「(11 + 12 + 1) / 2 = 12 以上ですか？⁴」という質問をする
- No なので答えが 11 と分かる

といった感じのステップで正解を出すことができます。

最後に、このアルゴリズムの計算量はどれくらいなのでしょうか。実は、

Qiita 君が $1$ 以上 $N (=2^x)$ 以下の整数を思い浮かべている場合

に一般化したとき、質問回数は $x = \log_{2} N$ 回となるため、$N$ に対するオーダーは $O(\log N)$ と表すことができます。

$N = 10^9$ でも $30$ 回程度しか質問しないことを考えると、恐ろしい効率ですね！！！

このように、アルゴリズムを少し変えることで、一気に切断回数や計算回数を少なくすることができます。特に、計算量オーダーが $O(\log N)$ になるまでアルゴリズムを改善できると、驚くほど高速に動作するのです。

4 章では、もう 1 つ別の問題設定を紹介し、アルゴリズムの改善によって切断回数を減らしてみたいと思います。

4. ケース B｜一度切られたものは二度切れない

次に、「一度完全に切られたピースは二度と切ることができない」場合を考えてみましょう。
厳密に述べると以下の通りです。

立方体のゼリーがあり、角のうち 1 つにさくらんぼが入っている。あなたは包丁を 1 回使うことで、表面に長方形の切れ目を入れることができるが、さくらんぼと完全に切り離された（全く繋がっていない）ピースに切れ目を入れることはできない。

できるだけ少ない包丁の使用回数で、同じ大きさの六角柱ピースを 1000 個作りたい。その方法を求めよ。

残念ながら、複数の「完全に分かれたピース」を同時に切ることができないため、3 章で扱った問題のように $O(\log N)$ 回を実現することはできません。

ですが、まだ諦めるのは早いです。
どうすれば回数を削減できるのでしょうか。5 分くらい考えてみましょう。

4-1. 512 回で切る方法

まず、以下の方法が考えられます。（3-1. 節とほぼ同じです。）

手順1　最初に上から六角形の切れ目を入れる（一番下まで切らないように注意する）
手順2　「底面と平行な面」で上から順に切り、1 個ずつ六角柱ピースを増やす。

しかし、6 + 1000 = 1006 回の切断が必要で、あまり効率的ではありません。

そこで、切り方の手順、つまり「ゼリーを切るアルゴリズム」を次のように改善しましょう。

手順1　最初に上から六角形の切れ目を 2 個作る
手順2　「底面と平行な面」で上から順に切り、1 個ずつ六角柱ピースを増やす。

そのとき、手順2では 1 回の切断で新たな六角柱ピースが 2 個生まれるので、

手順1：$6 \times 2 = 12$ 回
手順2：$\lceil 1000 \div 2 \rceil = 500$ 回

となり、合計操作回数は 12 + 500 = 512 回まで減ります。

4-2. 160 回で切る方法

前節では六角形の切れ目を 2 個作りましたが、果たして本当にそれが最適なのでしょうか。

手順1　最初に上から六角形の切れ目を $B$ 個作る
手順2　「底面と平行な面」で上から順に切り、1 個ずつ六角柱ピースを増やす。
（手順 1 の操作回数は $6 \times B$ 回、手順 2 の操作回数は $\lceil 1000 \div B \rceil$ 回）

といったアルゴリズムにおける操作回数を、いろいろな $B$ について調べてみましょう。結果は次表の通りになります。

$B$ の値	手順 1 の回数	手順 2 の回数	合計回数	メモ
1	6×1=6	1000÷1=1000	1006	手順 2 の操作回数が多い
2	6×2=12	1000÷2=500	512
4	6×4=24	1000÷4=250	274
8	6×8=48	1000÷8=125	173
10	6×10=60	1000÷10=100	160	最適！
20	6×20=120	1000÷20=50	170
40	6×40=240	1000÷40=25	265
100	6×100=600	1000÷100=10	610	手順 1 の操作回数が多い

B=10 を選んだ場合、なんと 160 回の切断で 1000 個の六角柱ゼリーを作ることができました。1 回当たり平均 6 個以上のゼリーを生み出しているので、かなり効率が良いと言えます。⁵

4-3. 94 回で切る方法

前節では 160 回のアルゴリズムを紹介しましたが、手順 1 での六角形の切り方を工夫するとさらに効率化できます。例えば、$B$ 個の六角形を作る際に

ステップ 1　最初に横方向（0 度方向とする）の切れ目を 2 個入れる
ステップ 2　次に 60 度方向の切れ目を適切に $B+1$ 個入れる
ステップ 3　次に 120 度方向の切れ目を適切に $B+1$ 個入れる

といったアルゴリズムを使うことを考えましょう。そうすると、4-2. 節では $6B$ 回切断していたところを $2B+4$ 回に減らすことができます。

このアルゴリズムにおける手順 1・手順 2 合わせた切断回数を関数 $f(B)$ で表すと、

$$
f(B) = (2B + 4) + \lceil 1000 \div B \rceil
$$

となり、関数のグラフは下図のようになります。B=20 のとき僅か 94 回の切断で 1000 個の六角柱ゼリーを作れることが分かります。⁶

4-4. 45 回で切る方法

最後に、現在私が知っている最も効率の良い解法を紹介して終わりたいと思います。

まず、下図の通りに切れ目を入れましょう。そうすると、32 回の切断で 78 個の六角形を作ることができます。（切断の際に、一番下まで切らないように注意しなければなりません）

次に、底面に平行な面で 13 回切ると、六角柱が 78 × 13 = 1014 個作れます。合計の操作回数は 32 + 13 = 45 回であり、1 回の操作で平均 20 個以上の六角柱を生み出すことができる、非常に効率の良いアルゴリズムとなっているのです！！！！！

なお、作るべき六角柱ゼリーの個数 $N$ に対する切断回数を計算量オーダーの形で表すと、$O(N^{1/3})$ となります。証明は読者への課題としますが、たとえ $N = 10^{9}$ でも数千回程度の切断しか必要ないことを意味するため、恐ろしい効率ですね。

5. 最終回のまとめ

今回は、ゼリーを何回か切ることで正六角柱形のピースを 1000 個作る問題を扱いました。

3-1. 節で紹介した最も単純なアルゴリズムでは 6000 回の切断が必要であり、もしこれを実際にやってみると大変な時間がかかってしまいます。しかし、

最初に六角柱を 1 個作り、それを使うことで 1005 回（3-1. 節）
六角柱を同時に切り、個数を倍々にすることで 16 回（3-2. 節）

まで劇的に減らすことができました。

また、複数のピースを同時に切断できない難しい場合でも、アルゴリズムの工夫によってたった 45 回の操作で目的を達成することができました。

このように、プログラミングの問題に限らず、コンピュータを使わないで解ける比較的身近な問題でも、アルゴリズムの効率化が重要になることもあるのです。

6. 全 3 回の総括　～アルゴリズムとは何か～

ここまで色々な問題を扱ってきましたが、結局アルゴリズムとは一体どのようなものなのでしょうか。端的に書くと、

問題を解くための手順や計算方法

のことを指します。また、アルゴリズムには優劣があり、答えを出すまでにかかる時間が短いものが良いとされる場合が多いです。

アルゴリズム効率化のすごいところ

アルゴリズム効率化の素晴らしい点として、

一気に 1 万倍、1 億倍、あるいはそれ以上の計算回数が削減できる

という点が挙げられます。例えば $N = 10^{9}$ の場合を考えると、

$O(N)$ のアルゴリズムでは、計算回数 1 000 000 000 回程度
$O(\log N)$ のアルゴリズムでは、計算回数 30 回程度

と、2 つの間に 3000 万倍以上の開きがあります。これは、コンピュータ自体の計算速度だけでは到底巻き返せるものではありません⁷。良いアルゴリズムには、これほどの威力があるのです。

どんなアルゴリズムがあるのか？

さて、私はここまで 3 回の記事で、以下の問題を扱いました。

コンビニでの 500 円以内の買い物で、最大何 kcal 得られるか（第 1 回）
ソーシャルディスタンスと座席数を両立させる問題（第 2 回）
六角形ゼリーを 1000 個作る問題（第 3 回）

しかし、たった 3 個の問題でも、下図の通り様々なアルゴリズム・設計技法が使われていたり、関連したりするのが分かると思います。

画像に載っているもの以外でも、幅優先探索・ユークリッドの互除法・勾配降下法などのアルゴリズムが有名です。

7. アルゴリズムを学ぶ意義

では、このような「アルゴリズム」はなぜ学ぶべきなのでしょうか。主に 4 つのポイントに分けて記したいと思います。

7-1. 実社会の様々な問題が解けるようになる！

21 世紀となった今、実社会には様々な問題があふれています。例えば、

どのような方法をとれば、素早く辞書から単語を探せるか？
どのような経路を選べば、家から学校まで最短距離で行けるか？
何を販売すれば、スーパーマーケットの利益が最大になるか？
経済と両立しながら、新型コロナウイルスをどう食い止めるか？

など、すぐには分からない難問も多いです。

しかし 6 章で述べた通り、アルゴリズムの効率化によって、実行速度が 1 万倍・1 億倍以上のオーダーで変わることもあります。そのパワーを生かすと、世の中にある様々な問題を解ける場合もあるのです。

情報化社会が進む今、こういう問題を解決できる「高度アルゴリズム人材」が求められています。したがって、将来プログラミング関連の職業に就きたいのであれば、アルゴリズムを学ぶことは必要不可欠だと私は考えます。

7-2. 論理的思考力が身につく！

もう一つの意義として、「論理的思考力が身につく」という点が挙げられます。

アルゴリズムを勉強していくと、「複雑なものをシンプルに整理する能力」が自然に得られるため、前節で述べたように実社会の問題が解けるだけでなく、

プログラムを書く速度が上がる⁸
物事の原因を突き止める力が身につく
仕事での生産性が高まる

などのメリットがあります！！！

7-3. コンピュータが速くなっても一生役立つ！

近年、スーパーコンピュータ「富岳」などの登場により、コンピュータの計算処理速度が急速に向上しています。しかしそれでも、アルゴリズムが役立たなくなることは絶対にあり得ません。

まず、一個例を挙げましょう。たとえば入力サイズが $N = 100$ の問題があって、

計算速度が $10^{16}$ 回／秒の富岳に、計算回数 $2^N$ 回のアルゴリズム
計算速度が $10^{8}$ 回／秒の家庭用コンピュータに、計算回数 $N^3$ 回のアルゴリズム

を実行させたとします。そのとき、答えを出すためにかかる時間は次の通りであり、なんと富岳の方が圧倒的に遅くなっています。

前者は $2^{100} \div 10^{16} \fallingdotseq 1.27 \times 10^{14}$ 秒（約 400 万年）
後者は $100^3 \div 10^{8} = 0.01$ 秒

このように、アルゴリズムを効率化すると 1 億倍以上のオーダーで計算時間が改善されることもあるため、決してコンピュータの性能がすべてではないのです。

このような理由で、アルゴリズムは一生役立つスキルだと私は考えています。

7-4. いろいろな難問を解けるようになって楽しい！

最後に、アルゴリズムの習得によって「解ける問題の幅」が広がると、一見難しそうな問題が解けたり、実生活の中でふと悩んでいた問題の解決策が分かったりすることも多くなります。そんなときは、

アルゴリズム効率化でこんな問題も解けるのか、すごい！！！！！！

と感動することでしょう。実際、私もその感動がきっかけで、競技プログラミングに熱中するようになりました。¹

このような面白さを味わうために、アルゴリズムを学んでみるのも良いと思います。

8. アルゴリズム構築能力を身に付けるためには？

さて、「今日からアルゴリズムを本格的に学びたい！」と思った方は、どうやって勉強を進めればよいのでしょうか。8 章ではこの方法をいくつか紹介して、本記事を締めたいと思います。

8-1. 参考資料を活用する！

まず、アルゴリズムを習得するにあたって、例えば以下の書籍が参考になると思います。

アルゴリズム図鑑絵で見てわかる26のアルゴリズム
- アルゴリズムを図解した、初心者向けの分かりやすい書籍です
- 全部で 200 ページ程度であり、比較的読みやすいと思います
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- AIZU ONLINE JUDGE (AOJ) 管理者の渡部有隆教授により執筆されました
- 私がアルゴリズムを学ぶために最初に手に取った書籍です
- アルゴリズムの実装にも重点を置いており、サンプルコードも掲載されています
問題解決力を鍛える！アルゴリズムとデータ構造
- Qiita アルゴリズムタグ内 1 位の @drken さんにより執筆されました
- 国内ではアルゴリズムの教科書としても使用されている、非常に人気の高い書籍です
アルゴリズムイントロダクション
- 世界的に有名なアルゴリズムの教科書です
- 前の 3 冊とは異なり、正当性の証明に重点が置かれています

また、近年はインターネット上にも、無料で読める有用な記事が増えてきています。例えば以下のものが参考になると思います。

8-2. 競技プログラミングでアルゴリズムに慣れる！

しかし、問題解決力を高めるためには、アルゴリズムの知識を得るだけではなく、「アルゴリズムに慣れていくこと」も同じくらい重要だと考えています。

そこで、競技プログラミングに挑戦してみることで、アルゴリズムを使ったいろいろな問題を解くことをお勧めします。特に、日本最大のコンテストサイトである AtCoder は登録もしやすく、入門者向けのコンテンツも集まっているので、是非やってみましょう。

また、AtCoder を使ってアルゴリズム構築能力を向上させるにあたって、

などの記事が参考になると思います。

9. おわりに

以上をもちまして、「実生活に学ぶアルゴリズム」の連載、そして私が今年 Qiita に投稿する記事は終わりです。次の投稿は 2022 年 2 月頃を予定しています。

振り返ってみると、私はこれまで 20 個以上の記事を Qiita に投稿してきましたが、たくさんの方々に読んでいただいたことで、アルゴリズムと競技プログラミングの面白さを伝えることが出来てとても嬉しいです。読者の皆さん、本当にありがとうございました。

最後に、今後少しでも多くの方々がアルゴリズムの世界に関心を持ち、楽しさや奥深さを感じることを願って、筆を置きたいと思います。

アルゴリズム最高！！！！！！！！！！

筆者自身も、Google Map のナビゲーションと最短経路問題が繋がったときは感動し、アルゴリズムを本格的に勉強する 1 つのきっかけとなりました。これは今でも鮮明に覚えています。 ↩
実は 15 回で切る方法も存在します。考えてみましょう。（読者への課題とします） ↩
$\lceil x \rceil$ という記号についてはこちらをお読みいただければと思います。 ↩
「答えの候補の範囲の真ん中」を質問し続けることで、答えの候補が必ず半分になる、というイメージを持つと分かりやすいでしょう。 ↩
似たようなアルゴリズムとして「平方分割」が挙げられます。 ↩
六角柱ゼリーの個数 $N$ に対する切断回数を計算量オーダーの形で表すと、$O(\sqrt{N})$ となります。 ↩
「コンピュータの性能は 2 年で 2 倍になる」というムーアの法則を前提にすると、コンピュータの処理速度だけで 3000 万倍の差を巻き返せるのは $2 \times \log_2 {(3 \times 10^7)} \fallingdotseq 49.7$ 年後と、恐ろしいほど後の未来になってしまいます。 ↩
プログラミングコンテストの最上位であるレッドコーダーは、論理的思考力が非常に高く、例えば 50 行のバグ無しのコードを僅か 5 分で書くこともあります。 ↩

実生活に学ぶアルゴリズム【最終回：1000 個の六角形ゼリーをたった 45 回の切断で作る方法、そしてアルゴリズムを学ぶ意義】

1. はじめに

目次

2. 最終回で扱う内容

3. ケース A｜どんな方法で切っても良い

3-1. 1005 回で切る方法

3-2. 16 回で切る方法

3-3. 計算量とは何か　～対数 log の速さ～

3-4. ＜参考＞計算量が log となる例　～二分探索法～

4. ケース B｜一度切られたものは二度切れない

4-1. 512 回で切る方法

4-2. 160 回で切る方法

4-3. 94 回で切る方法

4-4. 45 回で切る方法

5. 最終回のまとめ

6. 全 3 回の総括　～アルゴリズムとは何か～

アルゴリズム効率化のすごいところ

どんなアルゴリズムがあるのか？

7. アルゴリズムを学ぶ意義

7-1. 実社会の様々な問題が解けるようになる！

7-2. 論理的思考力が身につく！

7-3. コンピュータが速くなっても一生役立つ！

7-4. いろいろな難問を解けるようになって楽しい！

8. アルゴリズム構築能力を身に付けるためには？

8-1. 参考資料を活用する！

8-2. 競技プログラミングでアルゴリズムに慣れる！

9. おわりに

実生活に学ぶアルゴリズム【最終回：1000 個の六角形ゼリーをたった 45 回の切断で作る方法、そしてアルゴリズムを学ぶ意義】

1. はじめに

目次

2. 最終回で扱う内容

3. ケース A｜どんな方法で切っても良い

3-1. 1005 回で切る方法

3-2. 16 回で切る方法

3-3. 計算量とは何か ～対数 log の速さ～

3-4. ＜参考＞計算量が log となる例 ～二分探索法～

4. ケース B｜一度切られたものは二度切れない

4-1. 512 回で切る方法

4-2. 160 回で切る方法

4-3. 94 回で切る方法

4-4. 45 回で切る方法

5. 最終回のまとめ

6. 全 3 回の総括 ～アルゴリズムとは何か～

アルゴリズム効率化のすごいところ

どんなアルゴリズムがあるのか？

7. アルゴリズムを学ぶ意義

7-1. 実社会の様々な問題が解けるようになる！

7-2. 論理的思考力が身につく！

7-3. コンピュータが速くなっても一生役立つ！

7-4. いろいろな難問を解けるようになって楽しい！

8. アルゴリズム構築能力を身に付けるためには？

8-1. 参考資料を活用する！

8-2. 競技プログラミングでアルゴリズムに慣れる！

9. おわりに

3-3. 計算量とは何か　～対数 log の速さ～

3-4. ＜参考＞計算量が log となる例　～二分探索法～

6. 全 3 回の総括　～アルゴリズムとは何か～