Lesson 6: EquiLeader (Equi Leader)

Lesson 6: EquiLeaderhttps://codility.com/programmers/lessons/6

この解答ではCodilityが下のPDFで書いているO(N)の計算量のアルゴリズムをleaderを見つけるのに使っているので、まず見てください。
Open reading material (PDF)

で、問題ではequi leaderの定義が以下のようにされています。
``An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.''

ここを考えると解答に近づけそうですね。

まず、Xという値が全体の配列Aのleaderだとしましょう。そしてその出現回数をcntXとします。

そして、他にYという何でもいいですが、Xとは違う値を想定しましょう。その出現回数をcntYとします

Xがleaderという仮定ですから、cntX > N / 2が定義から成り立ちますね。

そうなると必ずcntY < N / 2となります（X以外の値が全部Yでも上の定義から、この必ずこうなりますね）

ここでcntX > N / 2かつN / 2 > cntYですからcntX > cntYといえますね。

さて、問題は、ここからです。全体の配列AのleaderであるX以外にequi leaderをもてる値があるのでしょうか？これがもし存在しなければ、かなり簡単にとける問題になりそうですね。こたえは、存在しない＝簡単にとける問題である、ということになります。

どうしてでしょう？それでは、Yがequi leaderを持てるとしましょう。その時のインデックスをSとしてみますね。定義より、A[0], A[1], ... , A[S]の中ではYがXより多く出現するということになります。

では、そう仮定して、XとYのそれぞれのA[0], A[1], ... ,A[S]の中での出現回数をそれぞれcntX_L, cntY_Lとしてみましょう。

Yがこの範囲ではleaderになると仮定したので、cntY_L > cntX_Lとなりますね。YのほうがXよりこの範囲では多く出現するとしたためです。

Yがequi leaderを持っている、その時のインデックスがSとしたので、分割された右側の配列でもYがXより多く出現していなければなりませんね。そうでなければ、右側の配列でのleaderにはなれませんよね。

X,Yそれぞれ全体の出現回数がcntX, cntY、Sから左側の配列での出現回数をそれぞれ、cntX_L，cntY_Lとしたので、右側での出現回数は、それぞれcntX - cntX_L， cntY - cntY_L となりますよね。

で、ここでYが右側でもleaderなので必ずXより出現回数が多くならねばいけないので、
cntX - cntX_L < cntY - cntY_L とならなければいけません。

が、これは矛盾してますね！

だって

cntX   > cntY

cntX_L < cntY_L

という想定なんですから、

cntX - cntX_L > cntY - cntY_L になっていなければおかしいですよね。

つまり、全体の配列のleaderであるX以外にはequi leaderをもてる値はないということになります。


上の条件がわかりましたので、後は簡単ですね。

まず全体のleaderとその出現回数を求めます。
そして、再度配列をスキャンして、現在位置までのleaderの出現回数をカウントしていきます。

この情報がそろっていれば、その現在スキャンしている位置でequil leaderの条件が整っているか調べて、あっていれば答えになるequil leaderのカウンタを増やせばいいですね。

この方針で１００％のスコアがもらえます。

#include <alloca.h>

int solution(int A[], int N) {
    
    //first find the leader and count its occurances.
    //as all the values on the stack will be the same,
    //we only have to keep one value.
    int sp = 0;
    int candidate = 0;
    
    int i;
    for (i = 0; i < N; i++){
        if (sp == 0){
            sp++;
            candidate = A[i];
            continue;
        }
        
        if (candidate == A[i]){
            sp++;
        }
        else {
            sp--;
        }
    }
    
    //if there is no leader, there is no equi leader.
    if (sp == 0){
        return 0;
    }
    
    //now we check if the candidate value is really a leader
    int cnt = 0;
    for (i = 0; i < N; i++){
        if (A[i] == candidate){
            cnt++;
        }
    }
    
    //if there is no leader, there is no equi leader.
    if (cnt <= N / 2){
        return 0;
    }
    
    //now we have a leader.
    int leader = candidate;
  
    
    //let's count the number of equi leader.
    int lcnt = 0; //leader appeard until the index.
    int ans  = 0; //the number of equi leaders.
    for (i = 0; i < N; i++){
        if (A[i] == leader){
            lcnt++;
        }
        //check if the current index is a equi leader
        int lelems = i + 1;
        if ((lcnt > lelems / 2) && 
            ((cnt - lcnt) > (N - lelems) / 2)){
            ans++;
        }
    }
    
    return ans;

}

Lesson 5: StoneWall (Stone Wall)

Lesson 5: StoneWall
https://codility.com/programmers/lessons/5

これはCodilityのブログに解説がありますので、そちらをごらんください。
http://blog.codility.com/2012/06/sigma-2012-codility-programming.html


とはいえ、自分でやってみました。

#include <alloca.h>

int solution(int H[], int N) {
    
    int *stack = (int*)alloca(sizeof(int) * N);
    int sp = 0;

    int cnt = 0;
    
    
    int i;
    for (i = 0; i < N; i++){
        
        //if there is no stone on the left, we need a new stone.
        if (sp == 0){
            cnt++;
            stack[sp++] = H[i];
            //check the next height.
            continue;
        }
        
        //there is at least one stone on the left
        
        //the same hight, we don't need a new stone.
        if (stack[sp - 1] == H[i]){
            //check the next height.
            continue;
        }
        
        //the hight goes up, we need a new stone
        if (stack[sp -1] < H[i]){
            cnt++;
            stack[sp++] = H[i];
            //check the next height.
            continue;
        }
        
        //the hight goes down, try rewinding the stack
        while(1){
                    
            //the stone on the left is still heigher.
            //try rewind the stack.
            if (stack[sp - 1] > H[i]){
                sp--;
                
                //reached the bottom of the stack.
                if (sp == 0){
                    //we need a new stone.
                    cnt++;
                    stack[sp++] = H[i];
                    break;        
                }
                continue;
            }
            
            //there is a stone with the same height on the left.
            //this can continue grow to the right.
            if (stack[sp - 1] == H[i]){
                break;
            }
            
            //the stone on the left is lower than the new height.
            //there is need for a new stone.
            stack[sp++] = H[i];
            cnt++;
            break;
        }
        
    }
    
    return cnt;
}

ですが、Codilityのブログを見ればわかる通り、条件を整理して行くともう少し短いコードにすることができます。まずスタックを巻き戻す動作をするという方針で、if文を整理する感じですね。（とはいうものの、短いコードが常にわかりやすい訳ではありませんが）。これも100%のスコアのを書いておきましょう。

#include <alloca.h>

int solution(int H[], int N) {
    
    int *stack = (int*)alloca(sizeof(int) * N);
    int sp = 0;

    int cnt = 0;
    
    int i;
    for (i = 0; i < N; i++){
        
        //try rewind the stack first.
        while (sp > 0 && stack[sp - 1] > H[i]){
            sp--;
        }
        
        //when the code reaches here, it is always
        //sp == 0 and/or stack[sp - 1] < H[i].
        
        //if there is the stone with the same height, 
        //simply keep on using it!
        if (sp > 0 && stack[sp - 1] == H[i]){
            continue;
        }

        //if not, we need a new stone.
        stack[sp++] = H[i];
        cnt++;
    }
    
    return cnt;
}

Lesson 5: Fish (Fish)

Lesson 5: Fish
https://codility.com/programmers/lessons/5

シンプルな解答はスタックを使うことにより実現できます。
まず、下って行く魚だけにスタックを用意しましょう。

そして、魚のサイズと向きの配列を先頭からスキャンして行きましょう。

もし現在見ているポジションの魚が下っているなら、そのままスタックにのせます。

もし現在見ているポジションの魚が登っているなら、このスタックから、自分より大きな魚に出会うまで魚を食べ続けます。自分より大きな魚にであったら、その場で死んでしまいますが、あわずにスタックが空になった場合、それは上流の端までたどり着いたということなので、生き残ります。

最終的には、上流に向かって生き残った魚の数と、最後にスタックに残った下流に進んで行った魚の数が、全体的に生き残った魚の数の合計となります。

これで１００％のスコアがもらえます。

#include <alloca.h>

int solution(int A[], int B[], int N) 
{
    int memsize = sizeof(int) * N;

    //stack (memory & index)
    int* down   = (int*)alloca(memsize);
    
    int d = 0;

    //the counter for the fish that reached to the end of the river.    
    int cnt_reached = 0;

    int i;
    for (i = 0; i < N; i++){        
        
        //if the fish is going upstream,
        //check if it can reach the upper end.
        if (B[i] == 0){
            while(1){
                //if there is no more fish against it,
                //it reaches the upper end.
                if (d == 0){
                    cnt_reached++;
                    break;
                }
                //met a bigger one, they it is eaten..
                if (down[d - 1] > A[i]){
                    break;
                }
                //we keep on eating the fish...
                d--;
            }
            continue;
        }
        down[d] = A[i];
        d++;
    }
    
    return cnt_reached + d;
}

Lesson 5 : Brackets (Brackets)

Lesson 5 : Brackets
https://codility.com/programmers/lessons/5

これは、括弧のマッチングをみる簡単な課題ですね。一番シンプルな解答をしてみましょう。

簡単にいうと、左括弧 （,[, {が現れた時にはスタックに積みます。そして、右括弧), ], }が現れた時に、スタックのてっぺんにある左括弧が、マッチしているかを調べれば良い訳です。

また、最後に全ての左括弧がきちんと閉じられている＝スタックの大きさがゼロであるということを調べなければいけません（考えないでやると忘れがちですね）。

これで１００％のスコアになります。

#include <alloca.h>

int solution(char *S) {
    
    int len = strlen(S);
    
    if (len == 0){
        return 1;
    }
    
    //I always wonder why thye don't tell anything about
    //what we shoud do when memory allocation failed 
    //in codility problems...
    char*   stack = (char*)alloca(len);
  
  
    int idx = 0;  //this is a stack pointer.
    
    int i;
    //scan the character one-by-one
    for (i = 0; i < len; i++){
        char c = S[i];
        
        switch(c){
            //if the character is '(', '[', '{',
            //just push it onto the stack.
            case '(':
            case '[':
            case '{':
                stack[idx] = c;
                idx++;
                break;
                
            //if the character is '(', '[', '{',
            //check if the last character matches with each
            case ')':
                idx--;
                if (stack[idx] != '('){
                    return 0;
                }
                break;
            case ']':
                idx--;
                if (stack[idx] != '['){
                    return 0;
                }
                break;
            case '}':
                idx--;
                if (stack[idx] != '{'){
                    return 0;
                }
                break;
            default:
                return 0;
        }
    }
    
    //we need to see if the string is terminted collectly
    if (idx != 0){
        return 0;
    }
    
    return 1;
}

Lesson 5 : Nesting (Nesting)

Lesson 5 : Nesting
https://codility.com/programmers/lessons/5

メモリ使用量を O(1)で解けとの課題。

方針としては、'('と')'の数がマッチしていればよい。ただし、途中で'）'の数が増えていると、間違った文字列が与えられているということになることに注意。また、空文字列も許容される。

これで１００％のスコアがもらえます。

int solution(char *S) 
{
    int lnum = 0;
    int rnum = 0;
    
    char *p = S;
    
    //the string can be empty. no need to scan.
    if (*p == NULL){
        return 1;
    }
    
    while(*p != NULL){
        if (*p == '('){
            lnum++;
        }
        else {
            //the number of ')' can never exceed the number of '('
            rnum++;
            if (rnum > lnum){
                return 0;
            }
        }
        p++;
    }
    
    return lnum == rnum;
}

Lesson 4: NumberOfDiscIntersections (Number of DiscIntersections)

Lesson 4: NumberOfDiscIntersections
https://codility.com/programmers/lessons/4

ちょっと忙しかった時期があり、解答にも説明にも時間がかかる問題だったので放っておいたら、ブログのことをすっかり忘れていましたが、とりあえずアフィり許可がもらえたのでついでに再開しました。

で、この問題なんですが、凄く難しい上に、解答や説明が間違っているものがいろんなブログでありました（そのせいでちょっときちんと理解するのに手間がかかったり、説明を考えなければ行けませんでした。）。

基本的に、この問題はコンパイラ等を勉強するとレジスタ割り付けで出てくるような、「生存区間分析」とちょっと似た問題です。

とりあえず、いろいろな答えがあるのですが、段階を踏んで理解しつつ一番良い答えにたどり着きましょう。

1. 一番簡単な解答

一番シンプルな解答は、単に一つ一つディスクをとりあげて、他と重なるか見て行くことです。当然、スコアは最悪になります。


計算量も 'detected time complexity: O (N ** 2)' と表示され、まぁ、実際そんなもんです。

int solution(int A[], int N) 
{   
    int cnt = 0;     int i, j;     
    for (i = 0; i < N - 1; i++){         long long curl = (long long)i - A[i];         long long curr = (long long)i + A[i];         for (j = i + 1; j < N; j++){             long long posl = (long long)j - A[j];              long long posr = (long long)j + A[j];              
            if (posl <= curr && curl <= posr){                  cnt++;                  if (cnt > 10000000){                      return -1;                  }              }             }     }   return cnt; }

2. もうちょっと良いやり方。

もっと良いやり方を考えるために、とりあえず図にして考えてみましょう。これも他の人がよくやっている解答のようです。ソートも使いますし、sortingのセクション(Lesson 4)にあるには適切な解答かと思います。問題の要求するパフォーマンスにも合致しますし。

下にあるのが、例題のデータを図にした物です。線になっていますが、discの左端と右端に線を引いて、どこからどこまでdiscがあるか書いてあります。

こうやってみてみると、コンパイラの授業でやる生存区間の分析にそっくりですね。（日本の大学では授業ではそこまでやらないで、院に進む学生が自分で勉強するのでしょうか？）

それぞれのA[]の要素でしめされるディスクを変数とかんがえれば、それがコードのどこから何処の間で行きているか？みたいな問題になりますね。数を数えて、CPUのレジスタが足りなければ、メモリに一時的にでも変数の値を逃がす必要が出てきます。

なので、とりあえず生存区間分析の問題と思ってみて行けばいいのでしょうね。

生存区間が重なってるdiscは互いにintersectionがあると考えて良さそうです。でも実際には今回の問題ではいちいち生存しているdiscのペアを 全部あげる必要はなく、重なっている数だけですので、ちょっとしたテクニックが仕える訳です。
簡単に言うと、あるdiscが死ぬ時に、そこで行きている全部のdiscの数をが分かっていれば、それから１（discを引く）と、そこまでで生きているdiscにたいして重なっているdiscの数がわかりますね。

ですから、ソートを上手く使ったのちに、そのソートした配列を順番にスキャンしていけば上手く行きそうです。

このアプローチで一応100%のスコアがもらえ、計算の複雑性は, the detected time complexity is 'O(N * log(N)) or log(N)'と評価されます。,実際にはquick sort 'O(N * log(N))' が二つで、一つのfor loop でその後配列をスキャンする 'O(N)'の組み合わせです。(だから O(2 * N * log(N) + N),で、大きい方をとるとO(N * log(N) )の扱いになりますね。).

#include <alloca.h>

int compare(const void* a, const void *b)
{
    long long l = *((long long*)a);
    long long r = *((long long*)b);

    if (l == r){
        return 0;
    }

    return l < r ? -1 : 1;
}

int solution(int A[], int N) {

    int memsize = sizeof(long long) * N;
    long long* activate = (long long*)alloca(memsize);
    long long* deactivate = (long long*)alloca(memsize);

    long long i = 0;
    for (   ; i < N; i++){
        activate[i] = i - A[i];
        deactivate[i] = i + A[i];
    }

    qsort(activate, N, sizeof(long long), compare);
    qsort(deactivate, N, sizeof(long long), compare);

    long long total = 0;

    long long currentActive = 0;
    long long activatedIndex = 0;
    long long deactivatedIndex = 0;

    for (i = 0; i < N; i++){

        while (activate[activatedIndex] <= deactivate[deactivatedIndex] &&
               activatedIndex < N){
            activatedIndex++;
            currentActive++;
        }

        currentActive--;
        total += currentActive;
        if (total > 10000000){
            return -1;
        }
        deactivatedIndex++;
    }

    return total;
}


このコードだけ見ても、ちょっと掴みづらいかと思いますので、図で説明して行きましょう。とりあえず、右端、左端はそれぞれ別の配列にソートしてあり、小さいところから見て言っています。ここでもういちど、全部のペアを取る必要はなく、単にintersectionの数を数えれば良いだけのことにもう一度留意しましょう。

いま一番小さい右端をもつのは、A[0]のdiscですね。この'1'に注目すると、そこまでにある左端のかずは４つですね（A[0], A[1], A[2], A[4])です。A[0]がいま、一番小さい右端であるという前提でチェックしてるのですから、ここより小さい左端があるということは、必ずA[0]のディスクと重なっているディスクの左端だという事になります。

もし重なっていないディスクがこの中に含まれているとすると、A[0]の左端-1より小さいところに、そのディスクの右端がふくまれていることになり、A[0]が一番小さいという仮定（ソートしましたよね、さっき）に反しますね。

ですから、４つのディスクが１の時点まで生きていて、全てA[0]かそれとかさなっているディスクということになります。ここで１の時点で死ぬA[0]と他のディスクの重なりの数は、４−１＝３となります。

下の図を見て考えてみてください。

では、次にA[0]のディスクをもう取り除いてしまいましょう。なぜなら、A[0]と重なるディスクは全て数えたのですから、取り除いて数えてしまって構いませんね。もし残しておいて２度数えたらおかしな結果になりますよね。

取り除いたあと、今の状況で最も小さい右端をもつディスクはどれでしょうか？A[2]かA[3]ですね。どちらをとっても結局おなじ答えになるので、今回はA[2]を取ってみましょう。（興味がある方は、自分で同じようにためしてみてください）。

今はすでにA[0]は取り除かれたと考えているので、一番小さい右端はA[2]で、ここより左に左端をもつディスクは全て、A[2]とかさなっていると考えられますよね。そうでなければ、ソートしてあり現在はA[2]が最小だと言う仮定に反します。

今度は４にたどり着くまでに、A[3]の左端２で新しくもうひとつディスクが生まれました。そうすると、先ほどまで生きていたものと足して、４の時点では４つのディスクが生きていますね。さきほどの段階と同じようにA[2]が４で死ぬのですが、ここで３つのディスクがA[2]と重なっていることがわかりましたので、４−１＝３があらたにintersectionの合計に加えられます。先ほどの３と加えて、合計３＋３＝６が今までに見つかったintersectionになります。

それでは再度、A[2]を取り除いて同じことをしましょう。


今度はもう、新しいディスクは生まれないままA[3]の右端4にたどり着きますね。
生きているディスクは３のままですから、A[3]と重なるディスクは２つになります。
なので、結果、今のところのintersectionの合計は3 + 3 + 2 = 8になりますね。

A[3]をとりのぞいて次に行きましょう。

A[5]にきましたが、これはディスクですが面積が０の点です。つまり５で生まれて５で直ぐ死ぬということですね。ですからA[5]が生まれてから、すぐ死ぬ直前では３つのディスクが生きているので、A[5]と重なるディスクは２つになります。つまり3 + 3 + 2 + 2 = 10が現在のintersectionの合計です。

また５を取り除いてみましょう。

次はA[1]の６が一番小さいですね。生きているディスクは２つですから、A[1]と重なるディスクの数は２−１＝１になります。これで合計すると3 + 3 + 2 + 2 + 1 = 11のインターセクションがここまで見つかりました。

そしてA[1]を取り除くともう一つしか残っていませんね。

つまり、もう他のディスクはみな死んだので、何とも重なっていません。ですから先ほどえた１１が解答になるわけです。


上のように図示したことで、わかりやすくなりましたか？もういちど強調したいのは、実際の生きているディスクのペアを取らなくていい問題で、単に数を数える問題ですから、上のようなアルゴリズムで、重なっている数だけを数えて行けば良かったのですね。

つまり、ディスクがactiveになる（liveになる)かdeactive(deadになる）かなるイベントをソート後に見て行けば、現在注目しているディスクの右端が一番小さい右端という仮定にもとづいて、そこより左に左端があるディスクは全て重なっていると言える。そうでなければ（重なっていないとすると）、現在注目しているディスクの右端より、左側に右端があるディスクがあると言うことになってしまう（そのディスクの右端が現在注目しているディスクの左端より左側にあることがこの場合重ならない条件ですね）ので、仮定に反するということになります。

ですから、今注目しているディスクの右端が一番小さいならば、そこより左側に左端があるディスクは絶対重なっていると言えるということです。

この性質をかんがえると、結局、有る地点でactiveなディスクの数が分かれば良いだけなので、更に問題を単純かして、ソートすらする必要がなくなります。

3. the best solution

上で述べた考えは、これはstack overflowで議論されていた解答で、ソートもいらないでO(N)の解答につながって行きます。ソートもいらないんですから、codilityの問題がソートのセクションにあるのがおかしいんじゃないかとも思うんですが、こういった詰めの甘さが常にcodilityにあるので、気にしないでいいのかもしれません。

http://stackoverflow.com/questions/4801242/algorithm-to-calculate-number-of-intersecting-discs

で、今から説明するやり方でも、きちんと１００％がでます。

この解答を理解するために、まずは、もうちょっと簡単にして考えましょう。
とりあえず、いままで分かったことは、実際に重なるディスクのペアは考えないでよく、重なりの数を数えるだけでした。そして、ある区間での生存状況と考えて調べて行きましたね。

結局分かったことは、「単にactivateされるイベントとdeactivateされるイベントがわかれば、0からN-1の数直線状の区間の有る点で、生きているディスクの数は分かるということです。

ですから、ソートするという考え方を辞めて二つの配列に、その数直線状の点で、activeになるイベントが幾つ発生したか、deactiveになるイベントが幾つ発生したかを考えればよさそうです。

そしてdeactiveになったときに我々はそこまで生きているactiveなディスクの数がわかれば、それから１をひくだけで、deactiveになったディスクと他のディスクの間のintersectionの数を得られるのでしたね。

とりあえず、この方針でかかれたのが下のコードです。今度はactivated, deactivatedの配列が用意されていますが、これらはactivate[i]やdeactivate[i]の時点で、activate/deactivateの各イベントが何回起きているかということを記録します。

また、仕様よりどのディスクの 右端も、からなず正になりますし、右端でそのディスクがdeactivateされると考えて重なりを計算するので,−１以下の左端は、0のところで始まったと考えてもよいということになります。同じような理由でN-1より右にディスクの左端があった場合、N-1で終わっていると考えてもよいことになりますね。


#include <memory.h>
#include <alloca.h>

int solution(int A[], int N) {
    
    int memsize = sizeof(int) * N;
    int* activated   = (int*)alloca(memsize);
    int* deactivated = (int*)alloca(memsize);
    
    memset(activated    , 0x00, memsize);
    memset(deactivated  , 0x00, memsize);
    
    int i;
    //counter the number of activation/deactivation at the index.
    for (i = 0; i < N; i++){
        //if the lower limit is below 0, consider it as 0.
        //this won't affect the number of activated discs at the index.
        long long lower_lim = i - (long long)A[i]; 
        lower_lim = lower_lim < 0 ? 0 : lower_lim;
        activated[lower_lim]++;
        
        //the same to the upper limit.
        long long upper_lim = i + (long long)A[i];
        upper_lim  = upper_lim > N - 1 ? N - 1 : upper_lim;
        deactivated[upper_lim]++;
    }
    
    //let's scan the activated/deactivated arrays.
    int total = 0;
    int active = 0;
    for (i = 0;  i < N; i++){
        active += activated[i];
        if (active == 0 || deactivated[i] == 0){
            continue;
        }
        
        
        //we have at least one deactivated disc at the index 'i'.
        while (deactivated[i] > 0){
            //active - 1is the number of the new intersection.
            total += active - 1;   
            if (total > 10000000){
                return -1;
            }
            //one disc is dead.
            //so decrement the number of active discs.
            active--;
            deactivated[i]--;
        }
    }
    
    return total;
}


さて、このコードのwhileループでは、ご丁寧にdeactivateのイベント一回につき、重なりの数を計算してtotalに足し、もし同じ地点に別のdeactivateイベントが残っていれば、さらにそれを同じ方針で何度も計算します。

でも、これ実際には等差数列の合計と全く同じですよね。たとえば７つ生存しているディスクがそこまでにあって、その地点で３つディスクが死ぬとすると、６、５、４とそれぞれのdeactivateイベントで合計にたされるわけですから。

つまり等差数列の和の計算の公式Sn = n (a + l) / 2（Snは合計、nは項数、aは初項、lは末項）でループ等せずとも計算できますね。

これをコードに適用して以下のようにします。当然パフォーマンスもあがるわけですし、１００％がもらえます。

#include <memory.h>

#include <alloca.h>

int solution(int A[], int N) {

    

    int memsize = sizeof(int) * N;

    int* activated   = (int*)alloca(memsize);

    int* deactivated = (int*)alloca(memsize);

    

    memset(activated    , 0x00, memsize);

    memset(deactivated  , 0x00, memsize);

    

    int i;

    //counter the number of activation/deactivation at the index.

    for (i = 0; i < N; i++){

        //if the lower limit is below 0, consider it as 0.

        //this won't affect the number of activated discs at the index.

        long long lower_lim = i - (long long)A[i]; 

        lower_lim = lower_lim < 0 ? 0 : lower_lim;

        activated[lower_lim]++;

        

        //the same to the upper limit.

        long long upper_lim = i + (long long)A[i];

        upper_lim  = upper_lim > N - 1 ? N - 1 : upper_lim;

        deactivated[upper_lim]++;

    }

    

    //let's scan the activated/deactivated arrays.

    int total = 0;

    int active = 0;

    for (i = 0;  i < N; i++){

        active += activated[i];

        if (active == 0 || deactivated[i] == 0){

            continue;

        }

        //Sn = n * (a + l) / 2

        //  where   Sn  is the sum of the sequence 9, 8, 7, 6, 5 ...

        //          n   is the number of terms  (= deactivated[i])

        //          a   is the first term       (= active - 1)

        //          n   is the last term        (= active - deactivated[i])

        //

        //int sn = deactivated[i] * ( (active - 1) + (active - deactivated[i]) / 2

        int sn = deactivated[i] * (2 * active - 1 - deactivated[i]) / 2;

        total += sn;

        if (total > 10000000){

            return -1;

        }

        active -= deactivated[i];

    }

    

    return total;

}

この問題は難しいし面白いかもしれませんが、いつ役にたつアルゴリズムなのか、自分は全く思いつきません。

ただ、様々なトリックをつかえるように問題が単純化してあるという嫌らしさです。この単純化のせいで良い解答が難しくなっているようですが、単純化したせいでこのアルゴリズムが他で役にたつのかというと、何処で役に立つか分かりません。本当にこういうのひつような状況があるのかなと思います．

実際のlinear register allocationなどを実装するときには、生きている変数のセットや知らないと、どの変数をレジスタにおいておくか、メモリに逃すかという判断が出来なくなるわけで、重なりの数だけ数えて意味がある場合はないですし、いつ使うんだろ、こういう戦略？