[PYTHON] Codeforces Round # 594 (Div. 2) Bacha Review (29.10.)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
In D ** habe ich geweint, weil die Indizes nicht für immer übereinstimmten ... Infolgedessen konnte ich es lösen, wenn ich es nach dem Neuanordnen der Richtlinie gelöst habe. Daher möchte ich wissen, dass ** ich aus der Richtlinie neu erstellen werde, wenn ich in der Implementierung stecken bleibe **.
Problem A
Wenn Sie eine Kreuzung haben, lautet die $ x $ -Koordinate der Kreuzung $ x + p \ _i = -x + q \ _i \ leftrightarrow x = \ frac {q \ _i-p \ _i} {2} $. Die Bedingung dafür, dass dies eine ganze Zahl ist, ist, wenn $ p \ _i, q \ _i $ durch 2 geteilt wird und der Rest gleich ist. Daher (gerade Zahl in $ p $ enthalten) $ \ times $ (gerade Zahl in $ q $ enthalten) + (ungerade Zahl in $ p $ enthalten) $ \ times $ (in $ q $ enthalten) Die ungerade Zahl) ist die Antwort.
A.py
for _ in range(int(input())):
n=int(input())
p=list(map(int,input().split()))
m=int(input())
q=list(map(int,input().split()))
co0=0
for i in range(n):
co0+=(p[i]%2==0)
co1=n-co0
co2=0
for i in range(m):
co2+=(q[i]%2==0)
co3=m-co2
print(co0*co2+co1*co3)
B-Problem
Wenn die endgültigen Koordinaten $ (x, y) $ sind, sollte zur Maximierung von $ x ^ 2 + y ^ 2 $ nur eine von ** $ x, y $ so groß wie möglich sein ** (Hier nehmen wir an, dass $ x $ erhöht wird). Da die Seiten kurz zuvor rechtwinklig zur Seite platziert werden müssen, ** bleiben bis zu $ n- [\ frac {n} {2}] $ Sticks, die die $ x $ -Koordinaten erhöhen. Sie können als ** wählen. Wählen Sie daher beim Sortieren eines bestimmten Sticks den Stick vom kleinsten bis zum kleinsten $ [\ frac {n} {2}] $ -Stick als den, um die $ y $ -Koordinate zu erhöhen, und $ [\ frac {n } {2}] + 1 Am besten wählen Sie den Stick nach dem drittkleinsten Stick als denjenigen, der die $ x $ -Koordinaten erhöht.
B.py
n=int(input())
a=list(map(int,input().split()))
a.sort()
c,d=0,0
for i in range(n//2):
c+=a[i]
for i in range(n//2,n):
d+=a[i]
print(c**2+d**2)
C-Problem
Es ist ein schwieriges Problem, aber Sie können es durch Experimentieren sehen.
Ich würde gerne DP verwenden, um die Bedingung von 2 aufeinanderfolgenden Quadraten zu behandeln, aber ** normaler 2D-DP scheint schwierig zu sein **, weil $ n und m $ groß sind. Daher habe ich ein Experiment mit der Erwartung durchgeführt, dass es ** zum Teil regelmäßig ** entschieden wird.
Zu diesem Zeitpunkt, als ich ein Experiment mit Proben durchführte, stellte ich fest, dass ** wenn die erste Reihe entschieden würde, die nachfolgenden Reihen in der Reihenfolge ** entschieden würden. Wenn es sich beispielsweise um 5 Zeilen und 3 Spalten handelt, ist dies wie folgt.
Aus der obigen Abbildung können Sie ersehen, dass durch die Entscheidung für die erste Spalte die nachfolgenden Spalten ** eindeutig bestimmt ** werden. Sie können auch sehen, dass die ** ungeraden und geraden Zahlen das gleiche Spaltenmuster ** haben.
Es gibt jedoch einige Muster **, die nicht eindeutig bestimmt werden können. Das heißt, es ist ein Muster, in dem schwarze und weiße Zellen wie unten gezeigt versetzt sind. Für dieses Muster kann es mehr als eine der folgenden Spalten geben: (Ich werde hier nicht beweisen, dass es in anderen Mustern nicht mehrere Möglichkeiten gibt, aber es kann durch die Tatsache bewiesen werden, dass es im Fall von Zellen mit aufeinanderfolgenden Farben eindeutig bestimmt ist.)
Wenn das Muster, in dem sich die schwarzen Zellen in der ersten Zeile befinden, A ist und das Muster, in dem sich die weißen Zellen in der ersten Zeile befinden, B ist, sind im Fall von ** AA oder BB die nächsten Spalten B bzw. A. Muss sein **. Basierend auf dem oben Gesagten wird nach dem Ermitteln der Anzahl der schwarzen und weißen Quadrate in der ersten Zeile die Anzahl der Zeilen im Muster aus abwechselndem Schwarz und Weiß separat berechnet, und die Summe beträgt $. Sie können sehen, dass Sie ein Programm von O (n + m) $ schreiben können.
Ich habe zu viel Zeit aufgewendet, weil ich nach der Zusammenfassung der bisherigen Überlegungen nicht mit der Implementierung fortfahren konnte. Es ist ein Spiegelbild. Wie auch immer, wir werden die Implementierung unten betrachten. Sie müssen auch daran denken, durch $ 10 ^ 9 + 7 $ zu teilen.
① Wie man die erste Reihe entscheidet
Wenn sich Schwarz und Weiß in der ersten Reihe abwechseln, gibt es immer zwei Möglichkeiten, die in ② gezählt werden (daher ** hier ausgeschlossen **). Für andere Muster werden die Spalten danach eindeutig bestimmt. Betrachten Sie daher den folgenden DP, um zu sehen, wie viele schwarze und weiße Zellen in der ersten Zeile angeordnet sind (weiß, wenn $ j = 0 $, schwarz, wenn $ j = 1 $, $ k = 0,1 $). ist).
$ dp [i] [j] [k]: = $ (Anzahl der Zellen, die angeordnet sind, wenn $ k + 1 $ Zellen fortgesetzt werden, wenn die $ i $ -Linie bestimmt wird)
Zu diesem Zeitpunkt ist der Übergang wie folgt (abgekürzt).
(1) Wenn $ k = 0 $ Sie können entweder schwarze oder weiße Quadrate auswählen, sodass Sie zwei Übergänge von $ dp [i] [j] [k] $ berücksichtigen können.
(2) Wenn $ k = 1 $ Es kann nur einen Weg geben, eine andere Farbzelle aus $ dp [i] [j] [k] $ auszuwählen, da es nicht mehr als zwei in einer Reihe sein darf.
Nach Berücksichtigung des Übergangs ist (Summe von $ dp [n-1] $) -2 die Antwort.
(2) Es gibt verschiedene Möglichkeiten zu entscheiden, wann das Muster ein Muster ist, in dem sich schwarze und weiße Zellen in der ersten Reihe abwechseln.
Wenn Sie das Muster, in dem sich die schwarzen Quadrate in der oberen Reihe befinden, als A und das Muster, in dem sich die weißen Quadrate in der oberen Reihe befinden, als B betrachten, können Sie wie zuvor den folgenden DP festlegen ($ j = 0). Wenn $, A, $ j = 1 $, B, $ k = 0,1 $).
$ dp [i] [j] [k]: = $ (Anzahl der Spalten, die angeordnet sind, wenn $ k + 1 $ Muster von $ j $ fortgesetzt werden, wenn die Spalte $ i $ bestimmt wird)
Zu diesem Zeitpunkt ist der Übergang wie folgt (er wird ein wenig abgekürzt).
(1) Wenn $ k = 0 $ Sie können entweder Muster A oder B auswählen, sodass Sie sich zwei Übergänge von $ dp [i] [j] [k] $ vorstellen können.
(2) Wenn $ k = 1 $ Es kann nur einen Weg geben, ein anderes Spaltenmuster aus $ dp [i] [j] [k] $ auszuwählen, da es nicht mehr als eines in einer Reihe geben darf.
Nach Berücksichtigung des Übergangs (die Summe von $ dp [n-1] $) ist die Antwort.
Wie oben erwähnt, sollte die Gesamtzahl der Muster von ① und ② als Antwort berechnet werden. Sie können auch sehen, dass der in ① und ② ausgeführte DP der gleiche ist.
C.py
mod=10**9+7
n,m=map(int,input().split())
n,m=min(n,m),max(n,m)
dp=[[[0,0] for j in range(2)] for i in range(m)]
dp[0]=[[1,0],[1,0]]
for i in range(m-1):
for j in range(2):
for k in range(2):
if j==0 and k==0:
dp[i+1][j][1]+=dp[i][j][k]
dp[i+1][j+1][0]+=dp[i][j][k]
elif j==1 and k==0:
dp[i+1][j][1]+=dp[i][j][k]
dp[i+1][j-1][0]+=dp[i][j][k]
elif j==0 and k==1:
dp[i+1][j+1][0]+=dp[i][j][k]
else:
dp[i+1][j-1][0]+=dp[i][j][k]
for j in range(2):
for k in range(2):
dp[i+1][j][k]%=mod
ans=-2
for j in range(2):
for k in range(2):
ans+=dp[m-1][j][k]
ans%=mod
dp2=[[[0,0] for j in range(2)] for i in range(n)]
dp2[0]=[[1,0],[1,0]]
for i in range(n-1):
for j in range(2):
for k in range(2):
if j==0 and k==0:
dp2[i+1][j][1]+=dp2[i][j][k]
dp2[i+1][j+1][0]+=dp2[i][j][k]
elif j==1 and k==0:
dp2[i+1][j][1]+=dp2[i][j][k]
dp2[i+1][j-1][0]+=dp2[i][j][k]
elif j==0 and k==1:
dp2[i+1][j+1][0]+=dp2[i][j][k]
else:
dp2[i+1][j-1][0]+=dp2[i][j][k]
for j in range(2):
for k in range(2):
dp2[i+1][j][k]%=mod
for j in range(2):
for k in range(2):
ans+=dp[n-1][j][k]
ans%=mod
print(ans)
D1-Problem
Dies ist ein Problem, das nicht berücksichtigt und organisiert werden konnte. Es ist eine Schande, weil es die Art von Problem ist, die ich nicht am meisten fallen lassen möchte.
In diesem Problem beträgt $ N $ bis zu 500, sodass Sie sehen können, dass $ O (N ^ 3) $ in Ordnung ist und $ O (N ^ 4) $ nicht. Angenommen, Sie wechseln zwischen $ i $ th und $ j $ th und können alle ** zyklischen Verschiebungen mit $ O (N) $ für diese Klammer ** versuchen.
Hier ist die Bedingung für die Erstellung der Klammerzeichenfolge, dass ** "(" ist +1, ")" als -1 betrachtet wird und die kumulative Summe immer 0 oder mehr ist und das letzte Element 0 ** ist. Selbst wenn Sie hier tauschen, ändert sich die Anzahl von "(" und ")" nicht, sodass Sie nur überprüfen müssen, ob der Wert des Elements, das die kumulative Summe minimiert, 0 oder mehr ist **. Die zyklische Verschiebung ist auch leicht zu verstehen, wenn man sie betrachtet, während das erste Element wie unten gezeigt verschoben wird (Muster in Beispiel 1).
Daher ** ist es gut, wenn es bei einer zyklischen Verschiebung immer 0 oder mehr auf der rechten oder linken Seite ist **. Wenn die von vorne genommene kumulative Summe sum1 ist, ist die von hinten genommene kumulative Summe sum2, das von vorne genommene kumulative Minimum ist amin1 und das von hinten genommene kumulative Minimum ist amin2, der Index der Position ganz links ist $. Wenn k $, ist die Bedingung auf der rechten Seite $ amin2 [k + 1] -asum1 [k] \ geqq 0 $ und die Bedingung auf der linken Seite ist $ amin1 [k + 1] + asum2 [k] \ geqq 0 $. Wenn eine dieser Bedingungen erfüllt ist, kann gesagt werden, dass die Klammern eine zyklische Verschiebung sind (✳︎).
Aus dem oben Gesagten ist es ein ausreichend schnelles Programm, da es $ O (N) $ für die Vorberechnung der kumulierten Summe und der Beurteilung in jeder zyklischen Verschiebung ist.
(✳︎)… Mein Kopf brach im kumulativen Teil, aber es ist nicht so schwierig….
D.cc
//Debug-Optionen:-fsanitize=undefined,address
//Compileroptimierung
#pragma GCC optimize("Ofast")
//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//Makro
//für Schleife
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//Konstante
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //Einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
signed main(){
//Ausgabespezifikation der Anzahl der Bruchstellen
//cout<<fixed<<setprecision(10);
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
string s;cin>>s;
ll ma=0;pair<ll,ll> now={1,1};
if(n%2!=0 or ll(count(ALL(s),'('))!=ll(n/2)){
cout<<0<<endl;
cout<<"1 1"<<endl;
return 0;
}
vector<ll> checks(n);
REP(i,n){
if(s[i]=='('){
checks[i]=1;
}else{
checks[i]=-1;
}
}
REP(i,n){
REP(j,n){
vector<ll> check=checks;
swap(check[i],check[j]);
//Nehmen Sie die kumulierte Summe von vorne
vector<ll> asum1(n);asum1[0]=check[0];
REP(k,n-1)asum1[k+1]=asum1[k]+check[k+1];
//Nehmen Sie die kumulierte Summe von hinten
vector<ll> asum2(n);asum2[n-1]=check[n-1];
REPD(k,n-1)asum2[k]=asum2[k+1]+check[k];
//Nehmen Sie das kumulative Minimum von vorne(Kumulative Summe)
vector<ll> amin1(n);amin1[0]=asum1[0];
REP(k,n-1)amin1[k+1]=min(amin1[k],asum1[k+1]);
//Nehmen Sie das kumulative Minimum von hinten(Kumulative Summe)
vector<ll> amin2(n);amin2[n-1]=asum1[n-1];
REPD(k,n-1)amin2[k]=min(amin2[k+1],asum1[k]);
ll ans=0;
if(amin1[n-1]>=0)ans++;
REP(k,n-1){
if(amin2[k+1]-asum1[k]>=0 and amin1[k]+asum2[k+1]>=0){
ans++;
}
}
if(ma<ans){
ma=ans;
now={i+1,j+1};
}
}
}
cout<<ma<<endl;
cout<<now.F<<" "<<now.S<<endl;
}
Nach dem D2-Problem
Ich werde diesmal nicht lösen.
Recommended Posts