AtCoder JSC2019 Qual B à résoudre par Ruby et Python

introduction

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

Ce thème

AtCoder JSC2019 Qual B - Kleene Inversion Difficulty: 797

Ce thème, somme de la séquence d'égalité + élément inverse Ruby Je n'ai jamais entendu parler de «chutes», mais voyons de quel genre de «chutes» ce sera par exemple «1 3 2».

Un «1 3 2» est «1», deux côte à côte «1 3 2 1 3 2» sont «4 + 1», et trois sont alignés «1 3 2 1 3 2 1 3 2» est «7 Vous pouvez voir que c'est la somme de + 4 + 1` et la séquence d'égalité. Pour la formule de la somme de la séquence d'égalité, reportez-vous à * here *.

ruby.rb

n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = a + a
c = 0
(a.size - 1).times do |i|
  (i + 1).upto(a.size - 1) do |j|
    c += 1 if a[i] > a[j]
  end
end
d = 0
(b.size - 1).times do |i|
  (i + 1).upto(b.size - 1) do |j|
    d += 1 if b[i] > b[j]
  end
end
d -= c * 2
def modpow(n, p, mod)
  r = 1
  while p > 0
    r = r * n % mod if p & 1 == 1;
    n = n * n % mod
    p >>= 1
  end
  r
end
def modinv(n, mod)
  modpow(n, mod - 2, mod)
end
MOD = 1_000_000_007
ans = (k - 1) * d % MOD
ans += 2 * c
ans %= MOD
ans *= k
ans %= MOD
ans *= modinv(2, MOD)
ans %= MOD
puts ans

cal.rb

c = 0
(a.size - 1).times do |i|
  (i + 1).upto(a.size - 1) do |j|
    c += 1 if a[i] > a[j]
  end
end
d = 0
(b.size - 1).times do |i|
  (i + 1).upto(b.size - 1) do |j|
    d += 1 if b[i] > b[j]
  end
end
d -= c * 2

Le premier terme «c» et la tolérance «d» sont calculés ici.

wa.rb

ans = (k - 1) * d % MOD
ans += 2 * c
ans %= MOD
ans *= k
ans %= MOD
ans *= modinv(2, MOD)
ans %= MOD

C'est la partie officielle de la somme de la séquence d'égalité, mais comme il y a une division par «2», il est nécessaire de trouver l'élément inverse. Python

python.py

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = a + a
c = 0
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] > a[j]:
            c += 1
d = 0
for i in range(len(b)):
    for j in range(i + 1, len(b)):
        if b[i] > b[j]:
            d += 1
d -= c * 2
def modpow(n, p, mod):
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
def modinv(n, mod):
    return modpow(n, mod - 2, mod)
MOD = 10 ** 9 + 7
ans = (k - 1) * d % MOD
ans += 2 * c
ans %= MOD
ans *= k
ans %= MOD
ans *= modinv(2, MOD)
ans %= MOD
print(ans)

Même avec PyPy3 (2.4.0), il pourrait être utilisé tel quel.

Résumé

• Résolu JSC2019 Qual B
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python

Site référencé

• Somme de 4 différences égales *