[PYTHON] AtCoder Beginner Contest 175 Review
This time's results
Impressions of this time
I got a blue performance for the first time in a long time ... It was the third blue performance for the first time in 3 months. If you can get the result as you can, you will get this much performance (should), so I want to improve my mentality. Also, I was able to pass the C problem at a fairly high speed, but as a result of ** excessively worrying about the ranking of the surroundings in the D problem and the E problem **, it took a considerable amount of time, so be careful after that. I want to
Problem A
Since there are only 3,2,1,0 outputs, we have divided the cases in each case. As far as I can see, there seems to be a cleaner solution, so I am conscious of solving problem A neatly.
A.py
s=input()
if s=="RRR":
print(3)
elif s=="RRS" or s=="SRR":
print(2)
elif s=="SSS":
print(0)
else:
print(1)
B problem
Search all three sides of the triangle. Also, in order to count without duplication, it is necessary to make range (n) → range (i + 1, n) → range (j + 1, n).
B.py
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n):
for j in range(i+1,n):
for k in range(j+1,n):
if l[i]+l[j]>l[k] and l[i]!=l[j] and l[j]!=l[k]:
ans+=1
print(ans)
C problem
Almost already mentioned. This problem.
The absolute value can be ** monotonically decreased ** at the beginning, and the operation is optimal, but when the absolute value of the coordinates becomes $ d $ or less (this time is $ e $), then * * It is best to go back and forth between $ e $ and $ de $ **.
Therefore, this round trip is determined by the even number of the remaining movements **, and the answer is $ e $ when the remaining number of movements when reaching $ e $ for the first time is even, and $ de $ when it is odd. I will.
C.py
x,k,d=map(int,input().split())
x=abs(x)
if x>k*d:
print(x-k*d)
else:
k-=x//d
x-=(d*(x//d))
ans=[x,abs(d-x)]
print(ans[k%2])
D problem
I tried to implement it carefully while commenting out, so I was able to find the corner case smoothly.
Move the frame according to the written number, but if you reach a certain square twice, you can see that ** the behavior after that is the same, so a cycle is likely to appear **.
Also, here we can see that there is always a cycle due to the constraint of ** permutation ** (the same number does not appear when recording the number of the cell traced when there is no cycle, but in the case of permutation You can see that it is impossible.)
Under this, we will follow the cells from each cell to the next, but since $ K $ is extremely large, it is necessary to ** calculate the cycle collectively **. Therefore, we first need to ** detect the cycle **. There seem to be several methods, but I prepared and implemented an array that records the squares that have already been traced ** and an array that records the order in which they were traced **. Specifically, select each cell as a starting point and try to repeat the process until the cell you have already traced appears. Also, ** calculate the part that is not included in the cycle first **, and if it is still less than $ K $, move on to the calculation of the cycle. (Since the number of movements is $ 1 $ or more and $ K $ or less, it is necessary to check whether the maximum value is updated ** every time the cell is traced.)
First of all, when you start to go around the cycle, there are cases where you cannot go around **, so we will classify the cases first. After this, consider whether or not to go around the cycle. First, calculate the score you will get in one round of the cycle. At this time, if the ** cycle score is negative **, there is no need to go through the cycle in the first place. However, even if you don't have to go through the cycle, there is a pattern ** where you can update the maximum value when you go around the middle of the cycle, so you need to check such a pattern. Next, if the score of the ** cycle is non-negative **, it is better to go around the cycle, so go around as much as you can. And I thought that I should try to move the mass for the last remaining part, but ** Actually, this method produces a WA pattern **. This means that even if the total score of the cycle is non-negative, ** there are patterns where it is better not to turn the last cycle ** (I do not show here that it is better to turn the non-last cycle). ). Therefore, you can follow such patterns by ** thinking only about the last cycle **, and you can cover all patterns by dividing into the above cases. (Here, I was able to discover WA by paying attention to ** whether to go around the cycle **.)
Also, I would like to be careful because the pattern problem of ** when performing operations in a batch is optimal but not optimal when only a part is taken out ** is sometimes seen and mistakes are hard to notice.
D.py
n,k=map(int,input().split())
#0-indexed
p=[i-1 for i in list(map(int,input().split()))]
c=list(map(int,input().split()))
#1 time or more and K times or less
ansF=-1000000000000000000
for i in range(n):
#What you have already followed
check=[False]*n
#The order of tracing
turns=[]
#now
now=i
while check[now]==False:
check[now]=True
turns.append(now)
now=p[now]
#answer(Now)
ans=0
#How many times out of k
#Update every time
spare=turns.index(now)
if spare>=k:
for j in range(k):
ans+=c[turns[j]]
ansF=max(ans,ansF)
continue
for j in range(spare):
ans+=c[turns[j]]
ansF=max(ans,ansF)
turns=turns[spare:]
spare=k-spare
#Cycle length
l=len(turns)
#Cycle sum(Too)
#Where to stop the cycle
x=0
for j in range(l):
x+=c[turns[j]]
#If the cycle does not go around in the first place
if spare<=l:
for j in range(spare):
ans+=c[turns[j]]
ansF=max(ans,ansF)
continue
#Sometimes it's better to cycle
#Some patterns should not be turned in the last cycle
if x>=0:
ans+=(x*(spare//l-1))
ansF=max(ans,ansF)
for j in range(l):
ans+=c[turns[j]]
ansF=max(ans,ansF)
for j in range(spare%l):
ans+=c[turns[j]]
ansF=max(ans,ansF)
#When it is better not to cycle
else:
for j in range(l):
ans+=c[turns[j]]
ansF=max(ans,ansF)
print(ansF)
E problem
With about 10 minutes remaining, I submitted the policy with confidence and then TLE. $ R \ times C \ times 4 \ simeq 3.6 \ times 10 ^ 7 $ So I submitted it because I thought it was barely possible even with PyPy, so I rewrote it with the intention of dying and submitted it about 5 minutes ago.
First of all, since it is a typical problem, I think it is easy to establish a basic policy. ** Search problem on the grid ** and ** The transition is clear **, ** Number of states ** seems to be good if you save the number of items picked up for each column (4 ways), DP Was established as a policy. Specifically, it is set as follows.
$ dp [i] [j] [k]: = $ (Maximum total value of items when the number of items selected in the line is $ k $ when the cell ($ i, j $) is reached)
There is a transition to the bottom and a transition to the right, but it is a little complicated, so ** case classification ** is necessary. Also, consider the transition from the state of $ dp [i] [j] [l]
(1) In the case of downward transition
Make a transition from the square ($ i, j
(2) In the case of transition to the right
Make a transition from the square ($ i, j
If the above transition is known, DP is initialized to 0, and if the item exists in the mass ($ 0,0 $), dp [0] [0] [1] = $ item [0] [0] $ If you don't forget to initialize with, just do 3D DP.
E.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll r,c,k;cin>>r>>c>>k;
vector<vector<ll>> item(r,vector<ll>(c,0));
REP(i,k){
ll x,y,z;cin>>x>>y>>z;
item[x-1][y-1]=z;
}
vector<vector<vector<ll>>> dp(r,vector<vector<ll>>(c,vector<ll>(4,0)));
if(item[0][0]>0)dp[0][0][1]=item[0][0];
REP(i,r){
REP(j,c){
REP(l,4){
if(l<3){
if(i!=r-1){
dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][l]);
if(item[i+1][j]>0)dp[i+1][j][1]=max(dp[i+1][j][0],dp[i][j][l])+item[i+1][j];
}
if(j!=c-1){
dp[i][j+1][l]=max(dp[i][j+1][l],dp[i][j][l]);
if(item[i][j+1]>0)dp[i][j+1][l+1]=max(dp[i][j+1][l+1],dp[i][j][l]+item[i][j+1]);
}
}else{
if(i!=r-1){
dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][l]);
if(item[i+1][j]>0)dp[i+1][j][1]=max(dp[i+1][j][0],dp[i][j][l])+item[i+1][j];
}
if(j!=c-1){
dp[i][j+1][l]=max(dp[i][j+1][l],dp[i][j][l]);
}
}
}
}
}
cout<<*max_element(ALL(dp[r-1][c-1]))<<endl;
}
F problem
I got an image of the policy by referring to the explanation, so I will solve it within a few days.
Recommended Posts