https://codility.com/programmers/lessons/12
これは難しい問題ですから、順番にやりましょう。
まず、O(M*N*log(M))の解答、次にO((N+M)*log(M))の解答、最後にO(M+N)の解答を見ましょう。
(1) 一番簡単なO(M*N*log(M))の解答
問題はO((N+M)*log(M))の計算量と言ってますね。てことはバイナリ・サーチを使うのは、Mにたいしてでこれは、釘の方をバイナリ・サーチして解答を出しなさいということです。
それを凄く単純にすると、まずバイナリ・サーチで釘の本数を決めて、その本数で全ての板が打ち付けられるかを確かめてみるということです。
もの凄く簡単にとりあえずこの方針を実装すると、Correctnessに100%のスコアはもらえてもパフォーマンスのスコアは０%になってしまいました。
これは有る意味当然です。O((N+M)*log(M))の解答ではないですからね。
（多分、このコードは O(N*M*log(M))のワーストケース計算量だと思います）
#include <alloca.h>
#include <memory.h>
int check(int k, int* nailed, int* A, int* B, int N, int* C, int M)
{
int i;
for (i = 0; i < k; i++){
int j;
for (j = 0; j < N; j++){
if (A[j] <= C[i] && C[i] <= B[j]){
nailed[j] = 1;
}
}
}
for (i = 0; i < N; i++){
if (nailed[i] == 0){
return 0;
}
}
return 1;
}
int solution(int A[], int B[], int N, int C[], int M)
{
int nailed_size = sizeof(int) * N;
int* nailed = (int*)alloca(nailed_size);
int beg = 1;
int end = M;
int min = M + 1;
while(beg <= end){
int mid = (beg + end) / 2;
memset(nailed, 0x00, nailed_size);
if (check(mid, nailed, A, B, N, C, M)){
end = mid - 1;
min = mid;
}
else {
beg = mid + 1;
}
}
return min == M + 1 ? -1 : min;
}
(2) The O((M+N) * log(M)) solution
で、パフォーマンスに難点があり、そこはcheck関数でやっている、全ての板に釘が打たれているかチェックする部分だとわかったので、そこを解決しなければなりません。
ここで、以前のレッスン(Lesson 3)でやった、prefix sumの考え方を導入しましょう。先頭からそこまでに見つかった釘の本数のprefix sumを取っておけば、ある範囲(i, j)に釘があるかどうかは、prefix_sum[j] != prefix_sum[i - 1]が成り立つかどうかでわかりますよね。もし両者が同じなら、その間に釘は一本もなかったということになります。
次のコードでは、まずprefix_sumの配列を０クリアし、そこで今回チェックする本数分の釘を打って行きます。ここで忘れてはいけないは、同じ位置に２本以上の釘が打たれることがあるということです。ですから、その位置に１を代入するのではなく、その位置に１を 足します。そして、つぎに配列prefix_sumを先頭からスキャンし、prefix sumを計算して行きます。
今度は、各々の板がそれぞれ釘で打たれているかのチェックが必要ですね。これは前述のように簡単に計算できますね。範囲(A[i], B[i])の間に釘があるかどうかは、prefix_sum[B[i]] == prefix_sum[A[i] - 1]で調べられます。
計算量はどうでしょうか？
プリフィックス・サムを計算する部分は、まず、ワーストケースで最大M回釘をうつので、最悪はO(M)ですね。その後先頭から配列をスキャンするのですが、この範囲が問題では(1,2*M)なので、O(2*M)=O(M)ですね.ですから、プリフィックス・サムを計算する部分はO(M)と考えて良さそうです。
次に、板に釘が打たれているかチェックするのは、N枚の板を全て調べますから、O(N)になります。
上記二つを足すと、バイナリ・サーチのループの中身の部分は O(M + N)になりますね。これをバイナリ・サーチで繰り返し、繰り返し回数が最悪log(M)になりますので、全体としての計算量は O((M + N) * log(M))となり、問題の求める計算量になりました。
実際に下記のコードのように実装すると、１００％のスコアがもらえました。
#include <alloca.h>
#include <memory.h>
int solution(int A[], int B[], int N, int C[], int M)
{
int prefix_sum_size = sizeof(int) * (2 * M + 1);
int* prefix_sum = (int*)alloca(prefix_sum_size);
int beg = 1;
int end = M;
int answer = -1;
while (beg <= end){
int mid = (beg + end) / 2;
memset(prefix_sum, 0x00, prefix_sum_size);
int i = 0;
for (i = 0; i < mid; i++){
prefix_sum[C[i]]++;
}
for (i = 1; i <= 2 * M; i++){
prefix_sum[i] += prefix_sum[i - 1];
}
int failed = 0;
for (i = 0; i < N; i++){
if (prefix_sum[B[i]] == prefix_sum[A[i] - 1]){
failed = 1;
}
}
if (failed){
beg = mid + 1;
}
else {
end = mid - 1;
answer = mid;
}
}
return answer;
}
(3) O(M+N)の解答
ということで、１００％はもらえたのですが、よりよい解答があるかどうかググるのが良い習慣ということで、検索すると、実際にO(M+N)の解答が出てきました。
ここにありました。
http://blog.csdn.net/caopengcs/article/details/41834173
中国人の方なので、説明が中国語で全く分かりませんが、コードを読んで自分が理解したことを下記に説明して行きます。
また、コードはこの理解にしたがって、わかりやすく変数名などを書き直し、さらにコメントを追加しました。
また、普段はCで答えていましたが（Codilityのパフォーマンスの測定の点がpythonなどにくらべて辛いので、不十分な解答で通ってしまうことがないとの印象からです）、両端キュー(double-ended queue, deque)を使うので、ライブラリで既に用意されているC++でプログラムを今回は書いています。（最初からC++で書けばスタックとか実装しないで良かったんですけどね…）
下のコードは、１００％のスコアをもらえます。O(M+N)になり、上のO((M + N) * log(M))の解答より格段に早いので当然といえば当然ですが。
#include <deque>
using namespace std;
int solution(vector<int> &A, vector<int> &B, vector<int> &C)
{
int max_pos = C.size() * 2;
//this vector holds -1 at nail_at[i] if there is no nail at the position i
//and k (the number of the nail) if there is.
vector<int> nail_at;
nail_at.resize(max_pos + 1, -1);
//as two or more nails can be at the same position,
//we scan C from tail to head so that we can retain the nail with
//the smallest index at each position.
for (int i = (int)C.size() - 1; i >= 0; --i){
nail_at[C[i]] = i;
}
//this vector holds -1 at plank_end_at[i]
//if there is no plank ends at the position i,
//and the beginning position of each plank, if there is.
vector<int> plank_end_at;
plank_end_at.resize(max_pos + 1, -1);
for (unsigned int i = 0; i < B.size(); i++){
//if there is any two or more planks that end at the same position,
//we only have to consider the smallest one.
plank_end_at[B[i]] = max(plank_end_at[B[i]], A[i]);
}
//a fifo queue to store the nail information.
deque<int> nail_pos_deque;
//we have checked all the nails until this position
//if it should be used or not.
int checked_until_here = 0;
int nail_scan_pos = 0;
//the minimum number of nails
int min_nails = -1;
for (int i = 1; i <= max_pos; i++){
//there is no plank end at there, just continue scanning.
if (plank_end_at[i] == -1){
continue;
}
//there is a plank, but its begining position has been already checked.
//This means that there is al least one plank successfully nailed and
//this plank can be also nailed together when the plank(s) was nailed.
//so we can simply neglect this plank.
if (plank_end_at[i] <= checked_until_here){
continue;
}
//now we need to check if there is any nail that can nail this plank.
//first, we have to discard all those nails in the queue that don't
//nail this plank.
checked_until_here = plank_end_at[i];
while ((!nail_pos_deque.empty()) &&
nail_pos_deque.front() < checked_until_here){
nail_pos_deque.pop_front();
}
//nail_scan_pos is the place we scan nails.
//if we found one at nail_at[nail_scan_pos], we put the information
//into the deque. So all those nails that appear before nail_scan_pos
//is currently in the queue or already discarded from it.
nail_scan_pos = max(nail_scan_pos, checked_until_here);
//now 'i' is the end of the plank curretly under examinened.
//so we scan any new nail until this position.
for ( ; nail_scan_pos <= i; nail_scan_pos++){
//no nail found at the current position, just go ahread.
if (nail_at[nail_scan_pos] == - 1){
continue;
}
//found a nail at the current position.
//now, we can discard away any nails that we don't use anymore.
//those nails on the left and with a larger index in C[] will never
//be required again.
while((!nail_pos_deque.empty()) &&
nail_at[nail_pos_deque.back()] > nail_at[nail_scan_pos]){
nail_pos_deque.pop_back();
}
nail_pos_deque.push_back(nail_scan_pos);
}
//if the queue is empty, there is no nail for this plank.
if (nail_pos_deque.empty()){
return -1;
}
min_nails = max(min_nails, nail_at[nail_pos_deque.front()]);
}
return min_nails + 1;
}
で、このコードを理解するのはちょっと大変かもしれないので、ゆっくり丁寧に説明して行きましょう。
まず、配列nail_at[]を用意します。この配列のそれぞれの要素nail_at[i]は、位置iに関係付けられていて、もし、その位置iに釘がなければ-1に、あれば、配列C[]の中での、その釘のインデックスが保持されています。
このような配列を作るのですが、その時に、配列C[]を後ろから前にスキャンしていますね。これは重要で、前にも話にでたように、同じ位置に釘が２本以上あるからです（これに気づかないで、勝手に釘の位置は重ならないと思っていてバグをつくっていました）。
後ろからスキャンすることにより、ある位置に２本以上釘がある場合、C[]内で最小のインデックスをもつものだけを保持します。自分達が知りたいのは、全ての板を打てる最小のインデックスまですむ釘の本数ですから、一番小さいものだけ覚えていれば全く問題ないですね。
そして、次に配列plank_end_at[]を用意します。この配列もplank_end_at[i]は位置iと関連づけられています。plank_end_at[i]には、その位置で「終わる」板の始まりの位置が何処にあるかが保存されています。例えば(a,b)という範囲の板があればplank_end_at[b] == aになっている訳です。
もし２つ以上の板が同じ位置で終わっていれば、始まりの位置が一番大きいもの（つまり、一番短い板ということになりますね）のみを、そこに保存します。他の板は無視してしまうのです。
板を無視していいの？と思われた方は、下の図を見てみましょう。明らかですが、板Aを打てる釘は全て板Bを打てますよね。もし左がi番目の釘、右がj番目の釘ですが、ここでi < jだとどうなるでしょうか？どちらにしろj番目の釘はAを打つのに必要なので、Bを打つのにj番目の釘を使っても何の問題もないですね。逆にj<iだったら、Bを打つのにもjの釘を使うべきですね（C[]の先頭から釘を使って、最小の数の釘で全ての板を打ちたいからです）。
ですから、同じ場所で板が終わっている場合、一番短い板を選べば、答えにはなんの影響も与えずに他の板は無視できる訳です。
さて、ここからが本番です。まず、配列pank_end_at[]の先頭からスキャンしていくわけですから、終わりの位置が近いものから必ず板を見て行く訳ですね（実際に何らかのソートをかけた訳ではありませんが、最初の配列pank_end_at[]を用意する際に、バケット・ソートをつかったと考えても良いでしょう。バケット・ソートの計算量はO(N)です。）
。
ここで、考えてみましょう。板の右はじが一番小さい左側よりのものから見て行く、そして同じ右端の位置のものは一番短い板のみを取って他は忘れてよかったので、以下の図のような５つのパターンが二つの板の間の関係に存在することになります。
Pattern (1): 次の板Bは、丁度今の板Aが終わったところから始まる。
Pattern (2): 次の板Bは、今の板Aが終わってから、間を空けて始まる。
Pattern (3): 次の板Bは、今の板Aの始まった位置より先に始まっていた。
Pattern (4): 次の板Bは、今の板Aが始まるのと丁度同じ位置から始まっていた。
Pattern (5): 次の板Bは、今の板Aの途中の位置から始まっていた
上のどのパターンであろうと、最初の板Aをチェックしたあとに、次の板B（と、その後の板）を打てるかもしれない釘のことは覚えていたいですよね。同時に、次の板B（と、その後の板）を打つのに関係ないこと、解答を得るのに関係しないことがわかっている釘は忘れてしまいたいですね。
たとえば、パターン１とパターン２では、最初の板Aをチェックした後、次の板Bの始まる場所より前の位置にある釘は全部忘れてしまっていいですよね。下の図で灰色の釘は、板Bを打つことはないですから、 もう覚えている必要がないですね。
他のパターンはどうでしょう？下の図をみてください。パターン３では、板Aを打てる釘は全て板Bを打てますね。ですから、板Aが始まる前に板Bを打てる釘があろうと忘れても良いですよね。Aをうつ釘がi番目、Aの後にBを打つ釘がj番目とした場合、i < jならiを使ってAもBも打つべきですよね。逆にi > jならば、どちらにしろi番目の釘を使わなければならないのでjを打ったところで、答えには関係ないということになります。板Aの後に板Bを打つ釘が別にあっても、同じ理由で関係ないですね。
とすると、上のパターン３の図でも、板Aの始まりより前に表れた釘は板Bを打てようが打てまいが、問題を考える上で関係ないということになります。
上のパターン４と５を見てみましょう。次の板Bは今の板Aの始まったところから始まるか、板Aの途中から始まっています。どちらにしろ板Aの始まる前の釘は忘れていいですね。とりあえず、板Aを打つ釘で次の板Bをかもしれない釘は覚えておきたいですね。
上をまとめると、もし今回のように、右端が小さい位置にあるものから順番に見て行く場合、とりあえず今の板を調べる時には、どのパターンでもその板の左はじより前にある釘は全部忘れてしまっていいようです。
そして、次の板Bを打つかもしれない釘は覚えておかなければ行けないということですが、これは自分の板が表れてから見つかった釘だけを覚えて行けば問題ない ということですね。
とりあえず、現在スキャニングしている位置までにある釘を覚えて行く（忘れて行く）のに、今回は両端キュー(double-ended queue)を使います（どうして単純なFIFOキューでないかは、次の段落から説明をしまs）。
さて、今度は、新たにスキャニングしている間に表れた釘のうち、どれを覚えて行くかという議論をしましょう。全部覚える必要はなさそうですからね。左から右にスキャンして釘を見つけて行っています。そして新しい釘がみつかりました。さてどうしよう？ということです。
Now, let's discuss which nails we should remember while scanning a plank. We scan the plank from the left to the right as in the below figure. Then, we found a nail that can nail this plank (see (1) of the below figure).
まずC[]で７番目の位置にある釘が見つかったとしましょう。これを取りあえずキューにいれて覚えておきましょう。ここで思い出してほしいのは配列nail_at[]では、位置iにはある位置に釘があれば、その要素nail_at[i]を見れば、その釘のC[]でのインデックスの番号がわかる訳ですね。だから、キューに入れるのは釘の位置だけで充分です。この今キューにいれた釘は次の板を打てるかもしれませんね。
さて、右にまたスキャンし続けて行って、次はC[]で３番目の位置にある釘が見つかりました（上の図の(2)の状態ですね）。３番目の釘なので、７番目ではなくこっちを使わなければならないということです。
さて、ここで７番目の釘はもう忘れてしまって良さそうです。なぜなら板の右端の位置が小さい順に調べて行っているので、７番目の釘で打てる板は、絶対に３番目の釘でも打てますよね（３番目の方が右側の位置にあるので）。パターン１、３、４、５の状態を考えてみましょう。
さらに右に進んで行くと今度は６番目の釘がみつかりました。こんどはどうしましょうか？当然覚えておきたいですよね、６番目の釘は３番目の釘が打てない板を打てるかもしれませんから。
では、３番目はどうしましょうか？これもを覚えておきたいですね。３番目と６番目の両方で打てる板が次に有る場合、3 < 6ですから、正しい答えをえるには小さいほうの３番目の釘を次の板にもつかいたいですね。
さて、次に５番目の釘がみつかったらどうしましょうか？そうですね、今度は６番目の釘をわすれてしまって、代わりに５番目の釘を覚えたいですね。６番目で打てれば、５番目の釘で必ず打てますし、５の方を使わないと正しい答えが得られない可能性があります。
以上をまとめると、キューを使って覚えて行く場合に下のような制約が守りたいということに言い換えられます。
(1) キューの中では先頭から順に位置が小さいものから必ず並んでいること
これは重要ですね。なぜなら、今調べている板の左端より左にある釘は忘れてしまいたい訳ですから、小さい順に並んでいれば、先頭から一つとって比較していらなければ捨てるというのを繰り返し、忘れてしまっては行けない釘があらわれたら、そこで繰り返しをやめればいいわけです。位置の小さい順に並んでいるとこれができますね。
(2) 釘の配列C[]でのインデックス（番号）も小さいものから並んでいてほしい。
まず、これは釘を全部調べた後、どの釘を使えばいいのか簡単に判断できますね。キューの先頭にある釘が一番C[]でインデックスが小さい、より早く使える釘ですから、正しい答えを得るためにはこれを使えば良いだけです。
どちらにしろ上のような形で釘を取捨選択していると、この制約が守られることになります。
そして、今まで見たように、キューの先頭から捨てるときとキューの後ろから捨てる時の両方があり、追加はキューの後ろにしますので、両端キューを使うと効率的に上記の釘の取捨選択のアルゴリズムが使える訳です。
解答のコードは、上記のようは方針で実装されています。まとめると
(1) 配列plank_end_atを0からM*2までスキャンします。もし現在の位置で終わる板がなければ、そのまま右へと進んで行きます。
(2) その位置で終わる板がありました。しかし、その始まりの位置が今までチェックした位置より左にあれば（＝今まで釘をチェックし終えた板の始まりの位置のうち最大のものです）、この板は無視して構いません。なぜなら、今までチェックした板を打つ釘がかならずこの板を打っているからです。その釘は絶対使われるので、それより小さい番号の新しく見つかった板をうつ釘がみつかったとしても、答えには関係ないですから。 パターン３と４を見ればわかると思います。
(3) 新しい板の始まりの位置が今までチェックした位置と同じか右にあれば（＝今まで釘をチェックし終えた板の始まりの位置のうち最大のものです）、この板はチェックしなければならないですね（パターン１、２、５ですね）。
しかし、今の板の始まりの位置より左にある釘は、もう関係なくなったということなので、全て捨ててしまいましょう。
また、今までチェックした位置（＝今まで釘をチェックし終えた板の始まりの位置のうち最大のもの）を、この板の左端の位置で更新して右に進めなければなりませんね。
(4) さて、この板の左端から、現在の位置（板の右端）まで新しい釘を探していきます。これを始める時にまだキューには幾つか以前見つかった釘が残っているかも知れません。
例えば、パターン１の時は、直前の板Aの右端にある釘があった場合、それはキューに残っていますよね。他には例えば、パターン５の場合、板Aの最初の釘は板Bの左端より右側ですから、捨てられていますが、他のものは残っています。
もし新しい釘が見つかったら、次はキューの中の最後尾を見て、新しく見つかった釘と比べています。もし古い釘の配列Cでのインデックスが新しい釘のものより大きければ、古い釘は捨てますね。次にまたキューの中の最後尾を見て同じことを繰り返します（これは釘の取捨選択のところで述べたやり方です）。もうこの条件で捨てれる釘がなければ、釘を捨てるのをやめて、キューの後ろに新しい釘を追加します。
(5) ついに現在調べている板の右端(iの位置ですね）についたとします。もし、この板を打ち付けられる釘がないなら、キューの中は空になっているはずですね。板の左端より左にある釘は最初にすてましたし、新しい釘もみつからなかったということです。この場合は、全部の釘を使っても全ての板を打てないということなので、直ちに-1を返して終了です。
(6)もしキューが空でなければ、釘の取捨選択のやり方のおかげで、キューの先頭にある釘が、この板を打てる釘のうちで、一番小さいC[]でのインデックスを持っています。それがこの釘をうてる釘のうち、最小のインデックスをもつ釘ということなので、これで現在までの「この番号まで使わないと全ての板を打てない」という番号を更新します。もし、現在のその番号が 、この板用の最小のインデックスより大きければ、そのままでよいですが、この板用の最小のインデックスの方が大きければ、それで更新しなければ行けません。
(7) さて、配列panks_end_at[]を最後までスキャンしたら、現在の「この番号まで使わないと全ての板を打てない」という情報に位置を足します。配列は０始まりですから、配列のインデックスでnまで使うということは、使う釘の本数はn+1ですね。これが答えになります。
以上が、このO(M+N)の解答の説明です。
さて、今度はこのコードが本当のO(M+N)なのか考えてみましょう。
最初の配列nail_at[]を準備するための計算量はO(M)ですね。そして配列plank_end_at[]の準備はO(N)です。
次に、このコードの本体とも言うべきネストされたループを見ましょう。まず外側のループはMに依存していますね。内側のwhileループは二つともM回以上繰り返されません（なぜならpush/popされる釘の数はM個までです）。ですから、外側のループの繰り返しとは関係ないので、単独でO(M)ですね。
内側のforループも同じで、M回以上繰り返されることはありませんね。これも実は外側のループからは独立しています。rightが０からmax_posまで、単純に増加して行くだけで、後戻りしないことを考えればわかると思います。外側のループと関係なくO(M)ですね。
つまり、このネストされたループは、全体でもO(3*M) = O(M)となります。
他のループの部分と足すとO(M + N + M) = O(2*M + N) = O(M + N)となりますね。
ということで、１００％はもらえたのですが、よりよい解答があるかどうかググるのが良い習慣ということで、検索すると、実際にO(M+N)の解答が出てきました。
ここにありました。
http://blog.csdn.net/caopengcs/article/details/41834173
中国人の方なので、説明が中国語で全く分かりませんが、コードを読んで自分が理解したことを下記に説明して行きます。
また、コードはこの理解にしたがって、わかりやすく変数名などを書き直し、さらにコメントを追加しました。
また、普段はCで答えていましたが（Codilityのパフォーマンスの測定の点がpythonなどにくらべて辛いので、不十分な解答で通ってしまうことがないとの印象からです）、両端キュー(double-ended queue, deque)を使うので、ライブラリで既に用意されているC++でプログラムを今回は書いています。（最初からC++で書けばスタックとか実装しないで良かったんですけどね…）
下のコードは、１００％のスコアをもらえます。O(M+N)になり、上のO((M + N) * log(M))の解答より格段に早いので当然といえば当然ですが。
#include <deque>
using namespace std;
int solution(vector<int> &A, vector<int> &B, vector<int> &C)
{
int max_pos = C.size() * 2;
//this vector holds -1 at nail_at[i] if there is no nail at the position i
//and k (the number of the nail) if there is.
vector<int> nail_at;
nail_at.resize(max_pos + 1, -1);
//as two or more nails can be at the same position,
//we scan C from tail to head so that we can retain the nail with
//the smallest index at each position.
for (int i = (int)C.size() - 1; i >= 0; --i){
nail_at[C[i]] = i;
}
//this vector holds -1 at plank_end_at[i]
//if there is no plank ends at the position i,
//and the beginning position of each plank, if there is.
vector<int> plank_end_at;
plank_end_at.resize(max_pos + 1, -1);
for (unsigned int i = 0; i < B.size(); i++){
//if there is any two or more planks that end at the same position,
//we only have to consider the smallest one.
plank_end_at[B[i]] = max(plank_end_at[B[i]], A[i]);
}
//a fifo queue to store the nail information.
deque<int> nail_pos_deque;
//we have checked all the nails until this position
//if it should be used or not.
int checked_until_here = 0;
int nail_scan_pos = 0;
//the minimum number of nails
int min_nails = -1;
for (int i = 1; i <= max_pos; i++){
//there is no plank end at there, just continue scanning.
if (plank_end_at[i] == -1){
continue;
}
//there is a plank, but its begining position has been already checked.
//This means that there is al least one plank successfully nailed and
//this plank can be also nailed together when the plank(s) was nailed.
//so we can simply neglect this plank.
if (plank_end_at[i] <= checked_until_here){
continue;
}
//now we need to check if there is any nail that can nail this plank.
//first, we have to discard all those nails in the queue that don't
//nail this plank.
checked_until_here = plank_end_at[i];
while ((!nail_pos_deque.empty()) &&
nail_pos_deque.front() < checked_until_here){
nail_pos_deque.pop_front();
}
//nail_scan_pos is the place we scan nails.
//if we found one at nail_at[nail_scan_pos], we put the information
//into the deque. So all those nails that appear before nail_scan_pos
//is currently in the queue or already discarded from it.
nail_scan_pos = max(nail_scan_pos, checked_until_here);
//now 'i' is the end of the plank curretly under examinened.
//so we scan any new nail until this position.
for ( ; nail_scan_pos <= i; nail_scan_pos++){
//no nail found at the current position, just go ahread.
if (nail_at[nail_scan_pos] == - 1){
continue;
}
//found a nail at the current position.
//now, we can discard away any nails that we don't use anymore.
//those nails on the left and with a larger index in C[] will never
//be required again.
while((!nail_pos_deque.empty()) &&
nail_at[nail_pos_deque.back()] > nail_at[nail_scan_pos]){
nail_pos_deque.pop_back();
}
nail_pos_deque.push_back(nail_scan_pos);
}
//if the queue is empty, there is no nail for this plank.
if (nail_pos_deque.empty()){
return -1;
}
min_nails = max(min_nails, nail_at[nail_pos_deque.front()]);
}
return min_nails + 1;
}
で、このコードを理解するのはちょっと大変かもしれないので、ゆっくり丁寧に説明して行きましょう。
まず、配列nail_at[]を用意します。この配列のそれぞれの要素nail_at[i]は、位置iに関係付けられていて、もし、その位置iに釘がなければ-1に、あれば、配列C[]の中での、その釘のインデックスが保持されています。
このような配列を作るのですが、その時に、配列C[]を後ろから前にスキャンしていますね。これは重要で、前にも話にでたように、同じ位置に釘が２本以上あるからです（これに気づかないで、勝手に釘の位置は重ならないと思っていてバグをつくっていました）。
後ろからスキャンすることにより、ある位置に２本以上釘がある場合、C[]内で最小のインデックスをもつものだけを保持します。自分達が知りたいのは、全ての板を打てる最小のインデックスまですむ釘の本数ですから、一番小さいものだけ覚えていれば全く問題ないですね。
そして、次に配列plank_end_at[]を用意します。この配列もplank_end_at[i]は位置iと関連づけられています。plank_end_at[i]には、その位置で「終わる」板の始まりの位置が何処にあるかが保存されています。例えば(a,b)という範囲の板があればplank_end_at[b] == aになっている訳です。
もし２つ以上の板が同じ位置で終わっていれば、始まりの位置が一番大きいもの（つまり、一番短い板ということになりますね）のみを、そこに保存します。他の板は無視してしまうのです。
板を無視していいの？と思われた方は、下の図を見てみましょう。明らかですが、板Aを打てる釘は全て板Bを打てますよね。もし左がi番目の釘、右がj番目の釘ですが、ここでi < jだとどうなるでしょうか？どちらにしろj番目の釘はAを打つのに必要なので、Bを打つのにj番目の釘を使っても何の問題もないですね。逆にj<iだったら、Bを打つのにもjの釘を使うべきですね（C[]の先頭から釘を使って、最小の数の釘で全ての板を打ちたいからです）。
ですから、同じ場所で板が終わっている場合、一番短い板を選べば、答えにはなんの影響も与えずに他の板は無視できる訳です。
。
ここで、考えてみましょう。板の右はじが一番小さい左側よりのものから見て行く、そして同じ右端の位置のものは一番短い板のみを取って他は忘れてよかったので、以下の図のような５つのパターンが二つの板の間の関係に存在することになります。
Pattern (1): 次の板Bは、丁度今の板Aが終わったところから始まる。
Pattern (2): 次の板Bは、今の板Aが終わってから、間を空けて始まる。
Pattern (3): 次の板Bは、今の板Aの始まった位置より先に始まっていた。
Pattern (4): 次の板Bは、今の板Aが始まるのと丁度同じ位置から始まっていた。
Pattern (5): 次の板Bは、今の板Aの途中の位置から始まっていた
上のどのパターンであろうと、最初の板Aをチェックしたあとに、次の板B（と、その後の板）を打てるかもしれない釘のことは覚えていたいですよね。同時に、次の板B（と、その後の板）を打つのに関係ないこと、解答を得るのに関係しないことがわかっている釘は忘れてしまいたいですね。
たとえば、パターン１とパターン２では、最初の板Aをチェックした後、次の板Bの始まる場所より前の位置にある釘は全部忘れてしまっていいですよね。下の図で灰色の釘は、板Bを打つことはないですから、 もう覚えている必要がないですね。
他のパターンはどうでしょう？下の図をみてください。パターン３では、板Aを打てる釘は全て板Bを打てますね。ですから、板Aが始まる前に板Bを打てる釘があろうと忘れても良いですよね。Aをうつ釘がi番目、Aの後にBを打つ釘がj番目とした場合、i < jならiを使ってAもBも打つべきですよね。逆にi > jならば、どちらにしろi番目の釘を使わなければならないのでjを打ったところで、答えには関係ないということになります。板Aの後に板Bを打つ釘が別にあっても、同じ理由で関係ないですね。
とすると、上のパターン３の図でも、板Aの始まりより前に表れた釘は板Bを打てようが打てまいが、問題を考える上で関係ないということになります。
上のパターン４と５を見てみましょう。次の板Bは今の板Aの始まったところから始まるか、板Aの途中から始まっています。どちらにしろ板Aの始まる前の釘は忘れていいですね。とりあえず、板Aを打つ釘で次の板Bをかもしれない釘は覚えておきたいですね。
上をまとめると、もし今回のように、右端が小さい位置にあるものから順番に見て行く場合、とりあえず今の板を調べる時には、どのパターンでもその板の左はじより前にある釘は全部忘れてしまっていいようです。
そして、次の板Bを打つかもしれない釘は覚えておかなければ行けないということですが、これは自分の板が表れてから見つかった釘だけを覚えて行けば問題ない ということですね。
とりあえず、現在スキャニングしている位置までにある釘を覚えて行く（忘れて行く）のに、今回は両端キュー(double-ended queue)を使います（どうして単純なFIFOキューでないかは、次の段落から説明をしまs）。
さて、今度は、新たにスキャニングしている間に表れた釘のうち、どれを覚えて行くかという議論をしましょう。全部覚える必要はなさそうですからね。左から右にスキャンして釘を見つけて行っています。そして新しい釘がみつかりました。さてどうしよう？ということです。
Now, let's discuss which nails we should remember while scanning a plank. We scan the plank from the left to the right as in the below figure. Then, we found a nail that can nail this plank (see (1) of the below figure).
まずC[]で７番目の位置にある釘が見つかったとしましょう。これを取りあえずキューにいれて覚えておきましょう。ここで思い出してほしいのは配列nail_at[]では、位置iにはある位置に釘があれば、その要素nail_at[i]を見れば、その釘のC[]でのインデックスの番号がわかる訳ですね。だから、キューに入れるのは釘の位置だけで充分です。この今キューにいれた釘は次の板を打てるかもしれませんね。
さて、右にまたスキャンし続けて行って、次はC[]で３番目の位置にある釘が見つかりました（上の図の(2)の状態ですね）。３番目の釘なので、７番目ではなくこっちを使わなければならないということです。
さて、ここで７番目の釘はもう忘れてしまって良さそうです。なぜなら板の右端の位置が小さい順に調べて行っているので、７番目の釘で打てる板は、絶対に３番目の釘でも打てますよね（３番目の方が右側の位置にあるので）。パターン１、３、４、５の状態を考えてみましょう。
さらに右に進んで行くと今度は６番目の釘がみつかりました。こんどはどうしましょうか？当然覚えておきたいですよね、６番目の釘は３番目の釘が打てない板を打てるかもしれませんから。
では、３番目はどうしましょうか？これもを覚えておきたいですね。３番目と６番目の両方で打てる板が次に有る場合、3 < 6ですから、正しい答えをえるには小さいほうの３番目の釘を次の板にもつかいたいですね。
さて、次に５番目の釘がみつかったらどうしましょうか？そうですね、今度は６番目の釘をわすれてしまって、代わりに５番目の釘を覚えたいですね。６番目で打てれば、５番目の釘で必ず打てますし、５の方を使わないと正しい答えが得られない可能性があります。
以上をまとめると、キューを使って覚えて行く場合に下のような制約が守りたいということに言い換えられます。
(1) キューの中では先頭から順に位置が小さいものから必ず並んでいること
これは重要ですね。なぜなら、今調べている板の左端より左にある釘は忘れてしまいたい訳ですから、小さい順に並んでいれば、先頭から一つとって比較していらなければ捨てるというのを繰り返し、忘れてしまっては行けない釘があらわれたら、そこで繰り返しをやめればいいわけです。位置の小さい順に並んでいるとこれができますね。
(2) 釘の配列C[]でのインデックス（番号）も小さいものから並んでいてほしい。
まず、これは釘を全部調べた後、どの釘を使えばいいのか簡単に判断できますね。キューの先頭にある釘が一番C[]でインデックスが小さい、より早く使える釘ですから、正しい答えを得るためにはこれを使えば良いだけです。
どちらにしろ上のような形で釘を取捨選択していると、この制約が守られることになります。
そして、今まで見たように、キューの先頭から捨てるときとキューの後ろから捨てる時の両方があり、追加はキューの後ろにしますので、両端キューを使うと効率的に上記の釘の取捨選択のアルゴリズムが使える訳です。
解答のコードは、上記のようは方針で実装されています。まとめると
(1) 配列plank_end_atを0からM*2までスキャンします。もし現在の位置で終わる板がなければ、そのまま右へと進んで行きます。
(2) その位置で終わる板がありました。しかし、その始まりの位置が今までチェックした位置より左にあれば（＝今まで釘をチェックし終えた板の始まりの位置のうち最大のものです）、この板は無視して構いません。なぜなら、今までチェックした板を打つ釘がかならずこの板を打っているからです。その釘は絶対使われるので、それより小さい番号の新しく見つかった板をうつ釘がみつかったとしても、答えには関係ないですから。 パターン３と４を見ればわかると思います。
(3) 新しい板の始まりの位置が今までチェックした位置と同じか右にあれば（＝今まで釘をチェックし終えた板の始まりの位置のうち最大のものです）、この板はチェックしなければならないですね（パターン１、２、５ですね）。
しかし、今の板の始まりの位置より左にある釘は、もう関係なくなったということなので、全て捨ててしまいましょう。
また、今までチェックした位置（＝今まで釘をチェックし終えた板の始まりの位置のうち最大のもの）を、この板の左端の位置で更新して右に進めなければなりませんね。
(4) さて、この板の左端から、現在の位置（板の右端）まで新しい釘を探していきます。これを始める時にまだキューには幾つか以前見つかった釘が残っているかも知れません。
例えば、パターン１の時は、直前の板Aの右端にある釘があった場合、それはキューに残っていますよね。他には例えば、パターン５の場合、板Aの最初の釘は板Bの左端より右側ですから、捨てられていますが、他のものは残っています。
もし新しい釘が見つかったら、次はキューの中の最後尾を見て、新しく見つかった釘と比べています。もし古い釘の配列Cでのインデックスが新しい釘のものより大きければ、古い釘は捨てますね。次にまたキューの中の最後尾を見て同じことを繰り返します（これは釘の取捨選択のところで述べたやり方です）。もうこの条件で捨てれる釘がなければ、釘を捨てるのをやめて、キューの後ろに新しい釘を追加します。
(5) ついに現在調べている板の右端(iの位置ですね）についたとします。もし、この板を打ち付けられる釘がないなら、キューの中は空になっているはずですね。板の左端より左にある釘は最初にすてましたし、新しい釘もみつからなかったということです。この場合は、全部の釘を使っても全ての板を打てないということなので、直ちに-1を返して終了です。
(6)もしキューが空でなければ、釘の取捨選択のやり方のおかげで、キューの先頭にある釘が、この板を打てる釘のうちで、一番小さいC[]でのインデックスを持っています。それがこの釘をうてる釘のうち、最小のインデックスをもつ釘ということなので、これで現在までの「この番号まで使わないと全ての板を打てない」という番号を更新します。もし、現在のその番号が 、この板用の最小のインデックスより大きければ、そのままでよいですが、この板用の最小のインデックスの方が大きければ、それで更新しなければ行けません。
(7) さて、配列panks_end_at[]を最後までスキャンしたら、現在の「この番号まで使わないと全ての板を打てない」という情報に位置を足します。配列は０始まりですから、配列のインデックスでnまで使うということは、使う釘の本数はn+1ですね。これが答えになります。
以上が、このO(M+N)の解答の説明です。
さて、今度はこのコードが本当のO(M+N)なのか考えてみましょう。
最初の配列nail_at[]を準備するための計算量はO(M)ですね。そして配列plank_end_at[]の準備はO(N)です。
次に、このコードの本体とも言うべきネストされたループを見ましょう。まず外側のループはMに依存していますね。内側のwhileループは二つともM回以上繰り返されません（なぜならpush/popされる釘の数はM個までです）。ですから、外側のループの繰り返しとは関係ないので、単独でO(M)ですね。
内側のforループも同じで、M回以上繰り返されることはありませんね。これも実は外側のループからは独立しています。rightが０からmax_posまで、単純に増加して行くだけで、後戻りしないことを考えればわかると思います。外側のループと関係なくO(M)ですね。
つまり、このネストされたループは、全体でもO(3*M) = O(M)となります。
他のループの部分と足すとO(M + N + M) = O(2*M + N) = O(M + N)となりますね。
0 件のコメント:
コメントを投稿