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

Benötigte Zeit

Impressionen

In der Vergangenheit konnte ich das XOR-Problem nicht lösen, aber sobald ich die Grundlagen gelernt hatte, dass es einfacher zu berechnen wäre, wenn jede Ziffer binär geteilt würde, könnte ich es lösen. Die Erklärung und der Code von D sind schwer zu verstehen, daher warte ich auf Verbesserungsvorschläge.

Problem A

Finden Sie einfach max.

answerA.py

a,b=map(int,input().split())
print(max(a+b,a-b,a*b))

B-Problem

Es gibt N-1 Möglichkeiten, sich in x und y zu unterteilen, und für jede von ihnen ist die Größe der größten Produktmenge die Antwort, indem x und y zu einer Menge anstelle einer Zeichenfolge gemacht werden.

answerB.py

n=int(input())
s=input()
ans=0
for i in range(n-1):
    s1=s[:i+1]
    s2=s[i+1:]
    s3=set(s1)&set(s2)
    ans=max(ans,len(s3))
print(ans)

C-Problem

Wenn Sie sich für einen Anführer entscheiden, können Sie die Anzahl der Personen westlich dieses Anführers zählen, die nach Westen ausgerichtet sind, und die Anzahl der Personen östlich dieses Anführers, die nach Osten ausgerichtet sind. Die Anzahl der Personen beträgt jedoch O ( Muss mit 1) oder O (log (n)) berechnet werden. Da die Anzahl der Personen ** kumulative Summe ** ist, kann sie durch O (1) berechnet werden, indem die Anzahl der nach Westen und nach Osten gerichteten Personen als kumulative Summe berechnet wird.

answerC.py

n=int(input())
s=input()
l=[0]*n
r=[0]*n
for i in range(1,n):
    l[i]=l[i-1]+(s[i-1]=="W")
for i in range(n-2,-1,-1):
    r[i]=r[i+1]+(s[i+1]=="E")
ans=n-1
for i in range(n):
    ans=min(ans,l[i]+r[i])
print(ans)

D Problem

Zuerst habe ich über Paraphrasierung nachgedacht, weil xor gleich + wird. Dann habe ich in XOR festgestellt, dass es keinen Übertrag ** gibt, da die Anzahl der Einsen in jeder Ziffer 1 ist, wenn es sich um eine ungerade Zahl handelt, und 0, wenn es sich um eine gerade Zahl handelt, wenn sie in eine Binärzahl konvertiert wird. Daher können Sie beim Hinzufügen sehen, dass ** wenn kein Übertrag für alle Ziffern vorhanden ist **, das Thema erfüllt ist. Mit anderen Worten, es gibt auch keinen Übertrag in der i-ten Ziffer **, was der Anzahl von $ A_l… A_r $ entspricht, wobei die i-te Ziffer 1 oder weniger ** ist. Ich werde. Bereiten Sie zunächst ein Array vor, in dem die Anzahl der Einsen in jeder Ziffer gespeichert ist. Basierend darauf werden wir nach Kandidaten für l und r suchen, aber überlegen, ob $ A_l… A_ {r + 1} $ gilt, wenn $ A_l… A_r $ gilt, $ A_l… A_r $ und $ A_l… A_ { Wenn Sie auf jede Ziffer von r + 1} $ achten, wird die Anzahl von ** 1 entweder erhöht oder unverändert **. Wenn also l festgelegt ist, ist die Menge von (l, r), die 2 nicht überschreitet, unter Berücksichtigung der Anzahl von 1s in jeder Ziffer von $ A_l… A_r $ für r = l + k (k> = 1) das Subjekt. Treffen. Wenn Sie zu diesem Zeitpunkt die ** Skalierungsmethode ** verwenden, können Sie alle (l, r) Kandidaten zählen, indem Sie ** r verschieben, um das Thema zu erfüllen, und dann l ** verschieben. Ich werde. Da ich vergessen habe, wie die Skalierungsmethode implementiert wird, werde ich den Code der Skalierungsmethode überprüfen. Weitere Informationen finden Sie in Kenchons Artikel. Bitte. Das Wichtige an diesem Problem ist, dass wenn ** (l, r) gilt, (l + 1, r) auch ** gilt (wie Sie aus der bisherigen Diskussion sehen können). Wenn daher die Skala genommen wird, wenn l fest ist und r erhöht wird, während das Subjekt erfüllt ist, gilt ** (l + 1, r) auch für alle r **. Daher ist es möglich, l effizient zu drehen, indem 0 → n-1 gedreht wird, indem die for-Anweisung gedreht wird, und r getrennt von der for-Anweisung gehalten und erhöht wird. Übrigens hat Python auch mit dieser Skalierungsmethode nicht bestanden, also habe ich es mit PyPy bestanden.

Die Erklärung ist schwer zu verstehen und der Code ist etwas schwer zu verstehen. Bitte lassen Sie mich wissen, wenn Sie Verbesserungsvorschläge haben.

Nachtrag (2020/04/11)

In Anbetracht des Falls, in dem nicht für alle Ziffern ein Übertrag vorhanden ist, sind die Ergebnisse der + -Operation und der ^ -Operation gleich. Speichern Sie also die Ergebnisse der + -Operation und der ^ -Operation "für jede Ziffer". Es kann als Alternative zu einem Array verwendet werden, in dem die Anzahl der Einsen gespeichert ist (auf diese Weise können Sie auch Python verwenden. Weitere Informationen finden Sie in den Kommentaren). Auch der zweite Code wird auf diese Weise implementiert.

answerD.py

n=int(input())
a=list(map(int,input().split()))
ans=0
right=0
now=[0]*20#2^Weil es 20 ist
for i in range(n):
    left=i
    if i!=0:
        for j in range(20):
            if (a[left-1]>>j)&1:
                now[j]-=1
    else:
        for j in range(20):
            if (a[left]>>j)&1:
                now[j]+=1
    while all([now[j]<=1 for j in range(20)]):
        right+=1
        if right==n:
            break
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]+=1
    else:
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]-=1
    right-=1
    ans+=(right-left+1)
print(ans)

answerD2.py

n=int(input())
a=list(map(int,input().split()))
ans=0
right=0
np,nx=a[0],a[0]
for left in range(n):
    while np==nx:
        right+=1
        if right==n:
            break
        np+=a[right]
        nx^=a[right]
    else:
        np-=a[right]
        nx^=a[right]
    right-=1
    ans+=(right-left+1)
    np-=a[left]
    nx^=a[left]
print(ans)