Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum

Introduction

• AtCoder Problems * Use Recommendations to solve past problems. Thanks to AtCoder and AtCoder Problems.

This theme

AtCoder Regular Contest B - DNA Sequence Difficulty: 410

This theme, cumulative sum

This is a cumulative sum problem, but this time we need four cumulative sums of ʻA C G`` T`. Ruby

ruby.rb

n, s = gets.chomp.split
n = n.to_i
a = [0]
c = [0]
g = [0]
t = [0]
n.times do |i|
  a << a[-1]
  c << c[-1]
  g << g[-1]
  t << t[-1]
  if s[i] == 'A'
    a[i + 1] += 1
  elsif s[i] == 'C'
    c[i + 1] += 1
  elsif s[i] == 'G'
    g[i + 1] += 1
  elsif s[i] == 'T'
    t[i + 1] += 1
  end
end
cnt = 0
n.times do |i|
  at = a[i] - t[i]
  cg = c[i] - g[i]
  (i.next).upto(n) do |j|
    cnt += 1 if a[j] - t[j] == at && c[j] - g[j] == cg
  end
end
puts cnt

I have reflected the idea of @scivola in the comment section.

ruiseki.rb

  a << a[-1]
  c << c[-1]
  g << g[-1]
  t << t[-1]

When creating a cumulative array, you can also prepare the required number of elements first. This time, I called the final element with [-1] and added it.

hantei.rb

  at = a[i] - t[i]
  cg = c[i] - g[i]
  (i.next).upto(n) do |j|
    cnt += 1 if a[j] - t[j] == at && c[j] - g[j] == cg
  end

If the number of elements of ʻA C G`` Tin the interval is the same, it can be judged ascomplementary`. Python

pypy.py

from sys import stdin

def main():
    input = stdin.readline
    n, s = input().split()
    n = int(n)
    s = 'N' + s + 'N'
    cnt = 0
    for i in range(1, n + 2):
        a = 0
        c = 0
        g = 0
        t = 0
        j = i + 1
        while True:
            if s[i] == 'A':
                a += 1
            elif s[i] == 'C':
                c += 1
            elif s[i] == 'G':
                g += 1
            elif s[i] == 'T':
                t += 1
            else:
                break
            if s[j] == 'A':
                a += 1
            elif s[j] == 'C':
                c += 1
            elif s[j] == 'G':
                g += 1
            elif s[j] == 'T':
                t += 1
            else:
                break
            if a == t and c == g:
                cnt += 1
            i -= 1
            j += 1
    print(cnt)
main()

pypy is another solution. With this solution, it becomes TLE in Python and Ruby.

banpei.py

    s = 'N' + s + 'N'

There are sentinels before and after the string. It is used for the condition of break with while.

hiroge.py

            i -= 1
            j += 1

We expand the range at each character position and check the number Java

java.java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        String s = "N" + sc.next() + "N";
        sc.close();

        int cnt = 0;
        for (int k = 1; k < n+2; k++) {
            int i = k;
            int j = k + 1;
            int gn = 0;
            int cn = 0;
            int tn = 0;
            int an = 0;
            while (true) {
                if (s.charAt(i) == 'A') {
                    an++;
                } else if (s.charAt(i) == 'C') {
                    cn++;
                } else if (s.charAt(i) == 'G') {
                    gn++;
                } else if (s.charAt(i) == 'T') {
                    tn++;
                } else {
                    break;
                }
                if (s.charAt(j) == 'A') {
                    an++;
                } else if (s.charAt(j) == 'C') {
                    cn++;
                } else if (s.charAt(j) == 'G') {
                    gn++;
                } else if (s.charAt(j) == 'T') {
                    tn++;
                } else {
                    break;
                }
                if (an == tn && cn == gn) {
                    cnt++;
                }
                i--;
                j++;
            }
        }
        System.out.println(cnt);
    }
}

Java is the same solution as Pypy. I have reflected the idea of @ c-yan in the comment section.

i.java

        for (int k = 1; k < n+2; k++) {
            int i = k;

Unlike Python and Ruby, if you assign to a loop variable in a block, it will affect the next loop variable, so you assign it to another variable.

Summary

• Solved ARC 104 D
• Become familiar with Ruby
• Become familiar with Python
• Become familiar with Java