[PYTHON] AtCoder Beginner Contest 168 Teilnahmebericht

AtCoder Beginner Contest 168 Teilnahmebericht

Es ist das erste Mal, dass ich 700 geschnitten habe, also mag ich es nicht !!

ABC168A - ∴ (Therefore)

Brechen Sie in 2 Minuten durch. Schreiben Sie einfach.

N = int(input())

if N % 10 in [2, 4, 5, 7, 9]:
    print('hon')
elif N % 10 in [0, 1, 6, 8]:
    print('pon')
elif N % 10 in [3]:
    print('bon')

ABC168B - ... (Triple Dots)

Brechen Sie in 2 Minuten durch. Schreiben Sie einfach.

K = int(input())
S = input()

if len(S) <= K:
    print(S)
else:
    print(S[:K] + '...')

ABC168C - : (Colon)

Es bricht in 9,5 Minuten durch. Es gibt eine dumme Person, die vergisst, den Stundenzeiger auch in Minuten zu bewegen.

from math import pi, sin, cos, sqrt

A, B, H, M = map(int, input().split())

x1 = A * cos(2 * pi * (H + M / 60) / 12)
y1 = A * sin(2 * pi * (H + M / 60) / 12)
x2 = B * cos(2 * pi * M / 60)
y2 = B * sin(2 * pi * M / 60)

print(sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)))

ABC168D - .. (Double Dots)

Es brach in 9,5 Minuten durch. Das Problem war, dass es einfach war, vom Eingang aus nach Breitenpriorität zu suchen, aber es war schwer, mit starkem Herzen zu behaupten, dass es keinen Fall von „Nein“ gab.

from collections import deque

N, M = map(int, input().split())
AB = [map(int, input().split()) for _ in range(M)]

links = [[] for _ in range(N + 1)]
for a, b in AB:
    links[a].append(b)
    links[b].append(a)

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

ABC168E - ∙ (Bullet)

Ich konnte es nicht lösen, weil es lösbar zu sein schien. Vielleicht ist der Fall, in dem entweder A i </ sub> oder B i </ sub> 0 ist, nicht vollständig.

Nachtrag: (A i </ sub>, B i </ sub>) = (0, 0) wurde falsch behandelt. (0, 0) liegt nahe an allen Fischen Es war so schlimm, dass ich es später hinzufügen musste.

Ich verstehe, dass b / a und -a / b nicht gut miteinander auskommen, aber leider hat Python keine rationalen Zahlen, deshalb ersetze ich das Taple von (a, b). Übrigens (1, 2) und (-4, 2) Ich verstehe mich nicht gut, aber ich weiß es überhaupt nicht, also teile a und b durch gcd (a, b) und teile sie. Dies ergibt (1, 2) und (-2, 1), also ( Nur (-b, a), (b, -a) haben eine schlechte Beziehung zu a, b). Auch (-b, a), (b, -a) sind beide (-a, -b). (A, b) und (-a, -b) sind Gruppen, weil sie nicht gut miteinander auskommen. Die Anzahl der Fälle für jedes existierende (a, b) beträgt 2 ^ (die Anzahl von (a, b) + ( -A, -b) Zahl) + 2 ^ ((-b, a) Zahl + (b, -a) Zahl) -1 (es gibt keine letzte -1, aber es wird dupliziert), also multiplizieren Addieren Sie dann die Zahl (0, 0) am Ende und subtrahieren Sie eine von dem Betrag, den Sie nicht ausgewählt haben, und Sie erhalten die Antwort.

Die Theorie ist einfach, aber die Implementierung ist kalorienreich und nervig ...

from math import gcd

N = int(input())
AB = [map(int, input().split()) for _ in range(N)]

t = []
d = {}
d[0] = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    t.append((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1

used = set()
result = 1
for a, b in t:
    if (a, b) in used:
        continue
    used.add((a, b))
    if a == 0 and b == 0:
        continue
    i = d[a][b]
    j, k, l = 0, 0, 0
    if -a in d and -b in d[-a]:
        j = d[-a][-b]
        used.add((-a, -b))
    if -b in d and a in d[-b]:
        k = d[-b][a]
        used.add((-b, a))
    if b in d and -a in d[b]:
        l = d[b][-a]
        used.add((b, -a))
    result *= pow(2, i + j, 1000000007) + pow(2, k + l, 1000000007) - 1
    result %= 1000000007
result += d[0][0] - 1
result %= 1000000007
print(result)

Recommended Posts

AtCoder Beginner Contest 181 Teilnahmebericht
AtCoder Beginner Contest 151 Teilnahmebericht
AtCoder Beginner Contest 176 Teilnahmebericht
AtCoder Beginner Contest 154 Teilnahmebericht
AtCoder Beginner Contest 166 Teilnahmebericht
AtCoder Beginner Contest 153 Teilnahmebericht
AtCoder Beginner Contest 145 Teilnahmebericht
AtCoder Beginner Contest 184 Teilnahmebericht
AtCoder Beginner Contest 165 Teilnahmebericht
AtCoder Beginner Contest 160 Teilnahmebericht
AtCoder Beginner Contest 169 Teilnahmebericht
AtCoder Beginner Contest 178 Teilnahmebericht
AtCoder Beginner Contest 163 Teilnahmebericht
AtCoder Beginner Contest 164 Teilnahmebericht
AtCoder Beginner Contest 168 Teilnahmebericht
AtCoder Beginner Contest 150 Teilnahmebericht
AtCoder Beginner Contest 158 Teilnahmebericht
AtCoder Beginner Contest 180 Teilnahmebericht
AtCoder Beginner Contest 156 Teilnahmebericht
AtCoder Beginner Contest 162 Teilnahmebericht
AtCoder Beginner Contest 157 Teilnahmebericht
AtCoder Beginner Contest 167 Teilnahmebericht
AtCoder Beginner Contest 179 Teilnahmebericht
AtCoder Anfängerwettbewerb 182
AtCoder Anfängerwettbewerb 146 Teilnahmebericht
AtCoder Beginner Contest 152 Teilnahmebericht
AtCoder Beginner Contest 155 Teilnahmebericht
AtCoder Beginner Contest 174 Teilnahmebericht
AtCoder Beginner Contest 171 Teilnahmebericht
AtCoder Beginner Contest 149 Teilnahmebericht
AtCoder Anfängerwettbewerb 148 Teilnahmebericht
AtCoder Beginner Contest 170 Teilnahmebericht
AtCoder Beginner Contest 183 Teilnahmebericht
AtCoder Beginner Contest # 003 Teilnahmehinweis
AtCoder Grand Contest 041 Teilnahmebericht
AtCoder Grand Contest 040 Teilnahmebericht
AtCoder Regular Contest 105 Teilnahmebericht
AtCoder Regular Contest 104 Teilnahmebericht
Eintragsdatensatz für den ACL-Anfängerwettbewerb
Atcoder Anfängerwettbewerb 146 Teilnahme Tagebuch
Teilnahmebericht des AtCoder Chokudai Contest 005
AtCoder Grand Contest 047 Teilnahmebericht
AtCoder Anfängerwettbewerb 177
AtCoder Anfängerwettbewerb 179
AtCoder Anfängerwettbewerb 172
AtCoder Anfängerwettbewerb 180
AtCoder Anfängerwettbewerb 173
Atcoder Anfänger Wettbewerb 153
Teilnahmebericht des AtCoder HHKB Programmierwettbewerbs 2020
Teilnahmebericht des AtCoder Acing Programming Contest 2020
Teilnahmebericht des AtCoder Keyence Programming Contest 2020
Teilnahmebericht des AtCoder Panasonic Programming Contest 2020
AtCoder Anfängerwettbewerb 152 Rückblick
AtCoder Anfängerwettbewerb 181 Hinweis
AtCoder Beginner Contest 160 Bewertung
AtCoder Anfängerwettbewerb 178 Bewertung
AtCoder Anfängerwettbewerb 180 Hinweis
AtCoder Anfängerwettbewerb 167 Bewertung
Teilnahmebericht zum AtCoder Library Practice Contest (Python)