** Aim for a light blue coder! !! !! !! !! !! ** **
So [Guidelines for improving AtCoder, a competition pro taught by Red Coder [Intermediate Edition: Aim for Light Blue Coder! ]]( https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7 % B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% E5% 8E % BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F) (@ e869120)
AtCoder has collected 100 good educational questions that are appropriate for brown and green coders to achieve a light blue coder, or rating 1200, with a small number of questions.
100 past questions that beginners and intermediates should solve in this article`
Will be solved with ** Python **!
Thanks to @ e869120! !! !! !! !! !!
** Search all: List all ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part1 / 22] ** Full search: All enumeration to reduce the number of streets by devising ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part2 / 22] ** Full search: Bit full search ** [[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Full search: Permutation full search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part4 / 22] ** Binary search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part5 / 22] ** Depth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part6 / 22] ** Breadth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22] ** Dynamic programming: Knapsack DP ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 8/22] ** Dynamic programming: Interval DP ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 9/22] ** Dynamic programming: bit DP ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 10/22] ** Dynamic programming: Other ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 11/22] ** Shortest path problem: Dijkstra's algorithm ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 12/22] ** Shortest path problem: Floyd-Warshall Floyd method ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 13/22] ** Minimum spanning tree problem ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 14/22] ** High-speed primality test ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 15/22] ** Fast exponentiation ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 16/22] ** Problems using the inverse element ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 17/22] ** Cumulative sum ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 18/22] Union-Find [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 19/22] ** Other techniques ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 20/22] ** Implementation issues ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part21 / 22] ** Mathematical problems ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 22/22]
** (Added on 2020/05/07) **
input()→sys.stdin.readline().rstrip()
I'm changing to!
[Python] Competitive template [At Coder]
I also made an article for the template, so please use it if you like ~We will solve the following 4 questions!
1 ITP1_7_B --How Many Ways? This is a basic problem. 2 AtCoder Beginner Contest 106 B - 105 3 AtCoder Beginner Contest 122 B - ATCoder 4 Paken Cup 2019 C-Karaoke If you can solve this, you can think that you are accustomed to the full search.
↓ Problems that have been taken up as similar subjects in past articles! (At this time, I solved it with a triple for sentence!) [Python] ABC133B (upper right triangle problem) [At Coder]
There is no problem with the triple for statement, This time I tried to make a double for sentence in a mood!
test.py
def LI(): return list(map(int,input().split()))
while 1:
n,x = LI()
if n==x==0:
break
ans = 0
for i in range(1,n+1):
for j in range(1,n+1):
k = x-i-j #However, the condition of k is[1,n]
if 1<=k<=n and i<j<k:
ans += 1
print(ans)
** (Added on 2020/05/01) ** Now I write the code like this.
test.py
import itertools
def LI(): return list(map(int,input().split()))
while 1:
n,x = LI()
if n==x==0:
break
ans = 0
for i,j,k in itertools.product(range(1,n+1),repeat=3):
if i<j<k and i+j+k==x:
ans += 1
print(ans)
ʻItertools.product` doesn't deepen the nest! Therefore, it is easy to understand even with a triple for statement.
** (Added on 2020/05/02) ** ʻItertools.combinations` This was smarter! !! !!
test.py
import itertools
def LI(): return list(map(int,input().split()))
while 1:
n,x = LI()
if n==x==0:
break
ans = 0
for i,j,k in itertools.combinations(range(1,n+1),3):
if i+j+k==x:
ans += 1
print(ans)
2 AtCoder Beginner Contest 106 B - 105
Difficulty:66
I was almost brain dead!
If the third argument of range (default is 1) is set to" 2 ", for example, one will be skipped!
range (1, int (i ** 0.5) +1) is my favorite when judging prime numbers and searching for divisors!
ʻInt () `is truncated after the decimal point!
test.py
def I(): return int(input())
N = I()
ans = 0
if N>=105:
for i in range(105,N+1,2):
count_yakusuu = 0
for j in range(1,int(i**0.5)+1):
if i%j==0:
count_yakusuu += 2
if count_yakusuu==8:
ans += 1
print(ans)
~~ ** (Added on 2020/04/20) **
By the way, in AtCoder,
Since the version of ABC162 ~ Python3 went up to 3.8 at once,
Future contests are easy with divisors → sympy.divisors () w
(Digression: Greatest common divisor → math.gcd () can now be used! I did it ~) ~~
** (Added on 2020/05/03) **
I couldn't use sympy!
I think I misunderstood ... I'm sorry ...
Greatest common divisor → math.gcd () You can use this! !! !!
I will leave the reference code for the time being ...
Reference code
test.py
import sympy
def I(): return int(input())
N = I()
ans = 0
if N>=105:
for i in range(105,N+1,2):
if len(sympy.divisors(i))==8:
ans += 1
print(ans)
3 AtCoder Beginner Contest 122 B - ATCoder Difficulty:85 I came up with two solutions! One is the usual greedy algorithm. The other is DP.
Solution 1 (greedy algorithm) Overwrite ʻans` in search of all possible answer candidates!
test.py
S = input()
ans,temp = 0,0
for x in S:
if x in 'ACGT':
temp += 1
else:
temp = 0
ans = max(ans,temp)
print(ans)
Solution 2 (DP) With the second argument of ʻenumerate` (default is 0), The index starts from that number!
test.py
S = input()
dp = [0]*(len(S)+1) #1_indexed
for i,x in enumerate(S,1):
if x in 'ACGT':
dp[i] = dp[i-1]+1
print(max(dp))
** (Added on May 26, 2020) ** Solution 3 (Search all substrings) Using the duplicate combination ʻitertools.combinations_with_replacement`, You can search all substrings! !! !! Wow! !! !!
test.py
import itertools
S = input()
ans = 0
for i,j in itertools.combinations_with_replacement(range(len(S)),2):
if all([x in 'ACGT' for x in S[i:j+1]]):
ans = max(ans,j+1-i)
print(ans)
No, it was difficult! A problem that combines the first question upper right triangle problem and the third question. However, I feel that I can write code smoothly from the next time!
test.py
def LI(): return list(map(int,input().split()))
N,M = LI()
A = [LI() for _ in range(N)]
ans = 0
for i in range(M):
for j in range(i+1,M):
temp = 0
for k in range(N):
temp += max(A[k][i],A[k][j])
ans = max(ans,temp)
print(ans)
Another solution
Inferior to the above code. The code that won AC at the very beginning.
If you start with for x in A, you end up with complicated code. .. ..
Prepare a two-dimensional array for temporary evacuation ...
Swap the matrix and add ...
Its maximum value!
test.py
def LI(): return list(map(int,input().split()))
N,M = LI()
A = [LI() for _ in range(N)]
temp = [[0]*(M*(M-1)//2) for _ in range(N)]
for i,x in enumerate(A):
l = 0
for j in range(M):
for k in range(j+1,M):
l += 1
temp[i][l-1] = max(x[j],x[k])
print(max([sum(x) for x in (zip(*temp))]))
** (Added on 2020/05/01) **
Became a Numpy Master (provisional)!
So now I write the code like this.
test.py
import itertools,numpy as np
def LI(): return list(map(int,input().split()))
N,M = LI()
a = np.array([LI() for _ in range(N)])
ans = 0
for i,j in itertools.product(range(M),repeat=2):
if i<j:
ans = max(ans,a[:,[i,j]].max(axis=1).sum())
print(ans)
If you can become Numpy, this code will be easier to read.
** It's interesting to add np.max (). Sum () to the back! !! !! ** **
Numpy's true character is demonstrated when it becomes a two-dimensional array or more! maybe!
Next time, I will solve the following 5 questions!
5 AtCoder Beginner Contest 095 C - Half and Half 6 Sumitomo Mitsui Trust Bank Programming Contest 2019 D --Lucky PIN 7 JOI 2007 Final 3 --The oldest ruins are interesting. In Python3, the assumed solution may be TLE. (PyPy3 is often in time) 8 Square869120Contest # 6 B --AtCoder Markets It seems that there are innumerable streets when you search all, but if you devise one, it is a problem that you can enumerate all with realistic streets. 9 JOI 2008 Qualifying 4-Search for constellations
Part1/22 end!
Recommended Posts