' P '

whatever I will forget

prefix sum - GenomicRangeQuery

Java algorithm

アルゴリズムの一種で、値のithからjthまでの合計値を効率良く取得するために使用する
ほぼほぼ累積和と変わらないと思っています

参考

codechacha.com

問題

app.codility.com

問題の英語的にはっきり言って一見では何したらいいのか意味不明でしたw

  • 渡されるString Sが、 ACGTのどれかを含むランダムな文字列。
  • 上記の四文字は、A=1, C=2, G=3, T=4と意味がある。
  • Array P、Qの数字（これをSの文字開始列、文字終了列とみなしてよい）の中にACGTが含まれている場合、それに対応する数字(1,2,3,4)を返却せよ

62点のコード

愚直にやるとタイムアウトでMAX62点
log(N * M)だとダメだということです...

import java.util.*;
public class Solution {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution("CAGCCTA", new int[] {2,5,0}, new int[] {4,5,6})));
    }
    public static int[] solution(String S, int[] P, int[] Q) {
        // write your code in Java SE 8
        int[] ans = new int[P.length];
        for(int i=0; i<P.length; i++) {
            if(S.substring(P[i], Q[i]+1).contains("A")) {
                ans[i] = 1;
            } else if(S.substring(P[i], Q[i]+1).contains("C")) {
                ans[i] = 2;
            } else if(S.substring(P[i], Q[i]+1).contains("G")) {
                ans[i] = 3;
            } else {
                ans[i] = 4;
            }
        }

        return ans;
    }
}

100点のコード

累積和を使う.
Sの1文字1文字の中で登場するA,C,Gがする累積和を求めておく.
その後、Q-Pの範囲での総和を求めればよいということになります.
さすが、累積和！log(N + M)となります!

qiita.com

import java.util.*;
public class Solution {
    public static void main(String[] args) {
        //System.out.println(Arrays.toString(solution("CAGCCTA", new int[] {2,5,0}, new int[] {4,5,6})));
        System.out.println(Arrays.toString(solution("AC", new int[] {0,0,1}, new int[] {0,1,1})));
    }

    public static int[] solution(String S, int[] P, int[] Q) {
        int[] A = new int[S.length()+1];
        int[] C = new int[S.length()+1];
        int[] G = new int[S.length()+1];

        for(int i=0; i<S.length(); i++) {
            int a,c,g;
            a = c = g = 0;
            if(S.charAt(i) == 'A') {
                a = 1;
            }
            if(S.charAt(i) == 'C') {
                c = 1;
            }
            if(S.charAt(i) == 'G') {
                g = 1;
            }
            A[i+1] = A[i] + a;
            C[i+1] = C[i] + c;
            G[i+1] = G[i] + g;
        }

        int[] ans = new int[P.length];
        for(int i=0; i<P.length; i++) {
            if(A[Q[i]+1] - A[P[i]] > 0) {
                ans[i] = 1;
            } else if(C[Q[i]+1] - C[P[i]] > 0) {
                ans[i] = 2;
            } else if(G[Q[i]+1] - G[P[i]] > 0) {
                ans[i] = 3;
            } else {
                ans[i] = 4;
            }
        }
        return ans;
    }
}