AtCoder Beginner Contest 073 Revue des questions précédentes

Temps requis

Impressions

Le problème D était un peu difficile en Python et est devenu 2 pena, mais j'ai trouvé que 10 ^ 7 de la méthode WF est serré. Plus tard, quand je l'ai réécrit en C ++ avec D, l'instruction for était gênante et j'étais fatigué d'écrire include, alors j'ai pensé que je devais bientôt créer un modèle.

Problème A

Il est plus facile de gérer la chaîne de caractères telle quelle.

answerA.py

n=input()
print("Yes" if "9" in n else "No")

Problème B

C'est un peu ennuyeux si vous avez un siège, alors peut-être que vous utiliserez la méthode Imosu? ?? Il suffit de compter ce problème tel qu'il est

answerB.py

n=int(input())
cnt=0
for i in range(n):
    l,r=map(int,input().split())
    cnt+=(r-l+1)
print(cnt)

Problème C

Puisqu'il est vérifié à plusieurs reprises s'il est couvert ou non, il est bon de simuler en utilisant le type d'ensemble qui peut ajouter ou supprimer tel que défini avec O (1). La solution Writer trie et applique la fonction groupby pour compter le nombre impair de chaque nombre.

answerC.py

n=int(input())
s=set()
for i in range(n):
    a=int(input())
    if a in s:
        s.remove(a)
    else:
        s.add(a)
print(len(s))

answerC_writer.py

n=int(input())
s=[int(input()) for i in range(n)]
s.sort()
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2
s=groupby(s)
l=len(s)
cnt=0
for i in range(l):
    cnt+=s[i][1]%2
print(cnt)

Problème D

Le problème avec ce problème est de trouver la distance la plus courte lors de la visite des villes R ** dans un ordre approprié . D'abord, j'ai trouvé la méthode WF parce que j'ai trouvé la distance la plus courte (+ cela semblait être à temps quand j'ai vu la contrainte). Après avoir trouvé l'itinéraire le plus court entre tous les points par la méthode WF, il est nécessaire de considérer l'ordre car R villes sont visitées dans l'ordre, mais ** R vaut 8 au plus et 8! = 40320 ** Trouver la commande ne nécessite pas beaucoup de calcul. Je voulais donc dire que ce problème était résolu, mais ** cela ne fonctionnait pas de cette façon lorsqu'il était implémenté naïf en Python ** Je ne savais pas si je pouvais le faire plus vite.) Donc, quand j'ai traduit le code écrit en Python en C ++ tel quel, j'ai pu le faire à temps ( C'était environ 100 fois plus rapide que Python . Je pense que la boucle for de Python est vraiment lente. ). De plus, lorsque je l'ai essayé avec PyPy, j'ai pu le faire à temps ( environ 5 fois plus vite que Python **).

Cependant, si vous y réfléchissez bien, la méthode WF trouve l'itinéraire le plus court entre tous les points, mais au final, ce que vous voulez savoir est l'itinéraire le plus court entre chaque ville pour les villes R (<= 8) à visiter, donc * Il s'avère qu'il suffit ** de trouver l'itinéraire le plus court à partir des villes * R (puisqu'il s'agit d'un graphe non orienté pondéré, la distance de l'itinéraire le plus court ne change pas même si le point de départ et le point d'arrivée sont échangés). Par conséquent, si vous trouvez l'itinéraire le plus court de ces ** villes R par la méthode Dyxtra, vous pouvez écrire un programme assez rapide ** (je n'ai jamais écrit la méthode Dyxtra en Python, donc ici. Je vais l'omettre. Je peux l'écrire si j'en ai envie.)

1/19 post-scriptum

Quand j'ai évoqué les commentaires, j'ai pu le transmettre en Python. En définissant la fonction principale et en faisant toutes les variables des variables locales, les programmes Python peuvent être accélérés **.

answerD.py

import itertools
n,m,r=map(int,input().split())
rx=[int(i) for i in input().split()]
inf=100000000
wf=[[inf]*n for i in range(n)]
for i in range(n):
    wf[i][i]=0

for i in range(m):
    a,b,c=map(int,input().split())
    wf[a-1][b-1]=c
    wf[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if wf[i][j]>wf[i][k]+wf[k][j]:
                wf[i][j]=wf[i][k]+wf[k][j]
cnt=0
l=list(itertools.permutations([i for i in range(r)]))
cnt=inf
for i in l:
    cnt_sub=0
    for j in range(r-1):
        cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
    cnt=min(cnt,cnt_sub)
print(cnt)

answerD.cc

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#define INF 100000000000

signed main(){
  ll n,m,r;cin >> n >> m >> r;
  vector<ll> rx(r);for(int i=0;i<r;i++)cin >> rx[i];
  vector<vector<ll>> wf(n,vector<ll>(n,INF));
  for(int i=0;i<n;i++) wf[i][i]=0;
  for(int i=0;i<m;i++){
    ll a,b,c;cin >> a >> b >> c;
    wf[a-1][b-1]=c;
    wf[b-1][a-1]=c;
  }
  for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j]);
      }
    }
  }
  ll cnt=INF;
  vector<ll> v(r);for(int i=0;i<r;i++) v[i]=i;
  do{
    ll cnt_sub=0;
    for(int i=0;i<r-1;i++){
      cnt_sub+=wf[rx[v[i]]-1][rx[v[i+1]]-1];
    }
    cnt=min(cnt,cnt_sub);
  }while(next_permutation(v.begin(),v.end()));
  cout << cnt << endl;
}