Résolution avec Ruby et Python AtCoder ABC133 D Somme cumulée

introduction

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

Ce thème

AtCoder Beginner Contest D - Rain Flows into Dams Difficulty: 945

Ce thème, somme cumulée

C'est un problème pour résoudre des équations simultanées et peut être trouvé dans la «bibliothèque lup» de «numpy» et «scipy». Cependant, comme un pro de la concurrence, ce sera "TLE", donc il peut être résolu en transformant les équations simultanées comme suit.

  b1 + b2 = a1
  b2 + b3 = a2
  b3 + b1 = a3

  b1 =  a1 + -a2 +  a3
  b2 =  a1 +  a2 + -a3
  b3 = -a1 +  a2 +  a3

  b2 = a1 - a2 + a3
     = 2 * a1 - (a1 + a2 - a3)
     = 2 * a1 - b1

Ruby (AC)

ruby.rb

n = gets.to_i
a = gets.split.map(&:to_i)
ans = [0] * n
a.each_with_index do |x, i|
  if i.even?
    ans[0] += x
  else
    ans[0] -= x
  end
end
1.upto(n - 1) do |i|
  ans[i] = 2 * a[i - 1] - ans[i - 1]
end
puts ans * ' '

rui.rb

a.each_with_index do |x, i|
  if i.even?
    ans[0] += x
  else
    ans[0] -= x
  end
end

Une somme cumulative spéciale qui est ajoutée ou soustraite en fonction de l'indice. Ruby Matrix(TLE)

TLE.rb

require 'matrix'

n = gets.to_i
a = gets.split.map(&:to_i)
b = []
n.pred.times do |i|
  b[i] = [0] * i + [1] * 2 + [0] * (n - i - 2)
end
b << [1] + [0] * (n - 2) + [1]
m = Matrix.rows(b).lup.solve(a)
puts (m * 2).to_a.map{|e| e.to_i}.join(' ')

C'est une solution utilisant «lup» de la bibliothèque «Matrix», mais c'est «TLE». Ruby BigDecimal(TLE)

TLE.rb

require 'bigdecimal'
require 'bigdecimal/util'
require 'bigdecimal/ludcmp'

include LUSolve

n = gets.to_i
a = gets.chomp.split.map(&:to_d)
zero = '0.0'.to_d
one = '1.0'.to_d
b = []
n.pred.times do |i|
  b[i] = [zero] * i + [one] * 2 + [zero] * (n - i - 2)
end
b << [one] + [zero] * (n - 2) + [one]
b.flatten!
x = lusolve(b, a, ludecomp(b, a.size, zero, one), zero)
puts x.map{|e| e.to_i * 2}.join(' ')

La solution utilise «LUSolve», mais c'est «TLE». Python (AC)

python.py

from sys import stdin

def main():
    input = stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    ans = [0] * n
    for i in range(n):
        if i % 2 == 0:
            ans[0] += a[i]
        else:
            ans[0] -= a[i]
    for i in range(1, n):
        ans[i] = 2 * a[i - 1] - ans[i - 1]
    print(' '.join(map(str, ans)))
main()

Python numpy(TLE)

TLE.py

from sys import stdin

def main():
    import numpy as np
    input = stdin.readline

    n = int(input())
    a = [[] for _ in range(n)]
    for i in range(n - 1):
        a[i] = [0] * i + [1, 1] + [0] * (n - i - 2)
    a[n - 1] = [1] + [0] * (n - 2) + [1]
    A = np.array(a)
    b = np.array(list(map(int, input().split())))
    x = np.linalg.solve(A, b) * 2
    print(' '.join(map(str, map(int, x))))
main()

La solution utilisant la «bibliothèque linalg» de «numpy» est «TLE». Python scipy(TLE)

TLE.py

from sys import stdin

def main():
    import numpy as np
    from scipy import linalg
    input = stdin.readline

    n = int(input())
    a = [[] for _ in range(n)]
    for i in range(n - 1):
        a[i] = [0] * i + [1, 1] + [0] * (n - i - 2)
    a[n - 1] = [1] + [0] * (n - 2) + [1]
    A = np.array(a)
    b = np.array(list(map(int, input().split())))
    LU = linalg.lu_factor(A)
    x = linalg.lu_solve(LU, b) * 2
    print(' '.join(map(str, map(int, x))))
main()

La solution utilisant la «bibliothèque linalg» de «scipy» est «TLE».

Résumé

• Résolu ABC 138 D
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python

Site référencé instance method Matrix#lup

• Comprendre les équations linéaires simultanées et la régression multiple linéaire en Python *