AtCoder ARC104 B Somme cumulative résolue en Ruby, Python et Java

introduction

• Utilisez les recommandations dans AtCoder Problems * pour résoudre les problèmes passés. Merci à AtCoder et AtCoder Problems.

Ce thème

AtCoder Regular Contest B - DNA Sequence Difficulty: 410

Ce thème, somme cumulée

C'est un problème de somme cumulative, mais cette fois nous avons besoin de quatre sommes cumulées de ʻ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

J'ai reflété l'idée de @scivola dans la section commentaires.

ruiseki.rb

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

Lors de la création d'un tableau cumulatif, vous pouvez également préparer d'abord le nombre d'éléments requis. Cette fois, j'ai appelé l'élément final avec [-1] et je l'ai ajouté.

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

Si le nombre d'éléments de "A" C "G" T` dans l'intervalle est le même, il peut être jugé "complémentaire". 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 est une autre solution. Avec cette solution, il devient «TLE» en «Python» et «Ruby».

banpei.py

    s = 'N' + s + 'N'

Il y a des gardes avant et après la corde. Il est utilisé pour la condition de "break" with "while".

hiroge.py

            i -= 1
            j += 1

Nous vérifions le nombre en élargissant la plage à chaque position de caractère 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» est la même solution que «Pypy». J'ai reflété l'idée de @ c-yan dans la section des commentaires.

i.java

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

Contrairement à Python et Ruby, si vous affectez à une variable de boucle dans un bloc, cela affectera la variable de boucle suivante, vous l'assignez donc à une autre variable.

Résumé

• ARC 104 D résolu
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python
• Familiarisez-vous avec Java