[At Coder] Beginner Contest 175 ABCD python Solution introduction

Grades

It was my first time to participate. I answered ABC correctly, but I was frustrated by the D problem. The algorithm seems to be correct, but I couldn't get the bug to the end. The performance is 904. image.png

Impressions

I looked at various explanations, but I thought it was important how to interpret the problem simply (correcting the index from 0, moving the negative coordinates to the positive coordinates with absolute values, etc.). Also, I learned that there is a solution method that enumerates all of them without being particular about automation. And next time I want to solve the D problem.

Problem A

--My answer I counted the number of consecutive Rs

A.py



input_str = input()
cnt = 0
max_cnt = 0
for tmp in input_str:
    if tmp == "R":
        cnt +=1
        max_cnt = max(cnt, max_cnt)
    else:
        cnt = 0
        
print(max_cnt)

--Full enumeration There are at most 8 ways, so it's better not to bother with debugging if you list all of them. Reference: https://qiita.com/DaikiSuyama/items/c4ce6869cb897221bf8b

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)

--Pattern Focusing only on R, it seems to judge whether it applies to each continuous pattern. Reference: https://qiita.com/u2dayo/items/ce1b420344e451560b42

A__.py


s = input()
ans = 0

for i in range(1, 4):
    p = "R" * i
    if p in s:
        ans = i

print(ans)

B problem

I think the points were as follows. (1) In multiple loops, the minimum value of the inner loop should be the outer current value + 1. ② I googled because I don't know the conditions of the triangle

B.py


N = int(input())
input_list = list(map(int, input().split()))
pair_list = []
def triangle_check(a,b,c):
    return all([a+b>c, b+c>a, c+a>b, a!=b, b!=c,c!=a])
 
if N < 3:
    print(0)
else:
    for i in range(N):
        for j in range(i+1,N):
            for k in range(j+1,N):
                if triangle_check(input_list[i],input_list[j],input_list[k]):
                    pair_list.append([input_list[i],input_list[j],input_list[k]])
    print(len(pair_list))

By the way, I misunderstood that it was a more advanced problem of counting only unique pairs of length combinations, and I lost time. In that case, it was implemented using the following code. Reference: https://medium.com/@yamasaKit/2-python%E3%81%A7list%E3%81%AE%E4%B8%AD%E3%81%AElist%E3%82%92unique%E3%81 % AB% E3% 81% 99% E3% 82% 8B% E6% 96% B9% E6% B3% 95-f38d20e6674f

del_list_dup.py


duplicated_data = [tuple(d) for d in duplicated_data]
unique_data = set(duplicated_data)
unique_data = [list(d) for d in unique_data]

C problem

I think the points were as follows.

--Absolute value of initial value X --When you move toward the origin, you have branched depending on whether you can reach the origin. --If you cannot reach the origin, move as close as possible --If you can reach it, move it until just before it reaches and determine how many times you can move. --If you repeat around the origin an even number of times, the movement will be canceled and will not change from the original location. --In the case of an odd number of times, it will be the last one move for the above reason.

c.py


X, K, D = list(map(int, input().split()))
X = abs(X)
syo, amari = divmod(X, D)
if amari > (D-amari):
    syo = syo +1
if syo >= K:
    print(X - K*D)
else: 
    remain_num = K - syo
    position = abs(X - syo*D)
    if remain_num%2 == 1:
        position = abs(position-D)
    print(position)

D problem

(The answer is not correct. There is a test case that becomes RE, so we will fix the bug as soon as the test case is released.) I think the points were as follows.

--Loop detection --Branch when the value goes up and when it goes down for each loop --If it goes down for each loop, it is a loss if you repeat the loop, so find the maximum value in the first loop --If you want to go up for each loop, add the score of the loop up to one before the last loop and the maximum value in the section of one before the last loop + the last loop. --The reason for putting the previous loop in the maximum value search section is that if you loop with a score such as -1-> -2-> 100, and the last loop ends with -2 due to K, the last This is because it is better to finish with 100, which is one before the loop of. --The input index starts from 1, but it is modified to start from 0 for the convenience of the program.

d.py


import numpy as np
N,K = list(map(int, input().split()))
input_list = list(map(int, input().split()))
input_list = list(np.array(input_list)-1)
c_list = list(map(int, input().split()))
 
def roop_func(l, i, start, return_list=[]):
    return_list.append(l[i])
    if l[i] == start:
        return return_list 
    return roop_func(l, l[i],start, return_list)
 
total_best = -100000000000000000000
for start in range(N):
    p_list = roop_func(input_list, start, start,[])
    epoc = sum([c_list[i] for i in p_list])
    if epoc <= 0: #When it goes down every time it turns
        best = c_list[p_list[0]]
        current_score = c_list[p_list[0]]
        for i in range(1, min(K, len(p_list))):
            current_score += c_list[p_list[i]]
            if best < current_score:
                best = current_score
    else: #When it goes up every time it turns
        syo,amari = divmod(K, len(p_list))
        base = (syo-1) * epoc
        tmp = p_list
        p_list.extend(p_list[:amari])
        tmp2 = p_list
        best = c_list[p_list[0]] + base
        current_score = c_list[p_list[0]] + base
        for i in range(1, len(p_list)):
            current_score += c_list[p_list[i]]
            if best < current_score:
                best = current_score
    if best > total_best:
        total_best = best
        
print(total_best)

Recommended Posts

[At Coder] Beginner Contest 175 ABCD python Solution introduction
[Python] [BFS] At Coder Beginner Contest 168-D [.. Double Dots]
[Python] ABC159D (High School Mathematics nCr) [At Coder]
[Python] Competitive template [At Coder]
Atcoder Beginner Contest 152 Kiroku (python)
[Professional competition] I tried At Coder Beginner Contest 175 (A ~ C)
[At Coder] ABC085C --Otoshidama's Python answer
(Python) ABC162-D Consideration log and solution
AtCoder Beginner Contest 174 C Problem (Python)
At Coder (2020/09/08)
Solve AtCoder Beginner Contest 170 D --Not Divisible (ABC170D) with python (Eratosthenes sieve)
AtCoder Beginner Contest: D Question Answers Python
[Python] ABC175D
[Python] ABC133B (upper right triangle problem) [At Coder]
Beginner ABC154 (Python)
AtCoder Beginner Contest 177
Beginner ABC156 (Python)
Introduction of Python
python beginner memo (9.2-10)
AtCoder Beginner Contest 179
python beginner memo (9.1)
Python beginner notes
[Python] DP ABC184D
[Beginner] Python array
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
Solve AtCoder Beginner Contest159 D --Banned K (ABC159D) with python (count is too slow!)
Beginner ABC155 (Python)
AtCoder Beginner Contest 173
python at docker
[Beginner] Python functions
Beginner ABC157 (Python)
PyQ ~ Python Beginner ~
Atcoder Beginner Contest 153
Fill at Coder
Python beginner memo (2)
[Python] UnionFind ABC177D
Python beginner Zundokokiyoshi
At Coder # 1 at midnight
Introduction of Python
[Python] AGC043A (Problem reading comprehension and DP) [At Coder]
AtCoder Beginner Contest 176 C Problem "Step" Explanation (Python3, C ++, Java)
[Professional competition practice] I tried At Coder Beginner Selection