[PYTHON] AtCoder Beginner Contest 074 Review of past questions

Time required

Impressions

Actually, I was doing other errands during the virtual console, so it actually ended about 15 minutes earlier. This time it was DP and WF, so I was able to solve it quickly.

Problem A

Except for white areas.

answerA.py

n=int(input())
print(n*n-int(input()))

B problem

Personally, if it's this long, I'll be discouraged from reading the problem statement ... You only have to consider the robots that are closer in order.

answerB.py

n=int(input())
k=int(input())
x=[int(i) for i in input().split()]
cnt=0
for i in range(n):
    cnt+=min(abs(k-x[i]),x[i])
print(2*cnt)

C problem

It was a slightly different type of DP, so I was at a loss for a moment. Personally, I think it's an interesting issue. I want to make the concentration as high as possible, but if it is too high, it will not dissolve completely, so I have to adjust the amount of sugar and water. However, when I tried to adjust the amount well and think about it, I found it troublesome to implement. Here, first, since there can only be multiples (30 ways) of 100 out of 0 to 3000, I thought that it would be better to decide the amount of water first and then fill the remaining amount with sugar. Here, you can think about how many times each water addition operation is performed, but in the end I want to know what amount of water can be made, so I checked all the amount of water that could be DP. Also, if you exclude the amount of water, you can see the amount of sugar that can be added, so I checked all the possible amounts of DP for water as well. With the above DP, we were able to check all possible amounts of water and sugar, so we will consider how much sugar can be added to each amount of water. At this time, it should be noted that the maximum amount of sugar that can be added is min (the amount that dissolves, the amount of beaker minus the amount of water). Implementing the above, the code is as follows. I'm glad that it was a surprisingly fast program.

answerC.py

a,b,c,d,e,f=map(int,input().split())
a=100*a
b=100*b
dp1=[0]*(f+1)
dp2=[0]*(f+1)
for i in range(f+1):
    if i%a==0:
        if i+a<=f:
            dp1[i+a]=1
for i in range(f+1):
    if i==0 or dp1[i]==1:
        if i+b<=f:
            dp1[i+b]=1
for i in range(f+1):
    if i%c==0:
        if i+c<=f:
            dp2[i+c]=1
for i in range(f+1):
    if i==0 or dp2[i]==1:
        if i+d<=f:
            dp2[i+d]=1

ans=[-1,-1,-1]
for i in range(f+1):
    if dp1[i]==1:
        x=min(f-i,(i//100)*e)
        k=-1
        for j in range(x,-1,-1):
            if dp2[j]==1 or j==0:
                k=j
                if ans[0]<100*k/(i+k):
                    ans=[100*k/(i+k),i+k,k]
                break
print(str(ans[1])+" "+str(ans[2]))

D problem

Do you feel that there are many old problems and graph problems? First, I doubt the WF or Dijkstra's algorithm because it is clearly a positive weighted undirected graph (and I choose WF because it can be solved without using the Dijkstra's algorithm. The Dijkstra's algorithm takes time to write. Because it takes.). First, consider the case where the output is -1, which is the easiest to think about. At this time, it can be said that ** $ A_ {u, v} $ is not the length of the shortest path from city u to city v **, so it can be said that there exists ** All you have to do is make sure that there are u, v that update from the state of $ A_ {u, v} $. Then, if the output is not -1, $ A_ {u, v} $ is the length of the shortest path from city u to city v for any u, v. Here, first ** assume that there is a shortest path between all cities ** and perform the WF method. At this time, if the distance when going directly from city i to city j and when going through another city is the same (```a [i] [j] == in the code below Consider a [i] [k] + a [k] [j] `` `). At this time, you can see that ** the shortest route can be realized even if you go through another city, so there is no need for a road to exist between those cities **. Therefore, the path in such cases can be deleted (I marked the path as 1). If you add this mark, you only need to count the roads that are not marked at the end, so the code is as follows (what you want is the total distance of the roads and divide by 2 at the end. Don't forget). By the way, I used C ++ because I can't make it in time by using the WF method normally. If you feel like it, you can use Python as well.

answerD.cc

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

signed main(){
  ll n;cin >> n;
  vector< vector<ll> > a(n,vector<ll>(n,0));
  vector< vector<ll> > b(n,vector<ll>(n,0));
  for(ll i=0;i<n;i++)for(ll j=0;j<n;j++) cin >> a[i][j];
  bool f=false;
  for(ll k=0;k<n;k++){
    for(ll i=0;i<n;i++){
      for(ll j=0;j<n;j++){
        if(a[i][j]>a[i][k]+a[k][j]){
          f=true;
        }else if(i!=j and i!=k and j!=k and a[i][j]==a[i][k]+a[k][j]){
          b[i][j]=1;
        }
      }
    }
  }
  if(f){
    cout << -1 << endl;
  }else{
    ll cnt=0;
    for(ll i=0;i<n;i++){
      for(ll j=0;j<n;j++){
        if(b[i][j]==0){
          cnt+=a[i][j];
        }
      }
    }
    cout << ll(cnt/2) << endl;
  }
}