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

Temps requis

スクリーンショット 2020-01-16 12.16.14.png

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 **).

スクリーンショット 2020-01-16 16.48.15.png

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

Recommended Posts

AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes