AtCoder ABC 182 Python (A ~ D)

Zusammenfassung

A, B, C gelöst. D ist einen Schritt weiter. E hat den Problemsatz in kürzester Zeit gelesen, aber es war ein überraschend einfaches Problem, daher war es möglicherweise in Ordnung, E zuerst zu lösen.

Problem

https://atcoder.jp/contests/abc182

A. twiblr

Antworten

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

max_follow = 2 * A + 100
answer = max_follow - B
print(answer)

Schreib das einfach.

B. Almost GCD

Antworten

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

max_gcd = 0
answer = 0
for i in range(2, 1000+1):
    count = 0
    for a in A:
        if a % i == 0 and a >= i:
            count += 1
    if count >= max_gcd:
        answer = i
        max_gcd = count

print(answer)

Dies ist im Grunde auch nur geschrieben, aber die Implementierung ist für das B-Problem etwas kompliziert.

C. To 3

Antworten

from itertools import combinations

N = list(map(int, str(int(input()))))
k = len(N)

for i in reversed(range(1, k+1)):
    for C in combinations(N, i):
        if sum(C) % 3 == 0:
            print(k - i)
            exit()

print(-1)

Bei Zahlen, die ein Vielfaches von 3 sind, können Sie testen, ob die Summe jeder Ziffer ein Vielfaches von 3 ist. Da Sie alle Möglichkeiten auf eingeschränkte Weise ausprobieren können, wählen Sie aus jeder Ziffer in der Kombination eine beliebige Zahl aus und versuchen Sie, ob die Summe durch 3 geteilt werden kann.

D. Wandering

Antwort (2 WA)

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
cumA = np.cumsum(A)
cumA = np.append(cumA, 0)

now = 0
max_list = []
max_point = 0
max_index = 0
for i, cum_a in enumerate(cumA):
    now += cum_a
    if now >= max_point:
        max_point = now
        max_index = i
        max_list.append((max_point, max_index))

use_max_index = []
for point, index in max_list:
    if point == max_point:
        use_max_index.append(index)


answer = 0
for max_index in use_max_index:
    # max_Index und max_index+Betrachten Sie 1 und übernehmen Sie die größere
    # max_Bei Verwendung von Index
    answer_1 = max_point - cumA[max_index-1]
    count = 0
    add_amount = 0
    for i in range(max_index):
        count += A[i]
        add_amount = max(add_amount, count)

    answer_1 += add_amount

    # max?index+Bei Verwendung von 1
    answer_2 = max_point
    count_2 = 0
    add_amount_2 = 0
    if max_index <= N-1:
        for i in range(max_index+1):
            count_2 += A[i]
            add_amount_2 = max(add_amount_2, count_2)

        answer_2 += add_amount_2

    answer = max(answer, answer_1, answer_2)

print(answer)

Ich dachte zu viel nach, der Code wurde lang und ich konnte keine zwei WAs bekommen.

Antwort (AC zu einem späteren Zeitpunkt)

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

cumA = A[:]
for i in range(1, N):
    cumA[i] += cumA[i-1]

max_cumA = cumA[:]
for i in range(1, N):
    max_cumA[i] = max(max_cumA[i], max_cumA[i-1])

now_point = 0
max_point = 0
for i in range(N):
    max_point = max(max_point, now_point + max_cumA[i])
    now_point += cumA[i]

print(max_point)

Dieses Problem ist ohne Berücksichtigung der Einschränkungen einfach, aber es war schwierig, den Rechenaufwand zu reduzieren. Ich erkannte schnell, dass die Politik der Reduzierung des Rechenaufwands die kumulierte Summe war, aber ich konnte sie nicht lösen, weil ich unterwegs verwirrt war.

Wenn Sie ruhig denken,

1. Nehmen Sie die kumulative Summe (cumA)
2. Nehmen Sie eine Liste von max bis zu jedem Index der kumulativen Summe (max_cumA)
3. Verwenden Sie max_cumA, um den maximalen Reichweitenpunkt (max_point) zu aktualisieren.

Ich habe es endlich sauber gelöst. Ich dachte, dass der Sinn dieses Problems darin bestand, "eine andere Idee zu nehmen, nachdem man die kumulative Summe genommen hat".