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;

}