『アルゴリズムデザイン』2章演習問題

証明は参考になるものを書くのは大変なので全体的に略。いずれやるかも。

代入すればよい

やるだけ

f2 < f4 < f6 < f1 < f4 < f5

g3 < g4 < g1 < g5 < g2 < g7 < g6

(a)(c)は正しいと思うけど証明が分からない。

(b)はf(n)=2n, g(n)=nが反例。

(a) O(n^3)

(b) Ω(n^3)

(c)

O(n^2)で解ける。

前計算O(n)で累積和を計算すればよい。

二重ループの中がO(1)になるので、全体としてO(n^2)になる。

行数をkとすると、歌った時に1行目はk回、2行目はk-1回、...、k行目は1回歌われ、合計でk(k-1)/2行分歌われる。

よってn単語からなる歌の行数のオーダーはO(√n)。

解答は(b)でk=2とすればいいので略。

DPで解けるが、意外と奥深い。

特にGoogle卵問題の場合、

$ dp[i][j] := あと卵がi個あって、j階まで試す時に必要な最低試行回数

というdpを立てたくなる気もするけどこれは罠で、遷移を考えると区間DPになるし、時間計算量も空間計算量も悪い。

そこでdpのkeyとvalueを入れ替えて、

$ dp[i][j] := あと卵がi個あって、j回上手く落とした時、何階まで求めることができるか

を検討する。アルゴリズムデザインのストーリーだとそもそもこの方が自然ではある。

dpの遷移を考える。卵を落とす時にどういう戦略を取るといいか考えると、「卵がi-1個あってj-1回落とした時に試せる最高階の、1階上」を試すのが最善であることが分かる。もし割れたら「卵がi-1個あってj-1回落とした時」の戦略を取ればいいし、もし割れなかったら今落とした階を0階として上の階について「卵がi個あってj-1回落とした時」の戦略を取る。つまり遷移は

$ dp[i][j] = 1 + dp[i-1][j-1] + dp[i][j-1]

になる。初期値としてi=1とj=1は自明なのでこれで求まる。

code: 8b_1.cpp

using namespace std;

int main() {

int K, N; cin >> K >> N;

vector dp(K, vector(N, 0));

// 1個の卵をj回落とすと明らかにj階まで試せる

// i個の卵を1回落として試せるのは明らかに1階分

for (int i = 1; i < K; i++) for (int j = 1; j < N; j++) {

}

for (int j = 0; j < N; j++)

return 0;

}

K=2, N=100で14回、K=3, N=100で9回と出力される。復元したいなら普通に後ろからできる。

ところでこのアルゴリズムの計算量は、K*NのDPテーブルをそれぞれO(1)で埋めているのでO(KN)になる。

このコードのように横に見ていくと少なくとも(K-1)*N回更新が必要だが、縦に（つまり外側のループを階数、内側のループを卵の数として）更新していけばより高速になる。

例えばK=3, N=100の場合、dpテーブルの更新回数は横に見ると209回だが縦に観れば27回になる。

code: 8b_2.cpp

using namespace std;

int main() {

int K, N; cin >> K >> N;

vector dp(K, 1);

for (int j = 1; j < N; j++) {

vector ndp(K, 0);

for (int i = 1; i < K; i++) {

}

swap(dp, ndp);

cout << j + 1 << endl;

break;

}

}

return 0;

}

dp配列の次元も削減しておく。

これならK=10,000,000, N=10,000,000とかでも1秒くらいで求まる（24回卵を落とせば求まるらしい）

このアルゴリズムのタイトな上界はよく分からない。O(N * K^(1/K))とかになっていてほしい。

これが上手くn乗やk乗の式に閉じれば二分探索＆ダブリングまで高速化したり計算量証明も簡単になったりして嬉しいけど、ダメらしい。

But, it is well known that there is no closed form (that is, direct formula) for the partial sum of binomial coefficients