atcoder Review des Panasonic Programming Contest 2020, bis zu Frage E (Python)

Dies ist ein Übersichtsartikel für Anfänger von Wettkampfprofis. Klicken Sie hier für die Wettbewerbe, an denen Sie teilgenommen haben. https://atcoder.jp/contests/panasonic2020

Der Code, den ich hier schreibe, wurde geschrieben, während ich die Antworten und Erklärungen anderer Leute betrachtete. Es wurde nicht tatsächlich eingereicht.

A - Kth Term Das Problem besteht darin, den n-ten Term der Eingabe aus einer vorbestimmten Zahlenfolge auszugeben.

li = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
i = int(input())
print(li[i-1])

Beachten Sie, dass die Artikelnummern ab 1 gezählt werden.

B - Bishop $ H \ times W $ Es ist eine Frage, den Bereich zu beantworten, in dem sich die Ecke auf dem Brett des Quadrats bewegen kann.

Bitte beachten Sie, dass sich die Ecke nicht einmal um einen Schritt bewegen kann, wenn nur eine horizontale oder vertikale Größe vorhanden ist (ein Verlust).

Der von mir eingereichte Code sieht folgendermaßen aus.

import math
H, W = map(int, input().split())
if H == 1 or W == 1:
    print(1)
else:
    w_odd = math.ceil(H/2)
    w_even = H // 2
    N_odd = math.ceil(W/2)
    N_even = W // 2
    print(w_odd * N_odd + w_even * N_even)

Wenn man die horizontalen Quadrate von links zählt, unterscheidet sich die Anzahl der beweglichen Quadrate zwischen dem geraden und dem ungeraden Mal. Die Anzahl der Zellen in diesen beiden Fällen und die Anzahl der entsprechenden Spalten wurden separat berechnet.

Sie können es tatsächlich präziser schreiben.

Einfach die Hälfte aller Quadrate ist beweglich. Wenn ein Rest durch 2 geteilt wird, befindet sich die untere rechte Zelle, die der Rest ist, immer in der Position (ungerade, ungerade). Da es sich um eine bewegliche Position handelt, erhöht sie sich um ein weiteres Quadrat.

H, W = map(int, input().split())
if H == 1 or W == 1:
    print(1)
else:
    print((H * W + 1) // 2)

Es ist auch nicht erforderlich, Mathematik in den Aufrundungsprozess zu importieren.

C - Sqrt Inequality Für Eingabe A B C.

\sqrt{A} + \sqrt{B} < \sqrt C \tag{1}

Das Problem zu bestimmen, ob.

Ich reichte Folgendes ein und dachte, dass es nutzlos wäre.

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

ich hab es nicht ausgearbeitet. Sie können nicht einmal Mathe verwenden. Quadrieren wir beide Seiten von Gleichung (1). $A + 2\sqrt{AB} +B < C \tag{2}$ Das ist auch nutzlos. Ich gab auf. Ich frage mich, ob es einen Fehler bei der Berechnung der Quadratwurzel geben wird, aber ich habe diese Art von Wissen nicht.

Ich habe den Kommentar gesehen. (2) wird weiter transformiert.

2\sqrt{AB} < C - A - B

Wenn beide Seiten positiv sind, quadrieren Sie beide Seiten $ 4AB < (C - A - B)^2 $ Ist festgelegt. Jetzt ist die Quadratwurzelberechnung weg.

Also die Antwort. Dies sollte bemerkt worden sein, da es nicht schwierig sein sollte.

a, b, c = map(int, input().split())
if 0 < c - a - b and 4 * a * b < (c - a - b)**2:
    print("Yes")
else:
    print("No")

D - String Equivalence

Das Problem besteht darin, alle vorhandenen Zeichenkettenmuster mit der Anzahl der Zeichen N (≤ 10) anzuordnen.

Ich wusste nicht, wie ich es machen sollte, also versuchte ich es zu lösen, indem ich alle Muster einmal anordnete und sie dann löschte. Eigentlich steckte ich mitten im Schreiben fest und konnte es nicht einreichen, aber ich schrieb den folgenden Code.

import itertools
N = int(input())
alp = [chr(ord('a') + i) for i in range(N)]
allS = list(itertools.product(alp, repeat=N))
answers = []
PatternList = []
for s in allS:
    pattern = []
    letters = []
    for l in s:
        if not l in letters:
            letters.append(l)
        pattern.append(letters.index(l))
    if not pattern in PatternList:
        PatternList.append(pattern)
        answers.append(s)
for answer in answers:
    print(''.join(answer))

Ich dachte, es wäre möglich, N = 10 zu erreichen, aber TLE kam in der zweiten Hälfte heraus.

Ich habe den Kommentar gesehen. Die Standardformularbedingung wird durch die folgende Formel ersetzt. $ s_1 = a $ $ s_k \leq \max[ s_1, \cdots, s_{k - 1}\] + 1$

Es scheint, dass Sie mit DFS suchen sollten, um diese beiden Bedingungen zu erfüllen. Die Maximalwertinformationen werden in der Variablen mx gespeichert, die die Maximalwertinformationen enthält, und von einer rekursiven Funktion übergeben.

Das Folgende wird gemäß der Probe gemacht.

n = int(input())

def dfs(s, mx):
    if len(s) == n:
        print(s)
    else:
        for i in range(0, mx + 1):
            c = chr(ord('a') + i)
            if i == mx: dfs(s+c, mx+1)
            else: dfs(s+c, mx)

dfs('', 0)

E - Three Substrings Angesichts der drei Teilzeichenfolgen a, b und c, die aus der Zeichenfolge s entnommen wurden, ist dies das Problem, die ursprüngliche Zeichenfolge s zu erraten.

Ich habe ein leeres Array mit der Länge von a + b + c als Zeichenfolge s vorbereitet und mit dem Schreiben mit der Richtlinie begonnen, die drei von a, b und c von einem Ende aus anzuwenden, aber es gibt einige Elemente, die stecken bleiben. Ich gab auf, weil ich TLE herauskommen sah.

Ich habe den Kommentar gesehen. Holen Sie sich die "relativen Positionen", die für a und b, b und c sowie a und c als Array existieren können. Speichern Sie dies als `ab []` `,` `ac []` `,` `bc []`. Von dort wird die Positionsbeziehung zwischen a und b durch "i" dargestellt, und die Positionsbeziehung zwischen a und c wird durch "j" dargestellt. Ich kann es schaffen

Dies dreht sich um `i``` und j``` und `ab [i]` und ac [j]``, ``bc [ji ] `` `Es kann durch Berechnen der Anzahl der Zeichen erhalten werden, wenn die drei Bedingungen erfüllt sind. Beachten Sie, dass a, b und c bis zu $ \ pm 4000 $ betragen können.

Ich habe gerade den größten Teil der Erklärung für Python umgeschrieben, aber der folgende Code wurde übergeben. Selbst mit Pypy3 schlägt dieser Algorithmus zu und die Zeit beträgt nur 1991 ms. Zum Beispiel setzen Sie einfach `True``` und` False``` in`` ab [] ``anstelle von 1 und 0, um TLE zu erhalten. Es scheint eine schnellere Methode zu geben (ich habe sie noch nicht gesehen), da einige Leute ein paar Mal schnellere Berechnungszeit erhalten und andere dies in Python tun.

a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 16000, [1] * 16000, [1] * 16000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[j] != '?' and a[i] != b[j]:
            ab[i-j+8000]= 0
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[j] != '?' and b[i] != c[j]:
            bc[i-j+8000]= 0
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[j] != '?' and a[i] != c[j]:
            ac[i-j+8000]= 0
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+8000] and bc[j-i+8000] and ac[j+8000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Das ist alles für diesen Artikel. Wenn möglich, möchte ich Frage F später hinzufügen.