dility Lesson5 - GenomicRangeQuery

コード#コード#

初めての試み
時間の複雑さ:O(N*M)->タイムアウト

// you can use includes, for example:
// #include <algorithm>
#include <string>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    // write your code in C++14 (g++ 6.2.0)
    vector<int> answer;
    int memo[27] ={0,};
    memo['A'-'A'] = 1;
    memo['C'-'A'] = 2;
    memo['G'-'A'] = 3;
    memo['T'-'A'] = 4;
    for(int i=0;i<P.size();i++) {
        string str = S.substr(P[i],Q[i]-P[i]+1);
        int min = 999;
        for(int j=0;j<str.length();j++) {
            min = min > str[j]-'A' ? str[j]-'A' : min;
        }
        answer.push_back(memo[min]);
    }

    return answer;
}

タイムアウトが予想されていましたが、試した解答です.中间のmemo[27]はif4つのドアが书きたくないだけで书かれたコード...ほほほ
論理はsubstrを用いて遺伝的に区分され、forゲートを迂回してminを比較しただけである.やっぱりタイムアウト
二次試行
時間の複雑さ:O(N+M)->合格しましたが、テストケースはフィルタリングできなかったようです.

// you can use includes, for example:
// #include <algorithm>
#include <string>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    // write your code in C++14 (g++ 6.2.0)
    vector<int> answer;
    vector<vector<int>> memo;
    vector<int> A, C, G, T;

    for(int i=0;i<S.length();i++) {
        if(S[i] == 'A') {
            A.push_back(i);
        } else if(S[i] == 'C') {
            C.push_back(i);
        } else if(S[i] == 'G') {
            G.push_back(i);
        } else if(S[i] == 'T') {
            T.push_back(i);
        }
    }
    memo.push_back(A);
    memo.push_back(C);
    memo.push_back(G);
    memo.push_back(T);

    for(int i=0;i<P.size();i++) {
        for(int j=0;j<4;j++) {
            bool flag = false;
            for(int k=0;k<memo[j].size();k++) {
                if(memo[j][k] >= P[i] && memo[j][k] <= Q[i])
                {
                    flag = true;
                    answer.push_back(j+1);
                    break;
                }
            }
            if(flag) break;
        }
    }

    return answer;
}

ACGTのindexを保存し、A -> C -> G -> Tの順にforがドアの周りに存在し、answerに入れてbreakを行う.
合格しましたが、AAAAAAAAAAAA~Tこのように最後がT、P, Qが最後の文字を指す場合、P.size()xS.length()なのでO(N*M)は合格できないかもしれませんが、このようなテストケースはないようです.
3回目の試み
O(N+M)かもしれません.

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    // write your code in C++14 (g++ 6.2.0)

    vector<int> answer;
    int path[4][S.length()] = {0,};

    if(S[0] == 'A') path[0][0] = 1;
    else if(S[0] == 'C') path[1][0] = 1;
    else if(S[0] == 'G') path[2][0] = 1;
    else if(S[0] == 'T') path[3][0] = 1;

    for(int i=1;i<S.length();i++) {
        if(S[i] == 'A') {
            path[0][i] = path[0][i-1]+1;
            path[1][i] = path[1][i-1];
            path[2][i] = path[2][i-1];
            path[3][i] = path[3][i-1];
        }
        else if(S[i] == 'C') {
            path[0][i] = path[0][i-1];
            path[1][i] = path[1][i-1]+1;
            path[2][i] = path[2][i-1];
            path[3][i] = path[3][i-1];
        }
        else if(S[i] == 'G') {
            path[0][i] = path[0][i-1];
            path[1][i] = path[1][i-1];
            path[2][i] = path[2][i-1]+1;
            path[3][i] = path[3][i-1];
        }
        else if(S[i] == 'T') {
            path[0][i] = path[0][i-1];
            path[1][i] = path[1][i-1];
            path[2][i] = path[2][i-1];
            path[3][i] = path[3][i-1]+1;
        }
    }

    for(int i=0;i<P.size();i++) {
        for(int p=0;p<4;p++) {
            int start = P[i] == 0 ? 0 : path[p][P[i]-1];
            
            // cout << start << " " << path[p][Q[i]] << endl;
            if(path[p][Q[i]] - start > 0) {
                // cout << p << endl;
                answer.push_back(p+1);
                break;
            }
        }
    }

    return answer;
}

ずっと맞왜틀(はい、なぜ間違っているのか)でしたが、接頭辞で解決する方法が思いつかず、参考にして解けました.
まず私の話をする前に、答えを書いてください.例は、問題のCAGCTAを例に挙げます.
最初の文字を確認したら、まず最初の文字を記憶するpath1を1に並べます.
そしてpath[1][0] = 1が保存されます.
そして一字一字確認して、数を数えました.
このようにした結果は以下の通りです.
path[0] = [0, 1, 1, 1, 1, 1, 2]
path[1] = [1, 1, 1, 2, 2, 2, 2]
path[2] = [0, 0, 1, 1, 1, 1, 1]
path[3] = [0, 0, 0, 0, 0, 1, 1]
これはどのように利用しますか.
path[0]を見ると、初めて1番indexに現れ、その後6番indexには現れません.
つまり、2-5の部分配列にはAはありません.
配列のインデックスがp,qの場合,path[0][q]−path[0][p]の値を調べることで個数を求めることができる.
問題の例として、まずP[0] = 2 Q[0] = 4を示す.
2~4つ目はGCCで、Aは存在しないことがわかり、path[0][4]とpath[0][2]はいずれも1に等しい.したがって、0はAがないことを示す.
//iはP、Qは配列index、jはpathは配列index
すなわち,上記の定式化後,path[j][Q[i]] - path[j][P[i]]と計算することができる.
参考として、P[i]が0であればP[i]-1I−1であるため、最初は삼항연산자を用いて処理される.
このようにpath[0]~path[3]を表示し、1つ以上あればその値を保存すればよい.小さい順(A->C->G->T)で確認し、1以上の値が出た場合、直ちにbreakを行うことができます.
次はこの問題を解くときに生じるホットスポットです.
これは時間がかかりすぎたので...時間の複雑さは通過しなかったためかもしれないと考えられています.でも正しいと思う(?)何を言っているのか分かりませんが、他の人の言い方を参考にして、直接cppに変更して、結果は間違っています.
複数のケースでエラーがあることを確認するために、結果ページにエラーのsingleケースが書かれていて、無言です.
(真ん中のstartは上のコードと違い、3つの演算子ではないのは、そこに問題があったのでテストしました.)

上の写真を見ると,['T',[0],[0]のとき,return value3が現れる.
4が表示されるはずなので、coutを使用してデバッグを試みます.
結果は以下の通りです.

??? 突然現れた4...coutしか入っていませんが、なぜか4が出てきました.
理解できなかったため、最終的に「法典」に質問メールを残し、以下のような回答を得た.
Hello,
We have forwarded this to our senior technical team to look into and they will be in touch after reviewing the details.
Kind regards,
Ajas
Codility Support
上級技術チームだけが問題を解決することができますが、突然思いついたのは、一部の企業が消費サービスを使用してコードテストを行っているのに、本当にこのような問題はありませんか?(解かなかったから落ちたのかもしれないけど)

解答と感想

遠い問題が難しくなるにつれて、問題も理解しにくくなりました...(英語が下手なせいか…)ㅠㅠㅠ他人の解答を見ても一度は読めないので、たくさんの解答を見ました...私はどのようにこれをprefixに解いたのか、やはり解決策があります...
いずれにしても、最初はprefixで解決できなかったので、他の方法を試してみましたが、コディリティのミスで時間を無駄にしてしまったので、工夫を凝らした質問でしたㅠㅠ後でコディリティ側から回答があれば、内容を追加します.

コメントサイト

[Codility]GeonomicRangeQuery解答-Cheolhojungのブログ

[断固たる(断固たる)]Lesson 5GenomicRangeQuery(100%)-ジャックコードストーリーブログ