Atcoder Acing Programmierwettbewerb Python

Zusammenfassung

Es war schwer. Es waren A, B, C 3 Fragen AC. Ich kenne die Binärzahl nicht gut, daher überspringt D den Moment, in dem ich das Problem sehe, und ich habe das Gefühl, dass ich das E-Problem lösen kann, aber ich verstehe es nicht, selbst wenn ich mir das Antwortbeispiel ansehe.

Problem

(https://atcoder.jp/contests/aising2020/tasks)

A. Number of Multiples

Antworten

L, R, d = map(int, input().split())

count = 0
for i in range(L, R+1):
    if i % d == 0:
        count += 1

print(count)

Ich habe es gehorsam geschrieben. Andere scheinen cooler zu schreiben.

B. An Odd Problem

Antworten

N = int(input())
a = list(map(int, input().split()))

count = 0
for i in range(0, N, 2):
    if i % 2 == 0 and a[i] % 2 != 0:
        count += 1
print(count)

Ich habe das auch ehrlich geschrieben. Das Problem ist seltsam, aber die Indizes in der Liste sind gerade.

C. XYZ Triplets

Antworten

N = int(input())

keys = [i for i in range(1, N+1)]
values = [0] * N
count_dict = dict(zip(keys, values))

for x in range(1, N//6+7):
    for y in range(x, N//6+7):
        for z in range(y, N//6+7):
            n = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if n > N:
                break
            if x == y and y == z:
                count_dict[n] += 1
            elif x != y and x != z and y != z:
                count_dict[n] += 6
            else:
                count_dict[n] += 3

for v in count_dict.values():
    print(v)

Um ehrlich zu sein, drehen Sie die for-Schleife des Bereichs (1, N + 1) für x, y, z und x ** 2 + y ** 2 + z ** 2 + x Es scheint, dass * y + y * z + z * x = n``` beurteilt werden sollte. Da die Einschränkung jedoch 10 ** 4 beträgt, ist es nicht rechtzeitig, wenn Sie normalerweise eine Dreifachschleife ausführen. Reduzieren Sie daher den Rechenaufwand.

Das erste, woran ich dachte, war, dass wenn `(x, y, z) = (1,1,1)`, n 6 ist, also ist der Maximalwert, der in einer for-Schleife gedreht werden kann, `. N // 6 sieht gut aus. Da der Index jedoch "+ 1" sein muss, habe ich "N // 6 + 7" mit einem Rand gewählt. (In der Produktion habe ich `` N // 6 + 7 verwendet, aber wenn ich die Einschränkung` `` 10 ** 4 umgekehrt verwende, `(x, y, z)` Sie können sehen, dass nur bis zu ungefähr 100 verwendet werden kann. Ich habe dies während der Produktion nicht bemerkt ...)

Es scheint also, dass dies allein wahrscheinlich nicht rechtzeitig sein wird, daher werde ich erwägen, den Rechenaufwand etwas weiter zu reduzieren.

Wenn Sie einige Beispiele nennen, werden Sie Folgendes bemerken.

• "" (1,2,3) "" und "" (1,3,2) "" und "" (2,1,3) "" und "" (2,3) , 1) `und (3,1,2) `und (3,2,1) ``, wobei x, y, z alle unterschiedlich sind, n der gleiche Wert ist Es gibt 6 Kombinationen
• Die beiden sind gleich, wie `(1,1,2)` und (1,2,1) und (2,1,1) `` 1 Es gibt drei Kombinationen, bei denen n gleich ist, wenn die beiden unterschiedlich sind
• Es gibt eine Kombination, bei der n der gleiche Wert ist, wenn alle Zahlen gleich sind, z. B. `` (1,1,1) `.

Daher ist der Bereich der for-Schleife von x, y, z `Bereich (1, N // 6 + 7)` Bereich (x, N // 6 + 7) . Als `` Bereich (y, N // 6 + 7)` `` scheint es, dass die Anzahl in den obigen drei Fällen +6, +3, +1 sein sollte.

Wenn danach n N überschreitet, können Sie es schaffen, indem Sie `` `break``` hinzufügen.