[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 1/22]

** 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! !! !! !! !! !!

Related article link

** 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) **

Commemorative "Part 1" -Ordinary full enumeration-

We will solve the following 4 questions!

Search all: Enumerate all

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.

1 ITP1_7_B - How Many Ways?

↓ 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)

4 Paken Cup 2019 C-Karaoke

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!

Full search: All enumeration to reduce the number of streets by devising

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!

Next (Part 2/22)

Recommended Posts

[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 5/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 4/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 1/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 6/22]
Solve with Python [100 past questions that beginners and intermediates should solve] (028 --033 breadth-first search)
Solve with Python [100 past questions that beginners and intermediates should solve] (053 --055 Dynamic programming: Others)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (024 --027 Depth-first search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (015 --017 Full search: Permutation full search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (010 --014 Full search: Bit full search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (001 --004 All search: All enumeration)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (056 --059 Shortest path problem: Dijkstra's algorithm)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (034-038 Dynamic programming: Knapsack DP basic)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (039 --045 Dynamic programming: Knapsack DP variant)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (005 --- 009 All search: All enumeration to reduce the number of streets by devising)
I tried to solve the ant book beginner's edition with python
Python that I would like to recommend to programming beginners
I tried to solve the soma cube with python
I tried to solve the problem with Python Vol.1
I tried to solve AOJ's number theory with Python
I tried to enumerate the differences between java and python
I tried to make GUI tic-tac-toe with Python and Tkinter
A super introduction to Django by Python beginners! Part 6 I tried to implement the login function
I tried to summarize the languages that beginners should learn from now on by purpose
Tohoku University 2020 First semester math exam (science) I tried to solve major questions 1 to 3 with Python
A super introduction to Django by Python beginners! Part 1 I tried to display an HTML page that only says "Hello World"
I tried to touch Python (installation)
python beginners tried to find out
I want to solve APG4b with Python (only 4.01 and 4.04 in Chapter 4)
[Python] A memo that I tried to get started with asyncio
[Pandas] I tried to analyze sales data with Python [For beginners]
I tried to make a periodical process with Selenium and Python
I tried to easily detect facial landmarks with python and dlib
[Python] I tried to explain words that are difficult for beginners to understand in an easy-to-understand manner.
I tried to summarize Python exception handling
I tried to implement PLSA in Python
I tried to refer to the fun rock-paper-scissors poi for beginners with Python
A super introduction to Django by Python beginners! Part 3 I tried using the template file inheritance function
How to write offline real time I tried to solve E11 with python
I tried to implement PLSA in Python 2
Python3 standard input I tried to summarize
I wanted to solve ABC160 with Python
I tried using PyEZ and JSNAPy. Part 2: I tried using PyEZ
I tried to implement ADALINE in Python
I tried to let optuna solve Sudoku
I tried to develop a Formatter that outputs Python logs in JSON
A super introduction to Django by Python beginners! Part 2 I tried using the convenient functions of the template
I tried to make Kana's handwriting recognition Part 2/3 Data creation and learning
I wanted to solve ABC159 in Python
I tried to implement PPO in Python
10 Python errors that are common to beginners
I tried to verify and analyze the acceleration of Python by Cython
I tried to solve AtCoder's depth-first search (DFS) in Python (result: TLE ...)
I tried to solve TSP with QAOA
[Python] I tried to calculate TF-IDF steadily
[Markov chain] I tried to read quotes and negative emotions into Python.
I tried to touch Python (basic syntax)
I tried to create a sample to access Salesforce using Python and Bottle
I wanted to solve ABC172 with Python
I refactored "I tried to make Othello AI when programming beginners studied python"