Beheben von AtCoder-Problemen Empfehlung mit Python (20200517-0523)

Liste der in diesem Artikel aufgeführten Probleme

1. AGC057 A Shik and Stone
2. ABC070 C Multiple Clocks
3. ABC123 C Five Transportations
4. AGC008 A Simple Calculator
5. [ARC059 C zusammen](# arc059-c-with)
6. [ABC047 C eindimensionale Umkehrung](# abc047-c-eindimensionale Umkehrung)
7. ABC143 D Triangles
8. [ABC035 B-Drohne](# abc035-b-Drohne)
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. [Panasonic Programming Contest 2020 C Sqrt Ungleichung](#Panasonic Programming Contest 2020-c-sqrt-Ungleichung)

Was ich bei der Lösung des oben genannten Problems gelernt habe

Über reduzieren

• Reduzieren ist Faltung
• Eine Art Funktion höherer Ordnung
• Eine Funktion höherer Ordnung ist eine Funktion, die eine Funktion als Argument verwendet (unten ein Beispiel für eine Funktion höherer Ordnung).

1. map (führe eine Funktion auf jedem Iterator aus und gib sie auf dem Iterator zurück)
2. filter (nur das Ergebnis der Ausführung der Funktion für jeden Iterator ist True wird vom Iterator zurückgegeben))

• Wird in Form von "Reduzieren (Funktion, Iterator, Initialisierer (Option))" verwendet
• Führen Sie die Funktion in der angegebenen Reihenfolge an den Iterator aus und geben Sie das Ergebnis zurück

Über das Runden von Ziffern

――In Wettkampfprofis sieht die Rundung der Ziffern manchmal als Code korrekt aus, aber es gibt Fälle, in denen es zu WA wird (5 und 14. oben).

• Runden Es gibt Fälle, in denen die Verwendung von "round ()" nutzlos ist. Verwenden Sie daher "( * 2 + 1) // 2". --Wurzel Es gibt Fälle, in denen die Verwendung von "math.sqrt ()" nutzlos ist. Verwenden Sie daher " ** (decimal (" 0.5 "))".

• 1: from Decimal import decimal ist erforderlich.
• 2: Das Argument "dezimal" wird als Zeichenfolge angegeben (wenn es als numerischer Wert angegeben wird, tritt an dieser Stelle ein Rundungsfehler auf).

Über Dichotomie

--Wenn Sie nach Werten aus einer sortierten Liste suchen, ist es (häufig) besser, eine Dichotomie als eine lineare Suche durchzuführen.

• Es kann in Form von " = bisect.bisect_left (, )" verwendet werden.

• Import halbiert ist erforderlich

Durch Verwendung der Dichotomie kann der Rechenaufwand im Vergleich zur linearen Suche von $ O (n) $ auf $ O (\ log n) $ reduziert werden.

Wie man jedes Problem löst

AGC057 A Shik and Stone

• Erforderliche Zeit: weniger als 10 Minuten --Point: Zuerst dachte ich, ich würde "collection.counter" verwenden, aber wenn ich nur die Anzahl von "#" zählen wollte, fand ich, dass "count ()" von "" ausreicht, also habe ich das geändert. Und umsetzen

# 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

• Erforderliche Zeit: 11 Minuten --Point: Ich habe schnell erkannt, dass es ein Problem ist, LCM zu finden, und habe gegoogelt, wie LCM implementiert wird. Die für das Studium "Reduzieren" erforderliche Zeit ist nicht in der erforderlichen Zeit enthalten.

# ABC070 C Multiple Clocks

from functools import reduce
from fractions import gcd #python3.Vor 5
# from math import gcd      #python3,5 oder später

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 --Zeit erforderlich: -minutes --Point: Sie können verstehen, indem Sie ein Beispiel auf Papier schreiben

# 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 Impressionen ――Es ist leicht zu sehen, aber es gibt überraschend viele Muster (vielleicht kann es schöner gemacht werden). ――Ich habe zweimal WA bekommen, weil ich eine grobe Musterteilung durchgeführt habe, als einer von beiden 0 war.

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

Impressionen

• Das Problem selbst ist einfach. Es schien kein Problem zu geben, den Rechenaufwand für alle Elemente einzeln zu berechnen, daher gibt es auch dort kein Problem.
• Da es Fälle gibt, in denen die Rundung mit "round ()" nicht korrekt ist, erfolgt die Rundung mit "( * 2 + 1 // 2)". (Warum "round ()" nicht richtig gerundet ist, wird hier weggelassen.)

#ARC059 C zusammen

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 Eindimensionale Umkehrung

Impressionen

• Wenn Sie an "itertools.groupby ()" denken, ist es ein Moment.
• Es scheint jedoch keine Möglichkeit zu geben, die Anzahl der Elemente des Iterators zu ermitteln. Daher muss der Iterator wie im folgenden Programm verwendet werden.

#ABC047 C Eindimensionale Umkehrung

import itertools

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

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

print(ans - 1)

ABC143 D Triangles

• Teil 1 ――Ich habe versucht, es mit einer vollständigen Suche zu lösen, aber es stellte sich heraus, dass es TLE war. --Teil 2 --Verwenden Sie eine Dichotomie (Bisect).

Mit der zweiten Option kann der Rechenaufwand von $ O (n ^ {3}) $ auf $ O (n ^ {2} \ log n) $ reduziert werden.

Teil 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)

Teil 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)

ABC035 B Drohne

• Sie können es sofort mit Counter () lösen.

#ABC035 B Drohne
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

• Teil 1 ―― Zuerst dachte ich, es würde ausreichen, bisect () (Dichotomie) zu verwenden, aber es wurde TLE. --Teil 2
• Da es viele Prozesse gibt, um Daten vom Anfang der Liste abzurufen, habe ich versucht, "deque" zu verwenden, und es hat bestanden.

Ich habe erneut bestätigt, dass Daten, die oben in der Liste stehen, in die Warteschlange gestellt werden sollten.

Teil 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)

Teil 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 Ein beweglicher Bürgersteig

#ARC054 Ein beweglicher Bürgersteig

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)

Panasonic Programmierwettbewerb 2020 C Sqrt Ungleichung

• Teil 1
• Wenn Sie math.sqrt () verwenden, können die Ziffern gerundet sein und Sie erhalten möglicherweise NG. --Teil 2
• Sie können korrekt mit decimal.Decimal () berechnen.

Teil 1

#Panasonic Programmierwettbewerb 2020 C Sqrt Ungleichung 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")

Teil 2

#Panasonic Programmierwettbewerb 2020 C Sqrt Ungleichung
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')