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

Benötigte Zeit

Impressionen

Eigentlich habe ich während des Bachacons andere Besorgungen gemacht, also endete es ungefähr 15 Minuten früher. Diesmal waren es DP und WF, also konnte ich es schnell lösen.

Problem A

Mit Ausnahme von weißen Bereichen.

answerA.py

n=int(input())
print(n*n-int(input()))

B-Problem

Persönlich, wenn es so lange dauert, werde ich davon abgehalten, die Problemstellung zu lesen ... Sie müssen nur den nächstgelegenen Roboter in der richtigen Reihenfolge berücksichtigen.

answerB.py

n=int(input())
k=int(input())
x=[int(i) for i in input().split()]
cnt=0
for i in range(n):
    cnt+=min(abs(k-x[i]),x[i])
print(2*cnt)

C-Problem

Es war eine etwas andere Art von DP, also war ich für einen Moment ratlos. Ich persönlich halte das für ein interessantes Thema. Ich möchte die Konzentration so hoch wie möglich halten, aber wenn sie zu hoch ist, löst sie sich nicht vollständig auf, daher muss ich die Menge an Zucker und Wasser anpassen. Als ich jedoch versuchte, die Menge gut anzupassen und darüber nachzudenken, fand ich die Implementierung schwierig. Da es hier nur ein Vielfaches (30 Wege) von 100 von 0 bis 3000 geben kann, dachte ich, dass es besser wäre, zuerst die Wassermenge zu bestimmen und dann die verbleibende Menge mit Zucker zu füllen. Hier können Sie darüber nachdenken, wie oft bei jeder Operation Wasser hinzugefügt werden soll, aber am Ende möchte ich wissen, wie viel Wasser hergestellt werden kann, also habe ich die gesamte Wassermenge überprüft, die DP sein könnte. Wenn Sie die Wassermenge ausschließen, können Sie auch die Zuckermenge sehen, die hinzugefügt werden kann. Daher habe ich auch alle möglichen DP-Mengen auf Wasser überprüft. Mit dem oben genannten DP konnten wir alle möglichen Mengen an Wasser und Zucker überprüfen, sodass wir prüfen werden, wie viel Zucker zu jeder Menge Wasser hinzugefügt werden kann. Zu diesem Zeitpunkt sollte beachtet werden, dass die maximale Menge an Zucker, die hinzugefügt werden kann, min ist (die Menge, die sich auflöst, die Menge an Becherglas abzüglich der Menge an Wasser). Der folgende Code implementiert das Obige. Ich bin froh, dass es ein überraschend schnelles Programm war.

answerC.py

a,b,c,d,e,f=map(int,input().split())
a=100*a
b=100*b
dp1=[0]*(f+1)
dp2=[0]*(f+1)
for i in range(f+1):
    if i%a==0:
        if i+a<=f:
            dp1[i+a]=1
for i in range(f+1):
    if i==0 or dp1[i]==1:
        if i+b<=f:
            dp1[i+b]=1
for i in range(f+1):
    if i%c==0:
        if i+c<=f:
            dp2[i+c]=1
for i in range(f+1):
    if i==0 or dp2[i]==1:
        if i+d<=f:
            dp2[i+d]=1

ans=[-1,-1,-1]
for i in range(f+1):
    if dp1[i]==1:
        x=min(f-i,(i//100)*e)
        k=-1
        for j in range(x,-1,-1):
            if dp2[j]==1 or j==0:
                k=j
                if ans[0]<100*k/(i+k):
                    ans=[100*k/(i+k),i+k,k]
                break
print(str(ans[1])+" "+str(ans[2]))

D Problem

Haben Sie das Gefühl, dass es viele alte Probleme und Grafikprobleme gibt? Zunächst bezweifle ich die WF-Methode und die Dyxtra-Methode, da es sich eindeutig um einen positiv gewichteten ungerichteten Graphen handelt (und ich wähle WF, weil es ohne Verwendung der Dyxtra-Methode gelöst werden kann. Die Dyxtra-Methode benötigt Zeit zum Schreiben. Weil es dauert.). Betrachten Sie zunächst den Fall, in dem die Ausgabe -1 ist, was am einfachsten zu bedenken ist. Zu diesem Zeitpunkt kann gesagt werden, dass ** $ A_ {u, v} $ nicht die Länge der kürzesten Route von Stadt u nach Stadt v ** ist, daher kann gesagt werden, dass es existiert **, daher wurde zuerst die WF-Methode verwendet. Sie müssen lediglich sicherstellen, dass u, v vorhanden sind, die vom Status $ A_ {u, v} $ aktualisiert wurden. Wenn die Ausgabe nicht -1 ist, ist $ A_ {u, v} $ die Länge der kürzesten Route von Stadt u nach Stadt v für jedes u, v. Nehmen Sie hier zunächst an, dass es eine kürzeste Route zwischen allen Städten gibt, und führen Sie die WF-Methode durch. Zu diesem Zeitpunkt, wenn die Entfernung direkt von Stadt i zu Stadt j und durch eine andere Stadt gleich ist (`a [i] [j] == im folgenden Code Betrachten Sie a [i] [k] + a [k] [j] `). Zu diesem Zeitpunkt können Sie sehen, dass ** die kürzeste Route auch dann realisiert werden kann, wenn Sie durch eine andere Stadt fahren, sodass zwischen diesen Städten keine Straße vorhanden sein muss **. Daher kann der Pfad in solchen Fällen gelöscht werden (ich habe den Pfad als 1 markiert). Wenn Sie diese Markierung hinzufügen, müssen Sie nur die Straßen zählen, die am Ende nicht markiert sind. Der Code lautet also wie folgt (Sie möchten die Gesamtentfernung der Straßen und am Ende durch 2 teilen. Vergiss nicht). Ich habe übrigens C ++ verwendet, weil die WF-Methode nicht ausreicht. Wenn Sie Lust dazu haben, können Sie auch Python verwenden.

answerD.cc

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

signed main(){
  ll n;cin >> n;
  vector< vector<ll> > a(n,vector<ll>(n,0));
  vector< vector<ll> > b(n,vector<ll>(n,0));
  for(ll i=0;i<n;i++)for(ll j=0;j<n;j++) cin >> a[i][j];
  bool f=false;
  for(ll k=0;k<n;k++){
    for(ll i=0;i<n;i++){
      for(ll j=0;j<n;j++){
        if(a[i][j]>a[i][k]+a[k][j]){
          f=true;
        }else if(i!=j and i!=k and j!=k and a[i][j]==a[i][k]+a[k][j]){
          b[i][j]=1;
        }
      }
    }
  }
  if(f){
    cout << -1 << endl;
  }else{
    ll cnt=0;
    for(ll i=0;i<n;i++){
      for(ll j=0;j<n;j++){
        if(b[i][j]==0){
          cnt+=a[i][j];
        }
      }
    }
    cout << ll(cnt/2) << endl;
  }
}