AtCoder I don't know diary_1 ABC148D

Introduction

I participated in the AtCoder contest for the first time. I solved the past questions just a little bit. I'm really a beginner, but I think C is so easy and D can be used. I thought, so I solved it. It didn't work in time. The answer of a programming strong man (Tsuyobito) is too smart for beginners. e? Is there a way to receive such input? !! Is it an ant how to output it? !! It will be like. I will devote myself. For the time being, I would like to think about why the algorithm I thought was not good. It doesn't make sense if you can't write down the operations you think of as code. The problem is from the D problem of ABC148. Here's a quote (I'm going to follow the rules, but please let me know if it's wrong).

(Addition that doesn't matter) I haven't bought an ant book yet. Because I have a small amount of money. If you have it in the school library, you may rent it for the year-end and New Year holidays. I thought I wanted him to buy it, but I made a mistake in the direction, so I was at home. ・ Algorithm textbook-Basics and applications of algorithms shown in practical programs- ・ Algorithm puzzles-Introduction to math puzzles for programmers- I wanted to lend me this book and learn the algorithm first, so I thought it was okay. The former book is older than me ...

D - Brick Break

N bricks are lined up in a horizontal row. The integer a i </ sub> is written on the i (1 ≤ i ≤ N) th brick from the left. You can choose and crush any brick of N-1 or less. As a result, K bricks remain. At this time, for any integer i (1 ≤ i ≤ K), Mr. Sunuke is satisfied when the integer written in the i-th one from the left among the remaining bricks is i. Please output the minimum number of bricks that Mr. Sunuke needs to crush to be satisfied. If that is not possible no matter how you crush it, print -1 instead.

Thoughts

(1) It seems that the numbers should remain in order from 1. ② Then, should I check it with the index from the front and erase the different one [^ 1] How do you decide on a proper noun? And what was the element of the metaphor and why? Such. [^ 1]: This is a mistake. You just have to count it. What is needed in the first place is not the final sequence. Read the problem properly

First time

n = int(input())
a = list(map(int, input().split()))
ans = 0
i = 0
while i + 1 <= len(a):
    #index+Delete if 1 is different from the list element
    if a[i] != i + 1:
        del a[i]
    #If they are the same, check the next element
    else:
        i += 1
#Impossible if you erase everything
if len(a) == 0:
  print(-1)
#If you subtract the remaining elements, it will be the number you broke
else:
    print(n - len(a))

To TLE in some test cases. Hmmm I thought about it for a while, but I don't know what's wrong ... I'm not confident that it's definitely right. It's not TLE in an infinite loop, but maybe it's time over in a test case where the sequence is too long? I don't fully understand how this works. After that, I was worried about breaking it on the way, but it didn't matter at all, so I omitted it.

4th

③ It might not have been good because I erased them one by one. You can erase it all at once. So,

n = int(input())
a = list(map(int, input().split()))
ans = 0
i = 0
while i + 1 <= len(a):
    #index+If 1 is different from the list element
    if a[i] != i + 1:
        #Check if there is the correct element
        if i + 1 in a:
            #Delete before the correct element
            del a[i:a.index(i + 1)]
        #Delete all if there is no correct element
        else:
            del a[i:]      
    #index+If 1 is the same as the element in the list, go to the next element
    else:
        i += 1
#Impossible if you erase everything
if len(a) == 0:
  print(-1)
#If you subtract the remaining elements, it will be the number you broke
else:
    print(n - len(a))

I passed by this. You did it. Answer of strong man (Tsuyobito)

It doesn't matter at all, but you can read it separately. ~~ It looks like a madman. ~~ [^ 2]

――The shortest code at the moment, I cried because I didn't understand the meaning at all [^ 3] [^ 4] --I'm checking the input directly without even putting the list in the variable --Place a variable that corresponds to the correct element, check the elements of the list from the front, and if they are the same, add +1 to the next ――You can use if in print ... What is this ...?

For some reason I was trying to find a clean line of bricks, but I felt like I just had to count the number of clean bricks.

It's called a ternary operator

It seems that you can write if and else statements in one line.

(If true, return this) if (under this condition) else (If false, this is the case)

Like this. I don't even need a colon. It's convenient. So the last 4 lines

print(-1 if len(a) == 0 else n - len(a))

It's fine. I see! Learning. [^ 2]: Compliance [^ 3]: Exaggerated expression [^ 4]: It's not the purpose to write the strongest code right now, it's important to solve the problem as far as you can understand, so don't worry about it.

Recommended Posts

AtCoder I don't know diary_1 ABC148D
AtCoder I don't know diary_2 ABC148E
AtCoder I don't know diary_3 ABC149C, D
AtCoder I don't know diary_4 ABC081B, 087B, 083B (from ABS)
I don't know the value error
I don't understand join
Atcoder Beginner Contest 146 Participation Diary
I participated in AtCoder (ABC158)
I don't know how to get query parameters on GAE / P
I didn't know Lucas's theorem that came out naturally in Atcoder