AtCoder ARC104 B Kumulative Summe in Ruby, Python und Java gelöst

Einführung

• AtCoder-Probleme * Verwendet Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

AtCoder Regular Contest B - DNA Sequence Difficulty: 410

Dieses Thema, kumulative Summe

Dies ist ein kumulatives Summenproblem, aber dieses Mal benötigen wir vier kumulative Summen von 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

Ich habe die Idee von @scivola im Kommentarbereich reflektiert.

ruiseki.rb

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

Beim Erstellen eines kumulativen Arrays können Sie auch zuerst die erforderliche Anzahl von Elementen vorbereiten. Dieses Mal habe ich das letzte Element mit "[-1]" aufgerufen und hinzugefügt.

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

Wenn die Anzahl der Elemente von "A" C "G" T "im Intervall gleich ist, kann dies als" komplementär "beurteilt werden. 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" ist eine andere Lösung. Mit dieser Lösung wird es zu "TLE" in "Python" und "Ruby".

banpei.py

    s = 'N' + s + 'N'

Es gibt Wachen vor und nach der Schnur. Es wird für die Bedingung "Pause" mit "während" verwendet.

hiroge.py

            i -= 1
            j += 1

Wir überprüfen die Nummer, indem wir den Bereich an jeder Zeichenposition erweitern 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" ist die gleiche Lösung wie "Pypy". Ich habe die Idee von @ c-yan im Kommentarbereich reflektiert.

i.java

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

Im Gegensatz zu "Python" und "Ruby" wirkt sich die Zuweisung zu einer Schleifenvariablen in einem Block auf die nächste Schleifenvariable aus, sodass Sie sie einer anderen Variablen zuweisen.

Zusammenfassung

• Gelöster ARC 104 D.
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Python vertraut
• Machen Sie sich mit Java vertraut