[PYTHON] AtCoder Beginner Contest 074 Revue des questions précédentes

Temps requis

Impressions

En fait, je faisais d'autres courses pendant le bachacon, donc ça s'est terminé environ 15 minutes plus tôt. Cette fois, c'était DP et WF, donc j'ai pu le résoudre rapidement.

Problème A

Sauf pour les zones blanches.

answerA.py

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

Problème B

Personnellement, si c'est aussi long, je serai découragé de lire l'énoncé du problème ... Vous n'avez qu'à considérer le robot le plus proche dans l'ordre.

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)

Problème C

C'était un type de DP légèrement différent, donc j'étais perdu pendant un moment. Je pense personnellement que c'est une question intéressante. Je veux rendre la concentration aussi élevée que possible, mais si elle est trop élevée, elle ne se dissoudra pas complètement, je dois donc ajuster la quantité de sucre et d'eau. Cependant, lorsque j'ai essayé de bien ajuster le montant et d'y réfléchir, j'ai trouvé cela difficile à mettre en œuvre. Ici, d'abord, comme il ne peut y avoir que des multiples (30 façons) de 100 sur 0 à 3000, j'ai pensé qu'il serait préférable de décider d'abord de la quantité d'eau, puis de remplir la quantité restante de sucre. Ici, vous pouvez penser au nombre de fois que chaque opération doit ajouter de l'eau, mais à la fin je veux savoir quelle quantité d'eau peut être produite, j'ai donc vérifié toute la quantité d'eau qui pourrait être DP. De plus, si vous excluez la quantité d'eau, vous pouvez voir la quantité de sucre qui peut être ajoutée, j'ai donc également vérifié toutes les quantités possibles de DP pour l'eau. Avec le DP ci-dessus, nous avons pu vérifier toutes les quantités possibles d'eau et de sucre, nous allons donc considérer la quantité de sucre pouvant être ajoutée à chaque quantité d'eau. À ce stade, il convient de noter que la quantité maximale de sucre qui peut être ajoutée est min (la quantité qui se dissout, la quantité de bécher moins la quantité d'eau). Le code suivant implémente ce qui précède. Je suis content que ce soit un programme étonnamment rapide.

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]))

Problème D

Pensez-vous qu'il existe de nombreux anciens problèmes et problèmes de graphes? Tout d'abord, je doute de la méthode WF et de la méthode Dyxtra car il s'agit clairement d'un graphe non orienté pondéré positif (et je choisis WF car il peut être résolu sans utiliser la méthode Dyxtra. La méthode Dyxtra prend du temps à écrire. Parce qu'il faut.). Tout d'abord, considérons le cas où la sortie est -1, ce qui est le plus facile à penser. À ce stade, on peut dire que ** $ A_ {u, v} $ n'est pas la longueur du chemin le plus court de la ville u à la ville v **, on peut donc dire qu'il existe **, donc la méthode WF a été utilisée en premier. Tout ce que vous avez à faire est de vous assurer qu'il y a u, v qui sont mis à jour à partir de l'état de $ A_ {u, v} $. Ensuite, si la sortie n'est pas -1, $ A_ {u, v} $ est la longueur de l'itinéraire le plus court de la ville u à la ville v pour tout u, v. Ici, supposons d'abord ** qu'il existe un itinéraire le plus court entre toutes les villes ** et exécutez la méthode WF. A ce moment, si la distance en allant directement de la ville i à la ville j et en passant par une autre ville est la même (```a [i] [j] == dans le code ci-dessous Considérons a [i] [k] + a [k] [j] ``). À ce stade, vous pouvez voir que ** l'itinéraire le plus court peut être réalisé même si vous passez par une autre ville, il n'est donc pas nécessaire qu'une route existe entre ces villes **. Par conséquent, le chemin dans de tels cas peut être supprimé (j'ai marqué le chemin comme 1). Si vous ajoutez cette marque, il vous suffit de compter les routes qui ne sont pas marquées à la fin, donc le code est le suivant (ce que vous voulez, c'est la distance totale des routes et divisez par 2 à la fin. N'oubliez pas). Au fait, j'ai utilisé C ++ car la méthode WF ne suffit pas. Si vous en avez envie, vous pouvez également utiliser Python.

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;
  }
}