AtCoder Beginner Contest 073 Review of past questions

Time required

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

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

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

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

Recommended Posts

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