Det är inte så mycket problemlösning i den här, utan snarare att implementera den. Här är enkel lösning:
Låt oss formulera om problemet lite så det blir lättare att tänka på. Gör om strängen till en array av heltal, där alla B blir ettor, och V nollor. För att slippa oroa oss om cirkulära arrayer kan vi bara lägga till en kopia av till slutet av . Det är jobbigt att tänka på klippningar, så efter lite tänk kan vi insé att varje klippningar motsvarar "om vi börjar på index i får vi stycken godisar". Så om vi testar varje får vi rätt svar, men detta tar ju tid.
För att optimera lösningen kan vi försöka återanvända arbete. Låt . Vad är skillnaden mellan och ?
Vad är skillnaden mellan de?
Så vad vi kan göra är att beräkna , och sen beräkna varje , osv genom att ta bort och lägga till ett tal. Denna tekniken brukar kallas sliding window.
Om vi befinner oss på en viss dag är det ganska svårt att avgöra vilken tv-serie som är bäst att titta på. Istället vi att bygga upp en bank av extratid. Extratid är dagar där vi hade kunnat kollat på tv, men vi inte vad vi ska kolla på, så vi sparar den. När vi väl kommer till en födelsedag vet vi vilka serier vi måste kolla på. Då kan vi helt enkelt kolla om vi har nog med extratid för att kolla på alla tv-serierna som behövs. Så ett sätt man kan tänka på det är att när vi väl är på en födelsedagsfest så tidsreser vi tillbaka och bestämmer vad vi skulle ha kollat på.
Som tur är så är korridoren ganska kort! Detta låter oss modellera problemet som en graf: varje meter är en nod. Hur ser kanterna ut?
Nu vill vi helt enkelt hitta snabbaste sättet att ta oss från början till slutet i en viktad graf. Djikstra är perfekt för detta!
Notera att denna implementation av djikstra är suboptimal, eftersom vi pushar saker i kön när vi kanske inte egentligen behöver göra det. Snabbare är att hålla koll på kortaste vägen hittills till varje nod och bara pusha om det förbättrar avståndet. Jag är ganska säker på att det finns testdata som gör att den är lika långsam som min, men i praktiken har ingen såna, så det blir snabbare. Det är i alla fall lite lättare att koda det såhär.
Notera att problemet går att lösa även för långa korridorer- dom enda platserna som egentligen spelar roll är början och slut av korridoren och början och slutet av varje rullband, vilket ger noder och kanter. Detta är dock pilligare, så vi gör inte det eftersom det inte behövs.
För dom första 50 poängen så funkar det fint att bara simulera problemet precis så som dom efterfrågar. För subtask 3/4 ger det problem eftersom folk stannar så länge i pariserhjulet. För att få mer poäng behöver vi byta perspektiv lite. Istället för att simulera hela hjulet kan vi representera hjulet på följande form: för varje person i det, när kommer dom hoppa av? Vi vet då att gruppen med minst tidpunkt att hoppa av kommer hoppa av först, så vi kan spola fram i tiden tills dess. Sen stiger ett nytt lag på, och så lägger vi in tiden när dom kommer hoppa av osv osv.
Så vi behöver alltså en datastruktur som kan:
Det finns en relativt simpel lösning för alla grupper förutom den sista. Låt oss börja bygga trädet från nod (i delgrupper 1-4 räcker det med , i delgrupp 5 kan vi testa alla möjliga ).
Låt oss definiera = minsta möjliga tiden att växa subträdet rotat vid . Det vill säga, vi tar bort komponenten som förälderkanten kopplar ihop oss med. För att kunna beräkna kan vi först insé att tiden det tar att växa ut varje barns subträd är oberoende. Så det första vi gör är att beräkna för varje barn, det vill säga tiden för att växa ut varje subträd bland 's barn. Så det enda vi behöver göra nu är att bestämma i vilken ordning vi ska växa ut kanter till våra barn.
Hur långd tid tar det att växa ut en given ordning av barn? Det tar:
Det vill säga, för första barnet tar det en sekund att växa kanten till barnet, och sen tar det sekunder att växa klart subträdet. Vi behöver dock inte sitta still och vänta; vi kan direkt efter växa en kant till barn nr 2, osv. Utifrån denna formeln borde det går det att inse att det är optimalt att växa ut den största först, näst största därefter osv.
Följande lösning ger därmed 72 poäng:
Härifrån kan du antingen snabba upp den med smått pillig tree reroot dp, vilket du kan läsa mer om här.
Eller så kan du helt tänka om lösningen. Ett vanligt trick kan ibland vara att göra problemet "baklänges". Så vad händer om vi börjar med det fulla trädet och försöker göra processen baklänges? Jo, varje nod som är granne med ett löv får ta bort exakt ett löv. Detta kan sedan producera nya löv, vilket fortsätter tills trädet är borta. Med detta perspektivet är det ganska uppenbart att det inte spelar roll vad vi gör om vi löser problemet baklänges, så länge vi poppar så många löv som möjligt samtidigt. Koden blir lite smått pillig. Går kanske att förenkla den smått.
När spelet väl börjat har varje spelare alltid 2 val: äta glassen till höger, eller äta glassen till vänster (så länge dom inte har förlorat).
Därmed kan vi svara på varje query oberoende i genom att rekursivt testa alla möjligheter, och kolla i linjär tid om någon vunnit.
Saker att notera om implementationen: det är väldigt vanligt att när folk implementerar rekursiva spel, så har dom en parameter "är jag spelare 1 eller 2". Om man tänker till dock så kan vi göra som här, och inte ha det. Det finns problem där denna pyttelilla optimering krävs.
Ta förra lösningen och dp:a rec. Notera att vi inte behöver återställa dp:n mellan varje query, utan vi kan lika gärna spara den. Varje state tar att kolla på grund av is_valid, så vi får sammanlagt.
Vi måste kunna kolla is_valid i för att få ner det till . Lättaste sättet att göra detta är troligtvis att förberäkna alla giltiga intervall samtidigt i .
Jag pallar inte gå igenom alla specialfall. Just nu har vi två långsamma delar- en DP med kvadratiskt mycket state, och förberäkning av is_valid i . För fullösning behöver vi optimera ner båda till . Vi börjar med att förberäkna is_valid i . Vi säger att en intervall är om is_valid()=True. För att göra det behöver vi insé följande: om vi har ett intervall [l,r] som är bra, så kommer också vara True. Det vill säga, om ett intervall är bra kan vi utvidga det till höger, och det kommer fortsätta vara bra. Detta innebär att det räcker att beräkna för varje : vilket är det första där är bra?
Ett sätt att göra det är att för varje göra en binärsökning över . Då reduceras problemet till att "i ett intervall, finns det unika värden"? Eller, ekvivalent "hur många unika värden finns i ett visst intervall"? Detta går att lösa, men kräver för avancerade datastrukturer (persistenta segmentträd). Men om ni stöter på denna sortens "först går det inte, sen går det" borde ni alltid tänkte på binärsökning först!
För att lösa det måste vi insé nåt ännu starkare: låt f()=minsta där is_valid()=true. Då håller det att för alla . Det vill säga, om vi har ett intervall som är bra och flyttar åt höger ett steg, så kommer vi behöva flytta åt höger för att göra intervallet bra.
Detta låter oss lösa problemet med en tvåpekarslösning:
Hur håller vi snabbt koll på om intervallet är bra? Vi kan hålla koll på hur många vi har av varje smak i intervallet, och antalet unika smaker vi har. Att ändra detta tar . och rör sig gånger var sammanlagt, så vi får . Här är en lösning med förberäkning och dp:
Nu kan vi beräkna is_valid i för godtyckliga . Men hur ska vi optimera vår DP? Vi har kvadratiskt mycket state och det känns väldigt svårt att bli av med det. Vi kommer använda en vanlig strategi för problem som handlar om att spela ett spel optimalt: printa ut svaret och försöka hitta ett mönster. Det känns då rimligt att printa en 2D-matris för varje , som indikerar om svaret är 0,1,2 eller 2. Typiskt ser detta ut ungefär såhär:
Vad kollar du på exakt? Första raden är , andra raden osv. Första kolumnen är , andra osv.
För att göra det ännu mer lättläsligt ändrar vi noll till . och 2 till 0.
Har prickarna något att göra med ? Dvs, första där är bra. Låt oss plotta # om är bra, annars punkt.
Vi kan alltså märka att alla som var . i första bilden är exakt dom intervallen som är dåliga. Men vad händer bland alla 0/1or? Vi kan märka att för varje rad finns det ett första värde efter att intervallet blir bra. Detta värde kopieras sedan upp diagonalt! Alltså behöver vi bara hitta vem som vinner för states som ligger precis kanten bredvid ett intervall som inte är bra. DP:n kan bara kan röra sig eller , vilket motsvarar ner eller åt vänster. Därför kan den bara besöka som mest som mest tillstånd om vi bara beräknar dom precis på kanten. Notera att du egentligen behöver hitta den första som vinner i varje diagonal. Jag har markerat dessa med X:
När du väl har beräknat dessa i kan du svara på varje query i genom att kolla på vilken diagonal queryn befinner sig på.
Men varför stämmer detta mönstret? Låt =den som vinner för . Vad mönstret säger är egentligen att (övertyga dig själv om att detta är ekvivalent med diagonal-mönstret). Det vill säga, om vi utvidgar mönstret åt vänster och höger samtidigt vinner samma person. Detta beror på att spelare kan spegla drag. Låt säga att är en förlorande position att vara på.
Om vi är vid och det är dags för spelare 2 att göra ett drag, så är spelare 1 vinnande:
Jag lämnar implementationen av detta som en övning. Notera att du absolut inte kan försöka beräkna som inte är diagonalt bredvid ett # (intervall som inte är bra), för det är jättelätt att besöka hela rutnätet och få isåfall.