[PYTHON] AtCoder Beginner Contest 125 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Frühere Fragen wurden vor einigen Tagen gelöst Es ist typisch für einen Stein, also konnte ich es nicht lösen

Problem A

Es ist einfach zu bedenken, wie oft Kekse hergestellt werden.

answerA.py

a,b,t=map(int,input().split())
print(b*(t//a))

B-Problem

Greifen Sie vom kleinsten Index in aufsteigender Reihenfolge zu und zählen Sie den größeren im Vergleich zu 0.

answerB.py

n=int(input())
v=input().split()
c=input().split()
co=0
for i in range(n):
    co+=max(0,int(v[i])-int(c[i]))
print(co)

C-Problem

In der Ära der vier Fragen ist das C-Problem schwieriger als das D-Problem, nicht wahr? Nun, das ist das typische Problem ... Da Sie eine Ganzzahl auswählen und in eine beliebige Zahl umschreiben können, können Sie sehen, dass Sie die maximale Versprechenszahl der verbleibenden N-1-Ganzzahlen finden und den Maximalwert berücksichtigen können. Bei einer reinen Implementierung ist dies jedoch O ($ N ^ 2 \ times log (maxA) $), sodass die Einschränkung mit einem Spielraum überschritten wird. Aus irgendeinem Grund (ich glaube ich war verrückt) habe ich hier versucht, ohne eine Richtlinie zu experimentieren oder einen geeigneten Algorithmus (wie Dichotomie) zu verwenden. Während ich über den Grund nachdachte, warum dies nicht möglich ist, machte ich die folgenden wichtigen Entdeckungen. (Grundlagen in den Grundlagen ...)

Es gibt einen Algorithmus, um den Rechenaufwand zu reduzieren!

Mit anderen Worten, ich denke, es ist leicht zu bemerken, dass das erste, was bei diesem Problem zu berücksichtigen ist, ** die Ursache für den großen Rechenaufwand ** ist, und ** es gibt einen Teil der GCD-Berechnung, der mehrfach berechnet wird . Ich werde. Wenn man zum Beispiel den Fall der Auswahl der k-ten Ganzzahl und den Fall der Auswahl der k + 1ten Ganzzahl vergleicht, ist gcd gcd (gcd ($ A_1 $ ~ $ A_ {k-1} )) bzw. gcd ( A_). {k + 1} $ ~ $ A_ {N} )) und gcd (gcd ( A_1 $ ~ $ A_ {k} ), gcd ( A_ {k + 2} $ ~ $ A_ {N} $) ), Sie können also sehen, dass $ A_1 $ ~ $ A_ {k-1} $ und $ A_ {k + 2} $ ~ $ A_ {N} $ häufig sind. Auf die gleiche Weise ist es bei der Auswahl von $ A_1 $ ~ $ A_ {N} $ unter Berücksichtigung der kumulierten gcd von links und rechts nicht erforderlich, mehrere Male und O ($ N \ times log (maxA)) zu berechnen. Sie können die Bestellung auf $) fallen lassen und berechnen. Aus dem oben Gesagten war es möglich, ein Programm einfach zu schreiben, indem die Memo-Phase und die Berechnungsphase getrennt und gehorsam implementiert wurden. ( Ich habe die Angewohnheit, seltsam kompliziert zu denken, deshalb möchte ich es beheben. **)

answerC.py

from fractions import gcd

n=int(input())
a=[int(i) for i in input().split()]
a1=[a[0]]
for i in range(1,n-1):
    a1.append(gcd(a1[-1],a[i]))
a2=[a[-1]]
for i in range(n-2,0,-1):
    a2.append(gcd(a2[-1],a[i]))
m=[]
for i in range(n-2):
    m.append(gcd(a1[i],a2[-i-2]))
m.append(a1[-1])
m.append(a2[-1])
print(max(m))

D Problem

Zunächst werde ich auch damit experimentieren. In diesem Problem möchten wir die Summe maximieren, daher besteht die Idee darin, die Anzahl der Positiven in der Ganzzahlsequenz so weit wie möglich zu erhöhen. Wenn Sie das Experiment wiederholen, werden Sie feststellen, dass ** die meisten Elemente korrigiert werden können **. Da die meisten Elemente positiv sind, könnte die in diesem Problem definierte Operation ** eine Operation erstellen, die ein beliebiges i, j auswählt und $ A_i $ und $ A_j $ mit -1 ** multipliziert. Ich dachte. Diese Hypothese ist richtig: $ A_i $ und $ A_ {i + 1} $, $ A_ {i + 1} $ und $ A_ {i + 2} $,…, $ A_ {j-2} $ und $ A_ { Dies kann erreicht werden, indem die in diesem Problem definierten Operationen in der Reihenfolge j-1} $, $ A_ {j-1} $ und $ A_ {j} $ ausgeführt werden. Wenn das Obige gezeigt werden kann, da nur eine gerade Anzahl negativer Elemente positiv gemacht werden kann, können bei einer geraden Anzahl negativer Elemente alle positiv gemacht werden. Finden Sie daher SUMME (absoluter Wert aller Zahlen) und negative Elemente. Wenn es eine ungerade Anzahl von SUMs gibt, finden Sie SUM mit Ausnahme von ** dem kleinsten Element des Absolutwerts **.

answerD.py

n=int(input())
a=[int(i) for i in input().split()]
a.sort()
j=n
for i in range(n):
    if a[i]>=0:
        j=i
        break
a=list(map(abs,a))
a.sort()
if j%2==0:
    print(sum(a))
else:
    print(sum(a)-2*a[0])