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

Benötigte Zeit

Impressionen

Das D-Problem war in Python etwas schwierig und wurde zu 2 Pena, aber ich fand, dass 10 ^ 7 der WF-Methode eng sind. Später, als ich es in C ++ in D umschrieb, war die for-Anweisung problematisch und ich hatte es satt, include zu schreiben, sodass ich dachte, ich müsste bald eine Vorlage erstellen.

Problem A

Es ist einfacher, mit der Zeichenfolge so umzugehen, wie sie ist.

answerA.py

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

B-Problem

Es ist ein wenig ärgerlich, wenn Sie einen Sitzplatz bekommen. Vielleicht verwenden Sie also die Imosu-Methode? ?? Zählen Sie dieses Problem einfach so wie es ist

answerB.py

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

C-Problem

Da wiederholt geprüft wird, ob es abgedeckt ist oder nicht, ist es sinnvoll, mit dem Mengen-Typ zu simulieren, der hinzugefügt oder entfernt werden kann, z. B. mit O (1). Die Writer-Lösung sortiert die Groupby-Funktion und wendet sie an, um die ungerade Zahl jeder Zahl zu zählen.

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)

D Problem

In diesem Problem wird die kürzeste Entfernung beim Besuch von R Städten ** in einer geeigneten Reihenfolge ** berechnet. Zuerst habe ich mir die WF-Methode ausgedacht, weil ich die kürzeste Entfernung gefunden habe (+ es schien rechtzeitig zu sein, als ich die Einschränkungen sah). Nachdem der kürzeste Weg zwischen allen Punkten nach der WF-Methode gefunden wurde, muss die Reihenfolge berücksichtigt werden, da R Städte in der richtigen Reihenfolge besucht werden, ** R jedoch höchstens 8 und 8! = 40320 ** Das Finden der Bestellung erfordert nicht so viel Berechnung. Ich wollte also sagen, dass dieses Problem gelöst wurde, aber ** es funktionierte nicht so, wenn es in Python naiv implementiert wurde ** (es scheint zu funktionieren, wenn Sie es um einen konstanten Faktor beschleunigen, aber wie machen Sie eine Dreifachschleife? Ich wusste nicht, ob ich es schneller machen könnte.) Als ich den in Python geschriebenen Code so wie er war in C ++ übersetzte, konnte ich ihn rechtzeitig erstellen (** Es war ungefähr 100 Mal schneller als Python . Ich denke, dass Pythons for-Schleife sehr langsam ist. ). Als ich es mit PyPy ausprobierte, konnte ich es rechtzeitig schaffen ( ungefähr fünfmal schneller als Python **).

Wenn Sie jedoch sorgfältig darüber nachdenken, findet die WF-Methode den kürzesten Weg zwischen allen Punkten. Am Ende möchten Sie jedoch den kürzesten Weg zwischen den einzelnen Städten kennen, den R (<= 8) Städte besuchen können. * Es stellt sich heraus, dass es ausreicht **, die kürzeste Route ab * R Städten zu finden (da es sich um eine gewichtete ungerichtete Grafik handelt, ändert sich die Entfernung der kürzesten Route nicht, selbst wenn Startpunkt und Endpunkt ausgetauscht werden). Wenn Sie also mit der Dyxtra-Methode den kürzesten Weg von diesen ** R-Städten finden, können Sie ein Programm schreiben, das schnell genug ist ** (ich habe die Dyxtra-Methode noch nie in Python geschrieben, also hier. Ich werde es weglassen. Ich kann es schreiben, wenn ich Lust dazu habe.)

1/19 Nachschrift

Als ich mich auf die Kommentare bezog, konnte ich sie in Python übergeben. Durch Definieren der Hauptfunktion und Festlegen aller Variablen zu lokalen Variablen können Python-Programme beschleunigt werden **.

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