蟻本読もうぜ（＾～＾）？

「　👇　蟻本読もうぜ？」

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

「　読み終わったら教えてくれだぜ」

「　蟻本読まないと ABC の D問題に出てくる DP が分かんないのよ」

「　アルファベットばかりで分けわからん」

蟻本買った( ﾟーﾟ) この本読んでそこら辺の着色コーダーと同じ道具が手に入るなら　あまりに楽な話だが( ﾟーﾟ) pic.twitter.com/v5uMwri5DW

— むずでょ＠きふわらべ第３１回世界コンピュータ将棋選手権一次予選３１位 (@muzudho1) June 14, 2021

「　👆　ソースコードとか　ダウンロードできないものか」

📖　「プログラミングコンテストチャレンジブック第2版」サポートサイト

「　👆　正誤表が載ってるだけかだぜ」

「　動かして試したいんだが、自分で打鍵するしかないのか」

「　それがプログラミング・コンテストよ」

「　アルゴリズムに著作権は無いから　バンバン　ブログに書いてもいいと思うんだが、どんなパンチが飛んでくるか分からないんで　手元でこっそり動かすかだぜ」

📖　コードテスト（C++入門 AtCoder Programming Guide for beginners (APG4b)）

「　👆　コードテストって、練習に勝手に使っていいのかだぜ？」

「　お父んみたいなやつがマジョリティーになって社会問題になったら AtCoder も腰を上げるだろ」

「　蟻本のコードは　G++　だから　APG4b　のサンプルの　GCC　と違うのな。
ちょっと読み替えないといけないな」

Chapter 1

P8

「　よし、ちょっと読み替えて、動くぜ」

「　ちゃんと理解してやってんの？」

「　理解しようとして手が止まってしまうよりは、コードを真似て動かして進もうぜ？」

P21

「　C++の for文って　打鍵量多いから　やっぱ　rep(i, N)　だよな」

「　👇　テンプレート作っとこ」

P

Test1:

// 実行時間とメモリ:
ms KB

Test2:

// 実行時間とメモリ:
ms KB

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// 制約
const int MAX_N = 100;

// 入力
int n, a[MAX_N];

void solve() {
}

int main() {
  // 標準入力より入力
  cin >> n;
  rep(i, n) {
    cin >> a[i];
  }

  solve();
}

P23

「　この蟻本、 POJ からの引用なのだったら、わたしが引用してもいいのでは？」

「　そんな推移律が成り立つのかだぜ？」

📖　北京大学（POJ）

「　👆　大学なのか。
中国で著作権の取り扱いがどうなってんのか分かんね」

    // 抜粋
    minT = max(minT, min(x[i], L-x[i]));

「　👆　最小の時間を計算、と言ってるのに　なんで　min( ) ではなく max( ) なの？」

「　図を描かないと　分かんないよな」

「　👆　例えば　長さ　5　の棒って　こんな感じ」

「　👆　全長が 5 で、蟻が 3 に居れば、
蟻の左側の長さは　3　で、右側は　L - 3　だな」

「　👆　min を取ると　長さが短い方を取るのは　わかるのよ」

「　👆　最小の時間を取るといったら、上図のどっちだぜ？」

「　時間がかかって足が引っ張ってしまう方を取るから　上図の上のバーね」

「　最小の時間を取るという話しをしているのに、なんで　時間がかかる方を取るんだぜ？」

「　全体として最小になる時間を取ろう、と言っているんだぜ」

「　部分としては　max　関数を使って　時間がかかる方を取る場面もあるということだな」

P25

xより小さければ、xはあるなら半分より後ろにある

「　👆　日本語が分けわかんない」

「　日本語はワケ分かんないが、二分探索は知ってるんで　あとで説明するぜ」

二分探索

kの中央の数字

「　👆　って何なの？」

「　👆　例えば、数字の４を折り曲げれると思ってくれだぜ。
このとき、折り目は2だぜ。この2を　中央の数字　と呼んでいる」

「　でも　数列はバラバラよ。例えば 2, 3, 9, 11, 105 とか」

「　👆　そのような数列でもイケる。昇順か、降順に並んでさえいれば」

偶数個の場合

「　👆　って何なの？」

「　👆　数字が偶数個の場合、長さを２で割ると　0.5　余るから切り捨てて、
下の方が短めの、真ん中から 0.5 ずれたところが　折り目になるな」

「　めんどくせ」

「　👆　x というのは探したいものだぜ。
棒の上にあるかもしれないし、ないかもしれない」

xより小さければ、xはあるなら半分より後ろにある

↓
xより　「中央の数字が」　小さければ、xはあるなら　「半分」　より後ろにある

「　👆　うーん、日本語が釈然としないなあ」

「　👆　半分 とか 中央の数字 とか　ワケ分かんないんで、
折り目と、折り目んとこにある数字　と考えろだぜ」

「　ｘは　無いこともあるの？」

「　ｘは、有ったり無かったりする」

「　👆　例えば　ｘが100だったら、上図の棒には　ｘ　は無いぜ」

「　なんということだぜ」

O(log n)

「　log n って何なの？」

「　倍々ゲームの速さだが……」

「　👆　log の右下に小さく　倍々の速度を書くのが本来だぜ。この右下の数字を　底（てい）と呼ぶ。
競技プログラミングでは　底は　２　を使うんで　省略しているそうだぜ」

「　倍々の速度って何だぜ？」

「　👆　緑色の数は　２倍、２倍で増えていっているが、 log2　緑色の数　と書くと、赤色の数　が出てくる表引きだと思ってくれだぜ」

「　log2 って　どうやって筆算すんの？」

「　筆算しない。表引き」

「　👆　指数の逆のことだと感じろだぜ」

「　128を 2 で何回割れるかということかだぜ」

「　そうだぜ」

二分探索の計算量は O(log n)

「　👆　二分探索の動きを絵にしたぜ。同じことを３回してるよな」

「　半分より１個多く　折ってる気がするが……」

「　👆　長さが８のとき、３回折ったら　ｘがあるなら、ｘを見つけてるだろ」

「　その聞きなれない日本語を止めなさい」

「　長さが７のときも試してくれだぜ」

「　境界値チェックか。やったろ」

「　👆　さっきと同じ 3回だぜ」

「　👆　2.8073…　回じゃないのかだぜ！」

「　小数点以下切上げだろ」

「　👆　この茶番は確かに　切り上げ　なのよ。　ｘが折り目にくるまで　３回かかるわ」

ソートにO(n log n)

ソートにO(n log n)時間

「　👆　なんのこっちゃ」

「　👆　ソートというのは　並び替えのことだが……」

「　👆　並び替える必要がないときはすぐ終わるし、最悪のケースでは　たくさん　操作があるぜ」

「　ライブラリなどに実装されている、配列の要素の並び替えの操作にかかる時間のオーダーは　最悪のケースで　O(n log n)　と言われているんだぜ」

「　n log n が何かって聞いてんのよ」

「　👆　ｎ　って要素数だから、１つの要素ごとに　log n　の計算量をさばいているということだぜ。
最悪のケースで」

「　n log n の左側の n の意味としては、要素数が増えれば　それだけ単純な掛け算として　時間がかかりますよ、ということだぜ。
右側の n は　対数時間だな。　対数時間というのは　指数時間の逆のようなものだぜ。さっきやった」

「　もっと時間のかかるソートもあるが、今どきのプログラム言語でソートといえば O(n log n) でしょ、ということだぜ」

ループにO(n^3 log n)

ループにO(n^3 log n)時間

「　👆　なんのこっちゃ」

「　最悪のケースで、全件探索を３回しながら　log n　の計算量の処理をするということだぜ」

「　👆　n=3 が ３個あるのを、例えば上図のように描いてみようぜ？」

「　👆　例えば　住所に例えれば　0県0市　みたいに階層になっていると考えろだぜ」

「　👆　３階層あれば　0県0市0区だな……、あれ？　なんか多くね？」

「　お父んが勝手に　0　から数を振ってるから、n は 3 ではなくて、実際には 4 だな」

「　このように、　１重ループなら　ｎ、　２重ループなら　ｎ×ｎ、　３重ループなら　ｎ×ｎ×ｎ　だぜ」

P26

8ms --> 8ms
408KB --> 336KB

7ms --> 6ms
452KB --> 352KB

「　👆　バイナリーサーチにしたら、微妙に速くなったかな？」

「　件数が小さいうちは　美味さが分からん……」

        // rep(d, n) {
        //   if (k[a] + k[b] + k[c] + k[d] == m) {

        ↓

        // if (binary_search(m - k[a] - k[b] - k[c])) {

「　👆　何でこれが　等しいのか　説明読んでも分かんないんだけど？」

「　絵にして説明しよう」

「　👆　長さが１，３、５　の棒が　いくつでもあるとき、　４本使って　長さ１０　にしたいとしよう」

「　3 × 3 × 3 × 3　で 81 パターンあるぜ」

「　👆　４重ループを使えば　総当たりできるな」

「　👆　例えば　ピッタリ行くパターンはこれだぜ。　他にもあるな」

「　それがなんで　ｍ　から　Ｋa、Ｋb、Ｋc　を引いていく　引き算になるの？」

「　👆　この　Ｋd　のループを、　O(n)　から　O(log n)　に縮めたいんだぜ」

「　長さが 5 の棒と、バイナリーサーチの　何が関係あるんだぜ？」

「　👆　バイナリーサーチするのは　当てはめる棒の方だぜ」

「　３本ぐらい　バイナリーサーチしても　おいしくないんじゃないかだぜ？」

制約
1 <= n <= 50

「　👆　3本が 50本に増えても　まだ大したことないかもしれないが、 1000本に増えると　ダメらしいぜ」

3
10
1 3 5

「　👆　どうやって n=1000 のケース作んの？　大変よ？」

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  cout << "3" << endl;
  cout << "4000" << endl;

  rep(i, 1000) {
    cout << i << " ";
  }
  cout << endl;
}

「　👆　コードテストが目の前にあるんで使おうぜ？　テスト考えるの大変だけど」

「　ほら　イケた」

「　👆　イケてないぜ」

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  /*
  cout << "3" << endl;
  cout << "4000" << endl;

  rep(i, 500) {
    cout << i << " ";
  }
  // */
  // /*
  rep(i, 500) {
    cout << i + 501 << " ";
  }
  // */

  cout << endl;
}

「　👆　２パートに分けろだぜ！」

「　👆　４重ループぐらい簡単にイケるみたいだぜ？」

「　n=3　を　n=1000　に変えないとダメなんじゃないの？」

「　👆　n=1000 ぐらい簡単にイケるみたいだぜ？」

// 制約
const int MAX_N = 50;

// 入力
int n, m, k[MAX_N];

「　👆　あれっ？　配列のサイズをオーバーするエラーになるんじゃないのかだぜ？
これでエラーにならなかった理由は不明。 MAX_N を 1000 にしたろ」

「　よし　エラーになったぜ」

「　じゃあ　バイナリーサーチを使ってみてくれだぜ」

O(n^3 log n)

「　👆　62ms になったぜ」

「　こりゃ　バイナリーサーチ使うわね」

「　ループが３つで O(n^3)、 バイナリーサーチ１つで O(n log n) として、 O(n^3 log n) だな」

「　蟻本の想定しているCPUって何だぜ？　Ryzen Threadripper 12 Core　使ってるから　 O(n^3 log n) の計算　n=1000 で　早く終わってしまったのかだぜ？」

「　いや、お父んが　コピー貼り付けで　MAX_N = 50　に戻したからだぜ」

「　アカンのか……」

O(n^2 log n)

「　👆　O(n^3 log n) の計算ではまだ遅いんで、　O(n^2 log n)　にしようぜ、という話しだぜ」

「　そんなこと　できたらいいな、だが　どうやってだぜ？」

「　👆　Ｋc と Ｋd のパターンを１つにしてしまうんだぜ」

「　そうすりゃ　できそうねぇ」

「　👆　やっと通った、つら」

Chapter 2

「　簡単なページは飛ばしていこうぜ」

P34

「　木構造で　何やってんだぜ？」

「　👆　main 関数で dfs(0, 0)　と書いているな。これを上図で示した」

「　👆　で、 sum が増えない出口と、 sum が増える出口　の計２つの出口があるんだぜ」

「　👆　あとは　葉っぱ　まで　潜って行けだぜ」

「　潜って何をやってるんだぜ？」

「　👆　sum の全パターンを作ったわけだな」

「　13 を探していたのよね～」

「　👆　13 は、 +2、 +4、 +7　で作れるみたいだな」

「　👆　戻るときは　True　か　False　を返してこいだぜ。 True が優先」

「　👆　DFS（Depth-First Search; 深さ優先探索）だから、上図のように潜ったり浮かんだりするんだろうけど」

P35

「　コンピューター囲碁の連（れん）を見つけるアルゴリズムだ」

「　また書かされるのか」

「　これって DFS（Depth-First Search; 深さ優先探索）だったの？」

「　そんな分類なんだな。 お部屋のお掃除 ぐらいにしか思ってなかったぜ」

「　その捉え方だと　ロジックが弱いから　類型問題の連想に結びつかないんじゃないか？」

「　いろいろなお部屋のお掃除 があるもんな」

「　👆　これにも名前が付いているのかだぜ？
横が m サイズ、 楯が n サイズの盤を　全マス　スキャンするんだぜ」

「　お父んは　何と呼んでるんだぜ？」

「　スキャン だぜ」

「　特に呼び名は内容ねぇ。　強いて言えば　２重ループかしら」

「　蟻本のサンプルは　縦方向の２重ループだけど、
漏れなく全マス見るようね。 オーダーは O(N × M)」

「　👆　蟻本では　８方向と言っているが、９マス調べているぜ。
調べ終わったマスは　.（ドット）で塗りつぶしていくから、
それでも　同じマスを何度も調べるような不具合は出ないんだな」

「　👆　あれっ、思ってたのと違う！」

「　問題文をよく読めだぜ」

「　👆　水溜まりの数は　１３個　じゃないのかだぜ！」

「　👆　３１個よ」

「　ぬぎぎぎぎ！」

「　勝手に　水溜まりを　くっつけるなだぜ」

「　ぬぎぎぎぎぎぎ！」

P36

状態を探索します。

「　👆　状態　って何なの？」

「　👆　こいつ（状態;State）だぜ。
探索（Search） という言葉が難しければ、何かを探して状態を訪問していることだと思えだぜ」

「　👆　蟻本の日本語難しくて分からないんで、幅優先探索なら知ってるんで　絵にして分かりやすく説明したろ」

「　他の人は　お父んが分かりやすいように説明されると　分からないんだけどな」

「　👆　ハムスターの４方向を　右側から時計回りに光が回転して、
床のパネルは浮き上がって　筒に入っていくんだぜ」

「　ハムスターって　そんな動物だったかしら？」

「　👆　ハムスターを隣に移動しろだぜ。数字も増えろだぜ」

「　３匹になった」

「　👆　また、ハムスターの隣の床が光れだぜ」

「　👆　キューに入っていたものは捨てて、新しい床を入れろだぜ」

「　👆　あとは　繰り返しだな。
ハムが　移動のターン数を床に書いていってるんで、階段に着いたときには　移動の最小ターン数が分かるな」

「　👆　やっと　コーディングできた。つら」

盤の入力

「　👆　迷路とか　土地とか、こんな感じで入力するが……」

「　👆　読取り方向は　さきに　ｘ　で、　次に　ｙ　だから……」

  rep(j, N) {
    rep(i, M) { // 内側がx軸
      cin >> maze[i][j]; // (x,y)
    }
  }

「　👆　二重ループの内側を　x　にしないといけないぜ」

「　i, j　じゃなくて　x, y　を使っちゃいけないの？」

「　知らね」

「　ループカウンタは　i, j, k...　を使うのが習慣だが」

P39

「　蟻本では　DFS　を　解候補の生成　と捉えてるんだな」

「　何だぜそれ？」

「　👆　例えば　５つの豆球があると思ってくれだぜ」

「　👆　電球は　Off　と　On　の２状態あるとするぜ」

「　👆　すると、On/Off や 並び は、いろんなパターンがあるな。
このパターンが　解候補　だぜ」

「　👆　枝を増やせば、 On/Off　だけじゃなくて、半分点灯　とかも　いけるわね」

「　その枝を　593　まで増やせば　将棋になるぜ」

next_permutation( )

「　next_permutation( ) って何よ」

「　さっぱり分からん。　ソースコード実装して　動かしてみよ」

「　next_permutation() を使わない場合と、使う場合の２種類のソースコードがあるんだけど」

「　動かしてみてくれだぜ」

0 1 2 
0 2 1 
1 0 2 
1 2 0 
2 0 1 
2 1 0 

「　👆　next_permutation() を使わないソースコードで、 3 を入力した結果が　上記だぜ」

「　順列の全パターンを作ってるわねえ」

0 1 2 
0 2 1 
1 0 2 
1 2 0 
2 0 1 
2 1 0 

「　👆　next_permutation() を使ったソースコードで、 3 を入力した結果が　上記だぜ」

「　同じじゃないか」

int perm2[3];
int n = 3;

do {
  // ここでperm2を利用
} while(next_permutation(perm2, perm2 + n))

「　👆　next_permutation( ) の引数に何を渡しているの？」

「　begin と end みたいなもんだと思うけど……」

Program:

// [コードテスト](https://atcoder.jp/contests/APG4b/custom_test)  
// C++(GCC 9.2.1)  
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#include <algorithm>

const int N = 10;

int main() {
  int array[N] = {1, 2, 3, 4, 5, 6, 7, 8 ,9, 10};
  int begin = 3;
  int end = 6;

  do {
    // 表示
    rep(i, N) {
      cout << array[i] << " ";
    }
    cout << endl;

    // arrayの指定区間をスワップする。辞書順で現在より後ろのうち、最小のものへ
  } while (next_permutation(array + begin, array + end));
}

Output:

1 2 3 4 5 6 7 8 9 10 
1 2 3 4 6 5 7 8 9 10 
1 2 3 5 4 6 7 8 9 10 
1 2 3 5 6 4 7 8 9 10 
1 2 3 6 4 5 7 8 9 10 
1 2 3 6 5 4 7 8 9 10 

「　👆　よし、分かったぜ」

「　教えてくれだぜ」

「　👆　まず　中身の入った　配列を用意しておけだぜ」

「　👆　次に　範囲を指定しろだぜ」

「　👆　next_permutation 関数は、この範囲の中の要素を　スワップ（入替え）するんだぜ」

「　勝手にスワップすんの？」

「　規則性がある」

「　４と５と６を使った３桁の数で、４５６より大きい数のうち、一番小さな数だぜ」

「　まわりくどい日本語ｗｗｗｗ」

「　👆　ざっくり言うと、次の数だな。 465」

「　next_permutation( ) （次の順列） ねえ」

「　👆　もう大きくならないなら、何もスワップせず　false　を返すぜ。 whileループでも抜けろだぜ」

Chapter 2-2

P43

int t = min(A / V[i], C[i]); // コインiを使う枚数

「　👆　これは何やってんの？」

「　👆　コインを持っている枚数は決まっているからな。右側は　出せるコインの枚数の最大値だぜ」

「　左側は　残額を　コインの額で割って　小数点切り捨て。
残額が９００円なら、５００円玉を２枚もっていても、ぴったり合わせるには１枚しか使えないな」

「　右側のコインの枚数は、左側で３枚とか出ても、出せませんよ、という意味だぜ」

「　こんな　min　を使ったプログラム　制限時間の中で　とっさに書けないぜ」

P43下

「　👆　この図は……」

「　👆　仕事が２つあるのかだぜ？」

「　また　お父んが　勝手に解釈してら……」

「　👆　線分１本が　仕事１つだぜ」

「　👆　お父んが　勝手に解釈しない図にするなら、こうだな」

「　なるほど……」

「　👆　そして　仕事のスタートとエンドは　被っていることもあるぜ。
この図で選べる仕事は１つだけだな。２つは選べない」

「　なるほどなるほど……」

P45

「　蟻本、証明付いてないんだが」

「　お父んが証明しろだぜ」

「　こりゃ　むずかしいな……。 P43　の問題から証明しようぜ？」

「　👆　一番少ないブロックの数で、点線の枠を埋めろだぜ」

「　👆　こうだぜ」

「　よっしゃ！」

「　👆　じゃあ　これでも　同じようにやってみろだぜ」

「　簡単だぜ。見てろだぜ」

「　👆　こうだぜ！」

「　なんで　さっきより　多くブロックを使ってるんだぜ？」

「　水色のブロックを使ったら、緑色のブロックを使ったときより隙間が小さくなって、もう緑色のブロックが入らなくなったからだな」

「　欲張るから　そうなるのよ」

「　欲張っていいときと、欲張ってはダメなときの違いを教えてくれだぜ」

「　👆　それは、ブロックが小さいもの順に並んでいるときの、隣り合うブロック２つに着目しろだぜ」

「　👆　ぴったり収まるケースと、はみでるケースがあるだろ」

「　あるぜ」

「　水色のブロックが緑色のブロックより大きいのは分かっているとして、
水色のブロック１つは、　緑色のブロック２つでカバーできる面積に　２　足りないわけだが……」

「　👆　この余ってるとこ」

「　👆　緑の左隣の小さなブロック　２つないと　カバーできないだろ」

「　ピッタリだな」

「　この　はみ出たところをカバーするのに、２つかかってしまった、というのが　いけない」

「　１枚でカバーできたって、すぐには　良いとは言えないんじゃない？」

「　👆　ワラちゃん、黒い点線の枠を　一番少ない数のブロックで埋めなさい」

「　簡単だぜ。任せろだぜ」

「　👆　でけたぜ」

「　よっしゃ！」

「　👆　じゃあ　赤色のブロックが品切れのときも　やってくれだぜ」

「　任せろだぜ」

「　👆　これは無理だぜ」

「　欲張るから　いけないのよ」

「　欲張っていいときと、欲張ってはダメなときの違いを教えてくれだぜ」

「　👆　例えば　隣り合うブロックが　１つずつ違う大きさのとき……」

「　👆　どこでもいいんで、連続する３つのブロックを選んでくれだぜ」

「　👆　そして　真ん中のブロックを積み上げて、背の高い方と　比べてみてくれだぜ」

「　👆　その差が　背の低い方のブロック１個分なら　セーフ」

「　それだと　もっと　いろいろなセーフのパターンもいけそうねぇ」

「　そのすべてのセーフのパターンを教えてくれだぜ」

👇📖　硬貨の問題が貪欲法で解けるための条件

「　👆　何言ってんのか分かんないわね」

「　👆　nが5のときは、上図だな」

「　👆　a[j] は一番後ろの手前とのことだぜ」

「　👆　j はどこか適当に選ぶとして、 j+1　って、 j の右隣だよな。
この回りくどい言い方は、どこでも　言いハマる、と言いたいんだぜ」

「　数式の読み方は　一般化され過ぎていて　むずかしい」

「　👆　δ （デルタ）は、a[j]　より左の、いずれかの a だな」

「　その　髪の毛が１本のオバQが　デルタなの？」

「　そうだぜ」

「　いずれかのa　と言われたら、あいまいで　落ち着かないぜ」

「　どこでもいいということは、両端の　最小のa　とか、　最大のa　とかにしろだぜ」

「　数式は　どうとでも当てはまるから、極端なケースを入れてやれだぜ」

「　p は　2/3　だな」

「　👆　ここまでは当てはまるが、次は　どうやるんだぜ？」

「　👆　赤いブロックは十分あるとして、緑色の点線の枠を埋めろだぜ」

「　簡単だぜ。任せろだぜ」

「　👆　でけたぜ」

「　よっしゃ。じゃ、 Ｈ（δ） は　２　な」

「　👆　ダメだったぜ」

「　じゃあ、貪欲法　使うと解けないことがあるんだな」

「　必ず解ける例を　教えてくれだぜ」

「　👆　はみ出たくないんだから、こうだろ」

「　等差数列をやめて、等比数列にしたのね」

「　👆　適当に　j　を取ってみるかだぜ」

「　👆　δ　から選ぶのは　一番大きな　こいつでいいだろ」

「　👆　Ｈ(δ)　は　２　だぜ」

「　👆　p　は　２.5　だな」

「　👆　ダメだったぜ」

「　じゃあ　引用する記事　変えようかな」

「　２倍ぐらいの比では　足りてないんじゃないの？」

「　👆　じゃあ　きふわらべ、これで」

「　👆　適当に　j　を取るぜ」

「　👆　δ　から選ぶのは　こいつだな」

「　👆　Ｈ(δ)　は　３　だぜ」

「　👆　p　は　3+1/3　だな」

「　👆　ダメだったぜ」

「　えっ！　Ｈ（δ）　が伸びてくるのかだぜ！」

「　δの最大を取ってるから　ダメなんじゃないの？」

「　境界値テストをしてるんだぜ」

「　ａは合ってるだろ。ｊも合ってるだろ。ｊ＋１も合ってるだろ。ｐも合ってるだろ。Ｈ（ｘ）も合ってるだろ。
怪しいのは　δ　だぜ」

0 ≦ δ < a[j]

「　👆　この記述から　何を読み取れる？」

「　δは実数なの？」

「　δの取りようなんか　無限にあるのでは？」

「　δは　どこだぜ！」

「　👆　a[j]　を適当に取ろう」

「　👆　ここも　δ　なんじゃないの？」

「　まったく　その通りだぜ」

「　👆　δ　って　ここなんじゃないの？」

「　まさしく　δ　とは　差　という意味だぜ」

「　じゃあ　この場合　δ　は　２　だな。
p　も　2」

「　Ｈ（δ）　はどうすんのかな」

「　👆　緑色のブロック１個を　δ　に埋めれるかな」

「　👆　でけたぜ」

「　つら……」

「　で、　証明って　どうやって　やんの？」

「　👆　δ　のとこにブロック１個埋めておわりなら　左の柱がブロック２個、右の柱がブロック２個なんで　トントンだな」

「　a[j]　側の同じブロックの数から１個引いたものより、
δ側をカバーするブロックの数は　同じか、より少なくあって欲しいようだな」

「　👆　気にしてるのは　２つの柱の　追加分ってことよね」

「　ブロックは小さな順に並んでいるというが、同じサイズのブロックが連続していてもいいのかだぜ？」

「　いいのでは」

「　👆　jより１つ前のブロックではδからはみ出るけど、２つ前のブロックなら埋めれるとき、なんで　いけないの？」

「　いけなくはないぜ。　Ｈ（δ）　は、貪欲法としか指定がないんで」

「　じゃあ　いけるのか」

「　図解で　面積は描けるが、　ブロックの個数であることを強調することは　視覚的な図形で　描けないしな……、
何かいい方法は無いものか」

「　点でいいのでは」

「　👆　指にしてみよ」

「　p は自然数なの？　実数なの？」

「　ｐとδは一意に求まると　記事に説明があったが……」

「　どうやってだぜ？」

📖　別の記事

「　👆　別の記事も参照しようぜ？　右クリック利かないけど」

「　どっちかのサイトが、もう片方のサイトをコピペしてるだろ。新しい発見無いぜ」