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 ")).

À propos de la dichotomie

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

#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.

#ABC047 C Reversi unidimensionnel

import itertools

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

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

print(ans - 1)

ABC143 D Triangles

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

#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

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

#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')

Recommended Posts

Recommandation de résolution des problèmes d'AtCoder avec python (20200517-0523)
Résolvez AtCoder 167 avec python
Résolvez AtCoder ABC166 avec python
Résoudre les problèmes d'AtCoder Boot camp pour les débutants (moyen 100) avec python
[Python] Résolvez 10 problèmes d'élite passés d'Atcoder
[AtCoder] Résoudre ABC1 ~ 100 Un problème avec Python
Résoudre AtCoder ABC168 avec python (A ~ D)
Résoudre des maths avec Python
Résolvez POJ 2386 avec python
[AtCoder] Résoudre un problème de ABC101 ~ 169 avec Python
Résolvez "AtCoder version! Arimoto (Débutant)" avec Python!
[Python] Résoudre des équations avec sympy
Bleu clair avec AtCoder @Python
Résoudre les problèmes d'optimisation avec Python
solveur> Lien> Résoudre le solveur Excel avec python
Résoudre ABC163 A ~ C avec Python
[Explication AtCoder] Contrôle ABC180 Problèmes A, B, C avec Python!
atCoder 173 Python
Résoudre ABC166 A ~ D avec Python
Résolution avec Ruby et Python AtCoder ABC133 D Somme cumulée
Résoudre Atcoder ABC169 A-D avec Python
Résoudre ABC168 A ~ C avec Python
[Explication AtCoder] Contrôle ABC158 Problèmes A, B, C avec Python!
Résolu AtCoder ABC 114 C-755 avec Python3
Résoudre ABC162 A ~ C avec Python
Résoudre ABC167 A ~ C avec Python
Résoudre ABC158 A ~ C avec Python
[Explication AtCoder] Contrôle ABC164 Problèmes A, B, C avec Python!
[Explication AtCoder] Contrôle ABC168 Problèmes A, B, C avec Python!
AtCoder ARC104 B Somme cumulative résolue en Ruby, Python et Java
Comment écrire hors ligne en temps réel Résolution des problèmes F01 avec Python
Je voulais résoudre ABC160 avec Python
Recommandation d'Altair! Visualisation des données avec Python
Solve Lake Counting (POJ n ° 2386) avec Python3
Je voulais résoudre ABC172 avec Python
FizzBuzz en Python3
Grattage avec Python
[Explication AtCoder] Contrôlez les problèmes A, B, C d'ABC182 avec Python!
Statistiques avec python
Grattage avec Python
Python avec Go
Twilio avec Python
Intégrer avec Python
Jouez avec 2016-Python
Résolvez les problèmes d'optimisation avec le recuit quantique aussi facilement que possible basé sur Python
AES256 avec python
Testé avec Python
python commence par ()
avec syntaxe (Python)
Résolvez AtCoder Débutant Contest 170 D - Non divisible (ABC170D) avec python (tamis Eratostenes)
Bingo avec python
Résolution avec Ruby, Perl, Java et Python AtCoder ABC 047 C Expression régulière
Zundokokiyoshi avec python
AtCoder ABC 175 Python