Recommandation de résolution des problèmes d'AtCoder avec python (20200517-0523)

Liste des problèmes répertoriés dans cet article

1. AGC057 A Shik and Stone
2. ABC070 C Multiple Clocks
3. ABC123 C Five Transportations
4. AGC008 A Simple Calculator
5. [ARC059 C ensemble](# arc059-c-avec)
6. [ABC047 C Inversion unidimensionnellei](# abc047-c-Inversion unidimensionnellei)
7. ABC143 D Triangles
8. [Drone ABC035 B](# abc035-b-Drone)
9. AGC011 A Airport Bus
10. AGC002 B Box and Ball
11. ABC078 C HSI
12. [ARC054 A Moving Trail](# arc054-a-Moving Trail)
13. ABC065 C Reconciled?
14. [Concours de programmation Panasonic 2020 C Sqrt Inequality](#Panasonic Programming Contest 2020-c-sqrt-inégality)

Ce que j'ai appris en résolvant le problème ci-dessus

À propos de réduire

--reduce est la convolution --Un type de fonction d'ordre supérieur --Une fonction d'ordre supérieur est une fonction qui prend une fonction comme argument (ci-dessous est un exemple de fonction d'ordre supérieur).

1. map (exécuter une fonction sur chaque itérateur et la renvoyer sur l'itérateur)
2. filter (seul le résultat de l'exécution de la fonction pour chaque itérateur est True est retourné par l'itérateur)) --Utilisé sous la forme de reduction (function, iterater, initializer (option)) --Exécute function à l'itérateur dans l'ordre et renvoie le résultat

A propos de l'arrondissement des chiffres

―― Chez les professionnels de la compétition, l'arrondissement des chiffres donne parfois une apparence correcte en tant que code, mais il y a des cas où il devient WA (5 et 14. ci-dessus). --Arrondir Il y a des cas où l'utilisation de round () est inutile, alors utilisez (<num> * 2 + 1) // 2. --Racine Il y a des cas où l'utilisation de math.sqrt () est inutile, alors utilisez <num> ** (decimal (" 0.5 ")).

• 1: from Decimal import decimal est requis.
• 2: L'argument de «décimal» est donné sous forme de chaîne de caractères (s'il est donné sous forme de valeur numérique, une erreur d'arrondi se produira à ce stade).

À propos de la dichotomie

• Lors de la recherche de valeurs dans une liste triée, il est préférable (souvent) de faire une dichotomie plutôt qu'une recherche linéaire. --Il peut être utilisé sous la forme <idx> = bisect.bisect_left (<liste>, <valeur>).

• ʻImport bisect` est obligatoire

En utilisant la dichotomie, le montant du calcul peut être réduit de $ O (n) $ à $ O (\ log n) $ par rapport à la recherche linéaire.

Comment résoudre chaque problème

AGC057 A Shik and Stone

--Temps requis: moins de 10 minutes --Point: Au début, je pensais que j'utiliserais collections.counter, mais si je voulais juste compter le nombre de #, je sentais que count () ʻof `était suffisant, alors j'ai changé pour cela. Et mettre en œuvre

# AGC057 A Shik and Stone

h,w = map(int, input().split())

_list = []
for i in range(h):
    _list += list(input())

if _list.count("#") == (h+w-1):
    print("Possible")
else:
    print("Impossible")

ABC070 C Multiple Clocks --Temps requis: 11 minutes --Point: Je me suis rapidement rendu compte que la recherche de LCM posait un problème, alors j'ai cherché sur Google comment implémenter LCM. Le temps nécessaire pour étudier «réduire» n'est pas inclus dans le temps requis.

# ABC070 C Multiple Clocks

from functools import reduce
from fractions import gcd #python3.Avant 5
# from math import gcd      #python3,5 ou plus tard

def lcm_base(x,y):
    return (x*y)//gcd(x,y)

def multi_lcm(numbers):
    return reduce(lcm_base, numbers)

n = int(input())
t_list = [int(input()) for i in range(n)]

print(multi_lcm(t_list))

ABC123 C Five Transportations --Temps requis: -minutes --Point: Vous pouvez comprendre en écrivant un exemple sur papier

# ABC123 C Five Transportations
import math

n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

_min = min([a,b,c,d,e])
_ans = math.ceil(n/_min)

print(_ans+4)

AGC008 A Simple Calculator Impressions C'est facile à voir, mais il y a étonnamment de nombreux motifs (peut-être que cela peut être rendu plus beau). `` J'ai obtenu WA deux fois parce que j'ai fait une division de motif approximative lorsque l'un d'eux était égal à 0.

# AGC008 A Simple Calculator

x, y = map(int, input().split())
_x = abs(x)
_y = abs(y)

if x > 0 and y > 0:
    if x <= y:
        print(y-x)
    else:
        print(x-y+2)
elif x * y < 0:
    print(abs(_y-_x)+1)
elif x == 0:
    if y >= 0:
        print(y)
    else:
        print(_y+1)
elif y == 0:
    if x > 0:
        print(x+1)
    else:
        print(_x)
else:
    if _x < _y:
        print(_y-_x+2)
    else:
        print(_x-_y)

ARC059 C ensemble

Impressions

• Le problème lui-même est simple. Il ne semblait y avoir aucun problème à calculer le montant du calcul pour tous les éléments un par un, donc il n'y a pas de problème là non plus.
• Comme il y a des cas où l'arrondi n'est pas correct avec round (), l'arrondi se fait avec (<num> * 2 + 1 // 2). (Pourquoi round () n'est pas arrondi correctement est omis ici)

#ARC059 C ensemble

n = int(input())
a_list = [int(x) for x in input().split()]

ave = ((sum(a_list) / len(a_list)) * 2 + 1) // 2

ans = sum([(x-ave)**2 for x in a_list])

print(int(ans))

ABC047 C Reversi unidimensionnel

Impressions ――C'est un moment où ʻitertools.groupby () `apparaît.

• Cependant, il semble qu'il n'y ait aucun moyen d'obtenir le nombre d'éléments de l'itérateur, il est donc nécessaire d'utiliser l'itérateur comme le programme ci-dessous.

#ABC047 C Reversi unidimensionnel

import itertools

s = itertools.groupby(list(input()))

ans = 0
for _ in s:
    ans += 1

print(ans - 1)

ABC143 D Triangles

• Partie 1 «J'ai essayé de le résoudre avec une recherche complète, mais il s'est avéré être TLE. --Partie 2 --Utilisez une dichotomie («bisect»)

En utilisant le second, le montant du calcul peut être réduit de $ O (n ^ {3}) $ à $ O (n ^ {2} \ log n) $.

Partie 1

# ABC143 D Triangles TLE

n = int(input())
l_list = [int(x) for x in input().split()]

l_list.sort()
ans = 0

# (i < j < k) -> (_a < _b < _c)
for i in range(n-2):
    _a = l_list[i]
    for j in range(i+1,n-1):
        _b = l_list[j]
        _tmp = _a + _b
        for k in range(j+1,n):
            _c = l_list[k]
            if _c < _tmp:
                ans += 1
            else:
                break

print(ans)

Partie 2

# ABC143 D Triangles

import bisect

n = int(input())
l_list = [int(x) for x in input().split()]

l_list.sort()
ans = 0

for i in range(n-2):
    _a = l_list[i]
    for j in range(i+1,n-1):
        _b = l_list[j]
        _tmp = bisect.bisect_left(l_list, _a+_b)
        if j < _tmp:
            ans += _tmp - j - 1

print(ans)

Drone ABC035 B

• Vous pouvez le résoudre immédiatement en utilisant Counter ().

#Drone ABC035 B
from collections import Counter

s = Counter(input())
t = int(input())

l = s["L"]
r = s["R"]
u = s["U"]
d = s["D"]
q = s["?"]

x = r-l
y = u-d

if t == 1:
    print(abs(x) + abs(y) + q)
else:
    _tmp = abs(x) + abs(y)
    if _tmp >= q:
        print(_tmp - q)
    elif (_tmp - q) % 2 == 0:
        print("0")
    else:
        print("1")

AGC011 A Airport Bus

• Partie 1 «Au début, je pensais qu'il suffirait d'utiliser« bisect () »(dichotomie), mais c'est devenu TLE. --Partie 2
• Comme il existe de nombreux processus pour obtenir des données depuis le début de la liste, j'ai essayé d'utiliser deque et cela a réussi.

J'ai réaffirmé que si j'obtiens des données du haut de la liste, elles devraient être mises en file d'attente.

Partie 1

# AGC011 A Airport Bus TLE
import bisect

n, c, k = map(int, input().split())
t_list = [int(input()) for _ in range(n)]

t_list.sort()
ans = 0

while len(t_list) > 0:
    _tmp = t_list[0] + k
    _idx = bisect.bisect_right(t_list, _tmp)
    if c <= _idx + 1:
        t_list = t_list[c:]
    else:
        t_list = t_list[_idx:]
    ans += 1

print(ans)

Partie 2

# AGC011 A Airport Bus
import bisect
from collections import deque

n, c, k = map(int, input().split())
t_list = [int(input()) for _ in range(n)]

t_list.sort()
t_list = deque(t_list)
ans = 0

while len(t_list) > 0:
    _tmp = t_list.popleft() + k
    _idx = bisect.bisect_right(t_list, _tmp)
    if c-1 <= _idx:
        for _ in range(c-1):
            t_list.popleft()
    else:
        for _ in range(_idx-1):
            t_list.popleft()
    ans += 1

print(ans)

AGC002 B Box and Ball

# AGC002 B Box and Ball

n, m = map(int, input().split())

b_list = [0] * (n+1)
b_list[1] = 1
c_list = [1] * (n+1)

for i in range(m):
    _x, _y = map(int, input().split())
    c_list[_x] -= 1
    c_list[_y] += 1 
    if b_list[_x] == 1:
        b_list[_y] = 1
        if c_list[_x] == 0:
            b_list[_x] = 0

print(sum(b_list))

ABC078 C HSI

# ABC078 C HSI

n, m = map(int, input().split())

i = (1/2)**m

x = (100*(n-m) + 1900*m) / i
print(int(x))

ARC054 Un trottoir mobile

#ARC054 Un trottoir mobile

l, x, y, s, d = map(int, input().split())

ans = float("Inf")
j = (d-s)%l
r = (s-d)%l
ans = min(ans,j/(y+x))
if y > x:
    ans = min(ans,r/(y-x))
print(ans)

ABC065 C Reconciled?

# ABC065 C Reconciled?

import math

n, m = map(int, input().split())
A = 10**9 + 7

if abs(n-m) > 1:
    print("0")
elif n == m:
    print(((math.factorial(m)**2)*2)%A)
else:
    print((math.factorial(m)*math.factorial(n))%A)

Concours de programmation Panasonic 2020 C Sqrt Inequality

• Partie 1 --Si vous utilisez math.sqrt (), les chiffres peuvent être arrondis et vous pouvez obtenir NG. --Partie 2
• Vous pouvez calculer correctement en utilisant decimal.Decimal ().

Partie 1

#Concours de programmation Panasonic 2020 C Sqrt Inequality WA
import math
from decimal import Decimal

a, b, c = map(Decimal, input().split())
_a, _b, _c = map(math.sqrt, [a,b,c])

if _a + _b < _c:
    print("Yes")
else:
    print("No")

Partie 2

#Concours de programmation Panasonic 2020 C Sqrt Inequality
from decimal import Decimal

a, b, c = map(int,input().split())
a, b, c = Decimal(a),Decimal(b),Decimal(c)
if a**Decimal("0.5") + b**Decimal("0.5") < c**Decimal("0.5"): 
    print('Yes')
else:
    print('No')