Solve with Ruby and Python AtCoder ABC133 D Cumulative sum

Introduction

This theme

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

This theme, cumulative sum

It is a problem that solves simultaneous equations and can be found in the lup library of numpy and scipy. However, like a competition pro, it becomes TLE, so it can be solved by transforming the simultaneous equations as follows.

  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

A special cumulative sum that is added or subtracted depending on the index. 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(' ')

It is a solution using lup of the Matrix library, but it is 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(' ')

The solution uses LUSolve, but it is 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()

The solution using the linalg library of numpy is 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()

The solution using the linalg library of scipy is TLE.

Ruby Python
Code length(Byte) 234 382
Execution time(ms) 130 98
memory(KB) 14084 19132

Summary

Referenced site instance method Matrix#lup

Recommended Posts

Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
AtCoder ABC130 D Cumulative Sum Binary Search Solved by Ruby and Python
Solve AtCoder ABC168 with python (A ~ D)
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solve AtCoder ABC166 with python
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
Solve AtCoder ABC 186 with Python
Solving with Ruby, Perl, Java, and Python AtCoder ARC 098 C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
Solve ABC166 A ~ D with Python
Solving with Ruby and Python AtCoder AISING2020 D Iterative Squares
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder 167 with python
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
Solving with Ruby, Perl, Java and Python AtCoder ABC 107 B String Manipulation
Solve ABC175 D in Python
AtCoder ABC 182 Python (A ~ D)
AtCoder ARC080 D simulation solved in Ruby and Python
Solving with Ruby and Python AtCoder ARC 059 C Least Squares
AtCoder ABC155 Problem D Pairs Review Note 2 NumPy and Python
Solve ABC163 A ~ C with Python
Scraping with Node, Ruby and Python
Solve Atcoder ABC169 A-D in Python
Solve AtCoder Problems Recommendation with python (20200517-0523)
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
Solve ABC168 A ~ C with Python
Solved AtCoder ABC 114 C-755 with Python3
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Solve ABC162 A ~ C with Python
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B
Solve ABC167 A ~ C with Python
Solve ABC158 A ~ C with Python
AtCoder ABC168 A case expression solved in Ruby and Python
AtCoder JSC2019 Qual B to solve with Ruby and Python Inverse element of arithmetic progression
I wanted to solve the ABC164 A ~ D problem with Python
ABC 157 D --Solve Friend Suggestions in Python!
I wanted to solve ABC160 with Python
Solve ABC165 A, B, D in Python
Encrypt with Ruby (Rails) and decrypt with Python
Easy web scraping with Python and Ruby
I wanted to solve ABC172 with Python
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization
Solve AtCoder Beginner Contest 170 D --Not Divisible (ABC170D) with python (Eratosthenes sieve)