[PYTHON] AtCoder Anfängerwettbewerb 178 Bewertung
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Auch diesmal war das Ergebnis enttäuschend. Das E-Problem hat lange gedauert, ohne auf meine Politik einzugehen.
Ich bedauere das F-Problem, weil es lange gedauert hat, es zu implementieren und zu versuchen, mit Set Gier zu lügen, obwohl ich etwas Zeit hatte. ** Mach keine Gier mit richtigen Gefühlen **. Außerdem war dieses Problem ** eigentlich ein Knebelproblem **, und die richtige Antwort war das, was ich für nicht die Lösung hielt. Ich bereue zu viel ...
Auch diesmal war es ein enttäuschendes Ergebnis, aber ich habe das Gefühl, dass der Boden allmählich an Stärke gewinnt. Deshalb möchte ich mein Bestes geben, ohne aufzugeben. Wahrscheinlich werde ich in der Lage sein, die Welle zu reiten, wenn ich etwas über die gelbe Leistung sagen kann, also werde ich mich widmen.
Problem A
Ich habe versucht, es einfach zu schreiben und bin gescheitert.
A.py
print(1 if int(input())==0 else 0)
B-Problem
** Da gezeigt werden kann, dass der Wert bei Auswahl des Endes größer ist als bei Auswahl des Nicht-Endteils **, wird der Maximalwert der vier Arten der Kantenmultiplikation berechnet.
B.py
a,b,c,d=map(int,input().split())
print(max(a*c,a*d,b*c,b*d))
C-Problem
** Die Existenzbedingung besteht darin, die Verweigerung und die komplementäre Menge zu berücksichtigen **. Das heißt, außer wenn nur 1 ~ 9 aus dem Ganzen ausgewählt ist ($ 10 ^ n
C.py
n=int(input())
mod=10**9+7
print((pow(10,n,mod)-2*pow(9,n,mod)+pow(8,n,mod)+2*mod)%mod)
D Problem
** Wenn Sie die Länge der Sequenz kennen, wird dies anscheinend durch doppelte Kombinationen entschieden **. Hier beträgt die Länge der Sequenz höchstens $ [\ frac {n} {3}] $ **, vorausgesetzt, alle Begriffe sind 3 oder mehr. Außerdem ** möchte ich doppelte Kombinationen 0 oder mehr ** erstellen, also subtrahiere 3 von allen Begriffen. Wenn die Länge der Zahlenspalte $ x $ beträgt, betrachten Sie daher den Fall, in dem die Summe $ s-3x $ beträgt und alle Zahlen 0 oder mehr sind. Zu diesem Zeitpunkt kann es als das Problem des Anordnens von ** $ s-3x $ Kugeln und $ x-1 $ Partitionen ** umformuliert werden, und die Gesamtzahl der Kombinationen beträgt $ _ {s-3x + x-1} C _ { Es wird s-3x} $. Da ich den Rest von $ 10 ^ 9 + 7 $ finden möchte, habe ich auch [Berechnung des Binomialkoeffizienten durch inverses Element] verwendet (https://qiita.com/DaikiSuyama/items/32706bc87c748edc301d).
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
ll fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];
//Eine Tabelle erstellen
void COMinit() {
fac[0]=fac[1]=1;
finv[0]=finv[1]=1;
inv[1]=1;
FOR(i,2,MAXR){
fac[i]=fac[i-1]*i%MOD;
inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
finv[i]=finv[i-1]*inv[i]%MOD;
}
}
//Berechnung des Binomialkoeffizienten
ll COM(ll n,ll k){
if(n<k)return 0;
if(n<0 || k<0)return 0;
return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
COMinit();
ll s;cin>>s;
ll ans=0;
FOR(x,1,ll(s/3)){
ll k=s-3*x;
ans+=COM(k+x-1,k);
ans%=MOD;
}
cout<<ans<<endl;
}
E Problem
** Es schien schwierig und ich verlor meine Konzentration **. Obwohl es eine Folgetheorie ist, kann ich das F-Problem lösen, wenn ich dieses Problem mit hoher Geschwindigkeit bestehen kann. Deshalb möchte ich mit einem Bacha trainieren, damit ich meine Konzentration aufrechterhalten kann.
Während des Wettbewerbs konnte ich es auch lösen, weil ich diesen Artikel von Google gefunden habe. Diese Frage ist nicht einfach, daher haben viele Leute gegoogelt, um die richtige Antwort zu erhalten.
Zuerst,Oder fixieren Sie einen der beiden Punkte
E.py
n=int(input())
xy=[list(map(int,input().split())) for i in range(n)]
ans=[]
cand=[xy[i][0]+xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[-xy[i][0]+xy[i][1]for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[-xy[i][0]-xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[xy[i][0]-xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
print(max(ans))
F Problem
Zunächst dachte ich über eine gierige Methode des Austauschs nach, damit die vorherigen Elemente nicht in der richtigen Reihenfolge übereinstimmen, aber ich lehnte sie ab, weil sie ungerechtfertigt zu sein scheint. Als nächstes, wenn ich die Tatsache ausnütze, dass sie nicht übereinstimmen sollten und dass sie alle sortiert sind, dachte ich, dass ** durch Umkehren nur die Mitte ** übereinstimmen würde (✳︎). Ich lehnte es jedoch ab **, weil ich es für zu einfach hielt. Danach war die Methode, die ich mir ausgedacht hatte, die Reihenfolge der meisten zu bestimmen. Ich habe diese Methode implementiert, obwohl ich sie nicht rechtfertigen konnte. Außerdem war die Implementierung etwas schwer und wurde während des Wettbewerbs nicht abgeschlossen.
Als ich mir nach dem Wettbewerb die Antworten anderer Leute auf Twitter ansah, bemerkte ich ** die Süße meiner Überlegungen ** während des Wettbewerbs. ** Es ist so einfach, dass ich es abgelehnt habe **. Ich habe die Angewohnheit aufzuhören zu denken **, wenn die Lösung eines Problems zu schwierig oder zu einfach ist **, also würde ich gerne aufhören. Wenn Sie mit der Betrachtung von (✳︎) fortfahren, kann dieses Problem wie folgt gelöst werden.
Überlegen Sie zunächst, wie viele 1 ~ $ n $ jeweils $ A $ und $ B $ insgesamt sind. Wenn mehr Elemente als $ n $ vorhanden sind, ist es nicht möglich, eine Zahlenfolge zu erstellen, die dem Thema entspricht. Da sich aus dem Prinzip ergibt, wird Nein ausgegeben.
In diesem Fall zuerst B gemäß der vorherigen Richtlinie umkehren. Zu diesem Zeitpunkt gibt es nur einen ** $ p $, der zu $ (\ forall x \ in [l, r]) wird (A \ _x = B \ _x = p) $. Im Gegenteil, wenn es nicht existiert, wird es den Zweck erfüllen, wenn es so ausgegeben wird, wie es ist. Zu diesem Zeitpunkt gilt auch $ (\ forall x \ notin [l, r]) (A \ _x \ neq B \ _x) $. (Beweis wird weggelassen)
Tauschen Sie nun ** gegen ein beliebiges Element von ** $ x \ in [l, r] $. Dieser Swap liegt zwischen $ x (\ in [l, r]) $ und $ y (\ notin [l, r]) $. Dieser Austausch kann auch für $ y (\ notin [l, r]) $ durchgeführt werden, wenn es sich um $ A \ _y \ neq p $ und $ B \ _y \ neq p $ handelt. Zwei Elemente stimmen nie mit ihren jeweiligen Indizes überein **. Da $ p $ in $ A $ und $ B $ kleiner als $ n $ ist, ist es außerdem möglich, gegen $ x (\ in [l, r]) $ (*) zu tauschen. * Es ist gut zu denken, dass Sie tauschen können, so dass $ p $ in allen Indizes vorhanden ist, wenn Sie auf das Maximum tauschen **.).
Aus dem Obigen wurde die Gültigkeit des Verfahrens zum Wiederholen des Austauschs zwischen dem überlappenden Teil und dem nicht überlappenden Teil in umgekehrter Reihenfolge gezeigt, so dass dies wie folgt implementiert wird.
F.py
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
from collections import Counter,deque
x,y=Counter(a),Counter(b)
for i in range(1,n+1):
if x[i]+y[i]>n:
print("No")
exit()
ans=b[::-1]
change=deque()
num=-1
now=deque()
for i in range(n):
if a[i]==ans[i]:
change.append(i)
num=ans[i]
else:
now.append(i)
if change==[]:
print("Yes")
print(" ".join(map(str,ans)))
exit()
while len(change):
q=now.popleft()
p=change.popleft()
if a[q]!=num and ans[q]!=num:
ans[q],ans[p]=ans[p],ans[q]
else:
change.appendleft(p)
print("Yes")
print(" ".join(map(str,ans)))
Recommended Posts