[PYTHON] AtCoder Beginner Contest 073 Review of past questions

Time required

Impressions

The D problem was a little difficult in Python and became 2 pena, but I found that 10 ^ 7 of the WF method is tight. Later, when I rewrote it in C ++ with D, the for statement was troublesome and I was tired of writing include, so I thought that I had to make a template soon.

Problem A

It is easier to handle the character string as it is.

answerA.py

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

B problem

It's a little annoying if the seat is covered, so maybe I'll use the potato method? ?? Just count this problem as it is

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

Since it is repeatedly checked whether or not it is covered, it is good to simulate using the set type that can add or remove such as set with O (1). The Writer solution sorts and applies the groupby function to count the odd number of each number.

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

The problem with this problem is to find the shortest distance when visiting R cities ** in an appropriate order . First, I came up with the WF method because I found the shortest distance (+ it seemed to be in time when I saw the constraints). After finding the shortest path between all points by the WF method, it is necessary to consider the order because R cities are visited in order, but since ** R is 8 at most and 8! = 40320 ** Finding the order does not require that much calculation. So I wanted to say that this problem was solved, but ** it didn't work this way when implemented naive in Python ** (it seems to work if you speed it up by a constant factor, but how do you do a triple loop? I didn't know if I could do it faster.) So, when I translated the code written in Python into C ++ as it was, I was able to make it in time ( It was about 100 times faster than Python . I feel that the for loop of Python is really slow. ). Also, when I tried it with PyPy, I was able to make it in time ( about 5 times faster than Python **).

However, if you think about it carefully, the WF method finds the shortest path between all points, but in the end, what you want to know is the shortest path between each town for the R (<= 8) towns you visit, so * It turns out that it is enough ** to find the shortest path starting from * R towns (since it is a weighted undirected graph, the distance of the shortest path does not change even if the start point and end point are exchanged). Therefore, if you find the shortest path from these ** R towns by Dijkstra's algorithm, you can write a program that is fast enough ** (I have never written Dijkstra's algorithm in Python, so here. I will omit it. I may write it if I feel like it.)

1/19 postscript

When I referred to the comments, I was able to pass it in Python. If you define the main function and make all variables local variables, you can speed up your Python program **.

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