Codility – Lesson 5 Prefix Sums – GenomicRangeQuery
プログラミング能力を評価するオンラインテスト、Codilityで、Lesson 5 Prefix Sums – GenomicRangeQueryに回答しました。
問題と結果画面
62%の評価。
almost_all_same_letters : NG
large_random : NG
extreme_large : NG
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
using System; class Solution { public int[] solution(string S, int[] P, int[] Q) { if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length || P.Length != Q.Length) throw new InvalidOperationException(); int[] result = new int[P.Length]; char[] dna = S.ToCharArray(); int[] impact = new int[dna.Length]; for(int i = 0; i < dna.Length; i++) { switch(dna[i]) { case 'A': impact[i] = 1; break; case 'C': impact[i] = 2; break; case 'G': impact[i] = 3; break; case 'T': impact[i] = 4; break; default: impact[i] = 0; break; } } for(int i = 0; i < P.Length; i++) { int value = 10; for(int K = P[i]; K <= Q[i]; K++) { if(impact[K] < value) value = impact[K]; } result[i] = value; } return result; } } |
問題と結果画面
75%の評価。
almost_all_same_letters : NG
large_random : OK
extreme_large : NG
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
using System; using System.Linq; class Solution { public int[] solution(string S, int[] P, int[] Q) { int[] result = new int[P.Length]; S = S.Replace('A','1'); S = S.Replace('C','2'); S = S.Replace('G','3'); // S = S.Replace('T','4'); int[] impact = S.Select(a => a - '0').ToArray(); for(int i = 0; i < P.Length; i++) { int value = 4; for(int K = P[i]; K <= Q[i]; K++) { // Console.WriteLine("impact[K] : " + impact[K]); if(impact[K] == 36) continue; if(impact[K] < value) value = impact[K]; if(impact[K] == 1) break; } result[i] = value; } return result; } } |
問題と結果画面
75%の評価。
almost_all_same_letters : NG
large_random : OK
extreme_large : NG
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
using System; using System.Linq; class Solution { public int[] solution(string S, int[] P, int[] Q) { int[] result = new int[P.Length]; S = S.Replace('A','1'); S = S.Replace('C','2'); S = S.Replace('G','3'); int[] impact = S.Select(a => a - '0').ToArray(); for(int i = 0; i < P.Length; i++) { int value = 4; bool isFound = false; for (int j = 1; j < 4; j++) { for(int K = P[i]; K <= Q[i]; K++) { if(impact[K] == j) { value = j; isFound = true; break; } } if(isFound) break; } result[i] = value; } return result; } } |
問題と結果画面
75%の評価。
almost_all_same_letters : NG
large_random : OK
extreme_large : NG
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
using System; using System.Linq; class Solution { public int[] solution(string S, int[] P, int[] Q) { int[] result = new int[P.Length]; S = S.Replace('A','1'); S = S.Replace('C','2'); S = S.Replace('G','3'); int[] impact = S.Select(a => a - '0').ToArray(); int[] count = new int[3]; count[0] = impact.Count(x => x == 1); count[1] = impact.Count(x => x == 2); count[2] = impact.Count(x => x == 3); for(int i = 0; i < P.Length; i++) { int value = 4; bool isFound = false; for (int j = 1; j < 4; j++) { if(count[j-1] == 0) continue; for(int K = P[i]; K <= Q[i]; K++) { if(impact[K] == j) { value = j; isFound = true; break; } } if(isFound) break; } result[i] = value; } return result; } } |
問題と結果画面
75%の評価。
パフォーマンスが0.4-5秒及ばず。
almost_all_same_letters : NG
large_random : NG
extreme_large : OK
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
using System; using System.Collections.Generic; using System.Linq; class Solution { public int[] solution(string S, int[] P, int[] Q) { int[] result = new int[P.Length]; char[] arr = S.ToCharArray(); List<List<int>> multi = new List<List<int>>(); multi.Add(new List<int>()); multi.Add(new List<int>()); multi.Add(new List<int>()); int len = arr.Length; for(int i = 0; i < len; i++) { if(arr[i] == 'T') continue; else if(arr[i] == 'A') multi[0].Add(i); else if(arr[i] == 'C') multi[1].Add(i); else multi[2].Add(i); } len = P.Length; for(int i = 0; i < len; i++) { int val = 4; bool found = false; int p = P[i]; int q = Q[i]; for (int j = 0; j < 3; j++) { int cnt = multi[j].Count; for(int k = 0; k < cnt; k++) { int pos = multi[j][k]; if(p <= pos && pos <= q) { val = j + 1; found = true; break; } } if(found) break; } result[i] = val; } return result; } } |
100%になっていないけれど、いったん保留。あとでまた考える。
