AtCoder ABC 182 Python (A ~ D)

Sommaire

A, B, C résolus. D est un pas de plus. E lisez simplement la phrase du problème en un rien de temps, mais c'était un problème étonnamment simple, donc il aurait peut-être été bon de résoudre E en premier.

problème

https://atcoder.jp/contests/abc182

A. twiblr

Répondre

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

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

Écrivez simplement ceci.

B. Almost GCD

Répondre

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)

C'est aussi fondamentalement juste écrit, mais l'implémentation est un peu compliquée pour le problème B.

C. To 3

Répondre

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)

Pour les nombres multiples de 3, vous pouvez tester si la somme de chaque chiffre est un multiple de 3. Puisque vous pouvez essayer toutes les méthodes d'une manière contrainte, sélectionnez un nombre arbitraire de chaque chiffre de la combinaison et essayez si la somme peut être divisée par 3.

D. Wandering

Réponse (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 et max_index+Considérez 1 et adoptez le plus grand
    # max_Lors de l'utilisation d'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+Lors de l'utilisation de 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)

J'ai réfléchi trop fort, le code est devenu long et je n'ai pas pu obtenir deux WA.

Réponse (AC à une date ultérieure)

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)

Ce problème est facile sans tenir compte des contraintes, mais il était difficile en termes de réduction de la quantité de calcul. Je me suis vite rendu compte que la politique de réduction du montant du calcul était la somme cumulative, mais je n'ai pas pu la résoudre car j'étais confuse en chemin.

Si tu penses calmement,

1. Prenez la somme cumulée (cumA)
2. Prenez une liste de max jusqu'à chaque indice de somme cumulée (max_cumA)
3. Utilisez max_cumA pour mettre à jour la portée maximale (max_point)

Je l'ai finalement résolu proprement. Je pensais que le but de ce problème était de "prendre une autre idée après avoir pris la somme cumulée".