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

Benötigte Zeit

Impressionen

Ich konnte es wegen einiger Besorgungen nicht bis zum Ende beenden, aber ich denke, es war ein Set, das schnell fertiggestellt werden konnte, selbst wenn ich keine Zeit hatte, wenn ich ruhig war. Es wäre schön, wenn Sie es bei Verwendung eines solchen Sets fest entfernen könnten.

Problem A

Wenn Sie den Unterschied in der Anzahl der Reiskuchen verringern, beträgt der Unterschied höchstens einen (ich werde es nicht beweisen, aber ich denke, es ist offensichtlich). Betrachten Sie daher den Fall, in dem die Differenz 0 ist, aber in diesem Fall ist n durch k teilbar. Wenn dies ausgegeben wird, ist es wie folgt.

answerA.py

n,k=map(int,input().split())
print(1 if n%k!=0 else 0)

B-Problem

Suchen Sie nach möglichen Kombinationen, bei denen n nicht groß ist. Angenommen, Sie haben 7 Donuts im Wert von 7 USD gekauft, können Sie mit dem Rest Ihres Geldes einen Kuchen im Wert von 4 USD kaufen.

answerB.py

n=int(input())
for i in range(n//7+1):
    if (n-i*7)%4==0:
        print("Yes")
        break
else:
    print("No")

C-Problem

Ich hätte nicht den Eindruck haben sollen, dass ich es richtig machen sollte, nachdem ich das Problem gesehen habe. Ich möchte mich an die Grundlagen des ** sorgfältigen Denkens und anschließenden Lösens ** erinnern. In der Antwort löse ich es mit **, das eindeutig durch die Entscheidung aus der unteren Ziffer ** bestimmt wird (ich habe es überhaupt nicht bemerkt ...), aber ich ** entscheide mich umgekehrt aus der oberen Ziffer und löse es. Es war **.

Bei der Entscheidung aus den oberen Ziffern habe ich festgestellt, dass sich der Bereich der darstellbaren Zahlen verengt. Das ist,|S_0 \times (-2)^0+S_1 \times (-2)^1+…+S_{k-1} \times (-2)^{k-1}|<|S_k \times (-2)^k|Ist wahr.

Mit Ausnahme von Mustern, bei denen dies nicht zutrifft, lautet die Antwort: Wenn Sie sich für die oberen Ziffern entscheiden und jede Ziffer hinzufügen, wird sie schließlich gleich n. Subtrahieren Sie also umgekehrt jede Ziffer von n, um sie zu 0 zu machen. Ich habe darüber nachgedacht.

Auf diese Weise wird der Absolutwert bei der Entscheidung über die k-te Ziffer festgelegt|S_k \times (-2)^k|Das Muster sollte dasjenige sein, das die obigen Fälle ausschließt.

Es gibt mehrere Kandidaten, also ** können Sie die Kandidaten speichern, wenn Sie sich mit deque bis zu einer bestimmten Ziffer entschieden haben, und mit BFS nach der Antwort suchen **.

Außerdem ist zu diesem Zeitpunkt der spezifische Rechenaufwand problematisch, sodass ich ihn nicht berechnet habe. Da er jedoch durch Beschneiden eindeutig weggelassen werden kann, habe ich ihn implementiert, ohne ihn zu berechnen.

answerC.py

from itertools import dropwhile
from collections import deque
n=int(input())
ans=deque([["",n]])
def bfs(d):
    global ans
    l=len(ans)
    for i in range(l):
        x=ans.popleft()
        new1=[x[0]+"0",x[1]]
        if abs(new1[1])<abs((-2)**d):
            ans.append(new1)
        new2=[x[0]+"1",x[1]-(-2)**d]
        if abs(new2[1])<abs((-2)**d):
            ans.append(new2)
    if d!=0:
        bfs(d-1)
bfs(32)

for i in ans:
    if i[1]==0:
        ans=list(dropwhile(lambda x:x=="0",i[0]))
        if len(ans)==0:
            print(0)
        else:
            print("".join(ans))
        break

D Problem

Ich denke, es ist ein ähnliches Problem wie das Problem, das neulich bei ABC aufgetreten ist (ich habe vergessen, welches).

Da Sie gefragt werden, ob der ** kontinuierliche Teil ** ein Vielfaches von M ist, sollten Sie anscheinend überlegen, ob die Subtraktion der kumulativen Summe ein Vielfaches von M ** ist (** Wenn Sie das Intervall mehrmals berechnen). Ist die kumulative Summe, falls dies nicht möglich ist, BIT oder Seg-Baum **). Das heißt, wenn (l, r) als Menge gegeben ist, ist $ S [l, m] = A_l + A_ {l + 1} +… + A_m $ und $ S [l, m] = S [1, m ] -S [1, l-1] \ (1 \ leqq l \ leqq r \ leqq N ) Betrachten Sie die Gesamtzahl der Paare von (l, m), die $ enthalten. Wenn $ S [1,0] = 0 $ ist, dann ist $ S [1, m] = S [1, m] -S [1, 1] \ (0 \ leqq l <r \ leqq N ) Sie können sich die Gesamtzahl der Paare vorstellen, die $ sind.

Das heißt, betrachten Sie $ S [1, k] % m $ mit k = 0 bis N, speichern Sie, wie viele kumulative Summen (x) die verbleibenden sind (unter Verwendung von Counter), und verwenden Sie jeden Rest. Alles was Sie tun müssen, ist $ _x C _2 $ zu berechnen und die Summe als Antwort zu verwenden.

answerD.py

from itertools import accumulate
from collections import Counter
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,m=map(int,input().split())
s=list(map(lambda x:x%m,list(accumulate(list(map(int,input().split()))))))
s.append(0)
d=Counter(s)
ans=0
for i in d:
    if d[i]>=2:
        ans+=combinations_count(d[i],2)
print(ans)

answerD_shortest.py

n,m,*c=map(int,open(0).read().split());d={0:1};r=s=0
for i in c:s+=i;x=d.get(s%m,0);r+=x;d[s%m]=x+1
print(r)