[PYTHON] Wettkampf-Tagebuch für berufliche Hingabe vom 11. bis 14. Tag (7/5 bis 7/8)

Impressionen

Ich habe einen Tag verpasst, aber ich möchte motiviert bleiben und diesen Monat weitermachen. Ich hoffe, die Probleme von Hellblau und Blau während dieses Andachtstagebuchs zu stabilisieren und ein blauer Kodierer zu werden. Ich muss auch für die Abschlussforschung studieren, also möchte ich mein Bestes geben. Ich tastete, weil ich nicht weiß, wie leicht es zu lesen ist, aber ich hoffe, ich kann es alle drei Tage einmal aktualisieren.

11. Tag

ABC132-E Hopscotch Addict

Zeit genommen

Ungefähr 30 Minuten

Erwägung

** Wir werden BFS ** verwenden, um die kürzeste Entfernung ohne Gewicht zu finden. Zuerst dachte ich über eine Methode nach, um das Ziel zu aktualisieren, um drei aufeinanderfolgende kenkenpa als neue Seite zu erreichen, aber wenn Sie über die Seite nachdenken, die sich von jedem Scheitelpunkt in der richtigen Reihenfolge erstreckt, ** ist es offensichtlich nicht rechtzeitig und es gibt viele nutzlose Berechnungen **. Ich habe es abgelehnt.

Unter der Annahme, dass Sie das Ziel erreichen können (Bewegung von höchstens $ M $ mal), ist es ein Vielfaches von 3, wenn Sie es dreimal wiederholen, also am Ende ** Bewegung von höchstens $ 3 \ mal M $ mal ** ich habe bemerkt, dass Wie oben erwähnt, sollten Sie die kürzeste Entfernung in jedem der drei Zustände berücksichtigen, in denen die Entfernung zum Ziel durch drei geteilt wird, wenn Sie ** umschreiben können, um das Ziel in einer Entfernung zu erreichen, die ein Vielfaches von 3 ** ist. Ich weiß, dass es gut ist.

In Anbetracht der erweiterten Dyxtra-Methode, bei der jeder Scheitelpunkt einen Zustand ** hat, und des erweiterten BFS **, bei dem jeder Scheitelpunkt drei Zustände hat, ein Array, das die kürzeste Entfernung wie ein normales BFS speichert ($ score [$ score [ i] [j]: = i $ Nur wenn der kürzeste Abstand zum dritten Scheitelpunkt durch 3 geteilt wird und der Rest $ j $ (der kürzeste Abstand in der Bewegung) ist und das Array inf wird. Wenn es aktualisiert werden kann, kann es mit $ O (M + N) $ implementiert werden.

import sys
sys.setrecursionlimit(10**6)
from collections import deque
n,m=map(int,input().split())
edges=[[] for i in range(n)]
for i in range(m):
    u,v=map(int,input().split())
    edges[u-1].append(v-1)
s,t=map(int,input().split())
inf=100000000000
score=[[inf]*3 for i in range(n)]
now=deque()
now.append(s-1)
score[s-1][0]=0
def bfs(dep,l):
    global n,m,edges,s,t,score,inf,now
    f=False
    for i in range(l):
        ne=now.popleft()
        for j in edges[ne]:
            if score[j][dep%3]==inf:
                score[j][dep%3]=dep
                now.append(j)
    l_ne=len(now)
    if l_ne:bfs(dep+1,l_ne)
bfs(1,1)
if score[t-1][0]!=inf:
    print(score[t-1][0]//3)
else:
    print(-1)

12. Tag

Ich habe das ABC173-E gelöst, das ich während des Wettbewerbs nicht bestehen konnte. Es ist in [diesem Artikel] zusammengefasst (https://qiita.com/DaikiSuyama/items/fa7f0bef79216a499650).

13. Tag

Ich konnte die Zeit nicht gut nutzen. Es tut mir Leid.

Tag 14

ABC135-D Digits Parade

Zeit genommen

25 Minuten

Erwägung

Da ich es bereut habe, habe ich das Problem des geringen Diff so schnell wie möglich gelöst. Ich habe das Gefühl, dass ich zuvor ein ähnliches Problem gelöst habe, aber ich bin froh, dass ich in angemessener Zeit AC konnte. Da ich RE jedoch einmal ausgestellt habe, bereue ich es.

Der größte Punkt ist zunächst, DP zu bemerken. ** Es ist eine Zeichenkette und es ist schwierig, den? Teil ** zu verarbeiten. Der **? Teil erhöht die Anzahl der Kandidaten ($ \ leftrightarrow $ Übergangsmethode erhöht sich) **, ** Mit dieser Zeichenkette In Anbetracht der Tatsache, dass der Rest der angezeigten Nummer durch die Entscheidung der Ziffern nacheinander bestimmt wird **, ist es meines Erachtens nicht schwierig, einen DP zu versenden, der den Status jeder Ziffer berücksichtigt.

Berücksichtigen Sie hier den Status einer bestimmten Ganzzahl (Zeichenfolge, die darstellt), wenn Sie nach ** $ i $ Ziffern ** suchen, aber hier, unter Berücksichtigung des Restes, $ dp [i] [j]: = i Es ist gut zu wissen, wie viele Zahlen $ j $ sind, wenn Sie sich die $ -Ziffer ansehen und durch 13 dividieren.

In Bezug auf den Übergang von DP sollten dann die folgenden zwei Fälle berücksichtigt werden ($ p [i] $ wird durch Teilen von $ 10 ^ i $ durch 13 vorberechnet).

① Wenn die $ i $ -Ziffer $ k (0 \ leqq k \ leqq 9) $ ist Das Übergangsziel von $ dp [i] [j] $ ist $ dp [i + 1] [(j + k * p [i])% 13] $.

② Wann ist die Ziffer $ i $? Alles was Sie tun müssen, ist $ l $ des Musters ① von 0 bis 9 zu machen.

Ich habe auch versucht, $ p [i] $ in der Schleife zu finden, die DP ausführt, aber da es notwendig ist, maximal $ 10 ^ {10 ^ 5-1} $ zu finden, berechnen Sie zuerst nur den Rest. Ich habe versucht, es zu verlassen.

Nach der Implementierung des obigen ist der Code wie folgt.

mod=10**9+7
s=input()[::-1]
l=len(s)
dp=[[0]*13 for i in range(l+1)]
dp[0][0]=1
#Vorberechnung, weil die Leistung zu groß ist
p=[0]*l
p[0]=1
for i in range(l-1):
    p[i+1]=(p[i]*10)%13
for i in range(l):
    s_sub=s[i]
    if s_sub=="?":
        for j in range(13):
            for k in range(10):
                dp[i+1][(j+k*p[i])%13]+=dp[i][j]
                dp[i+1][(j+k*p[i])%13]%=mod
    else:
        k=int(s_sub)
        for j in range(13):
            dp[i+1][(j+k*p[i])%13]+=dp[i][j]
            dp[i+1][(j+k*p[i])%13]%=mod
print(dp[l][5])

ABC133-E Virus Tree 2

Zeit genommen

Es dauert fast eine Stunde, aber WA

Fehlerursache

Ich konnte überhaupt nicht debuggen, weil ich es anders implementiert habe als ich es mir vorgestellt hatte. ** Ich hatte nicht genug Kraft, um an meine Gedanken zu glauben **, richtig? Ich bin nicht sehr gut darin, solche Muster zu debuggen, aber ist es eine Erfahrung ...? ??

Erwägung

Erstens, da es sich um einen Baum handelt, kann gesagt werden, dass ** Seiten N-1 Seiten sind, alle Eckpunkte verbunden sind und es keinen geschlossenen Pfad ** gibt. Darüber hinaus beträgt der Abstand zwischen zwei verschiedenen Scheitelpunkten (die für die Verfolgung erforderliche Mindestanzahl von Seiten) 2 oder weniger (1 oder 2).

Hier kann ** jeder Baum als Wurzelbaum angesehen werden **, daher habe ich mich für einen Baum entschieden, dessen Wurzel Scheitelpunkt 1 ist. Außerdem ist es besser, jeweils eine Farbe zu malen, damit die Nachbarn unterschiedlich bemalt werden. Daher habe ich vorerst von der Spitze aus gemalt, die der Wurzel am nächsten liegt. (Wenn es unmöglich war, wollte ich es umgekehrt von den Blättern auftragen.)

Um zu bestätigen, wie man malt, habe ich mich für einen Baum mit 8 Eckpunkten und 7 Seiten entschieden, wie in der folgenden Abbildung gezeigt. In der folgenden Abbildung ist rot dargestellt, welcher Scheitelpunkt beim Malen von oben nicht unterschiedlich sein sollte.

Die Verbalisierung des Malens der Farben in der obigen Abbildung ist wie folgt.

Erstens gibt es $ K $ Möglichkeiten, Wurzeln zu malen. Da sich die Farbe der anderen Scheitelpunkte als der Wurzel von der Farbe der Scheitelpunkte unterscheidet, deren Abstand 1 oder 2 beträgt, ** Eltern **, ** Eltern Eltern **, ** Geschwister (Scheitelpunkte mit demselben Elternteil) * Anders als *. Da das Elternteil des Elternteils auf dem Höhepunkt der Tiefe 1 nicht vorhanden ist, kann ** Wie die Farbe des Bruders gemalt wird ** aus anderen Straßenfarben als den Eltern $ \ _ {K-1} ausgewählt werden. P \ _ {Gesamtzahl der Geschwister} $. Da sich am Scheitelpunkt der Tiefe 2 immer ein Elternteil des Elternteils befindet, wählen Sie außerdem aus anderen Straßenfarben als dem Elternteil und dem Elternteil des Elternteils $ K-2 $ P \ _ {Bruder Die Gesamtzahl von} $ wird sein.

Als ich hier aufzeichnete, wie man die Farben meiner Brüder malt, habe ich sie einmal im Array gespeichert, aber ** ich habe den falschen Wert aufgezeichnet **. Es wäre sehr enttäuschend, wenn ich den Testfall selbst und die Probe genau machen könnte.

from sys import setrecursionlimit
setrecursionlimit(10**6)
n,k=map(int,input().split())
paths=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)
inf=100000000000000
nums=[-inf]*n
nums[0]=k
from collections import deque
now=deque()
now.append(0)
def bfs(d):
    global n,k,paths,nums,now
    l=len(now)
    if d==1:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-1
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    else:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-2
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    if len(now):bfs(d+1)
bfs(1)
ans=1
for i in range(n):
    if nums[i]<=0:
        print(0)
        exit()
    ans*=nums[i]
    ans%=(10**9+7)
print(ans)