Fill JOI Difficulty 4 with Python

Introduction

Use Python (PyPy) to solve JOI difficulty 4 problems. See this site for questions and difficulty.

A-Maximum sum

** Thoughts ** I don't have time to sum each time, so I use the cumulative sum.

n, k = map(int,input().split())
a = [int(input()) for _ in range(n)]

sums = [0]
for i in range(n):
    sums.append(sums[-1]+a[i])

ans = sums[k]
for i in range(k,n+1):
    ans = max(sums[i]-sums[i-k],ans)
print(ans)

C-Card Game

** Thoughts ** I'm not good at game-related problems. I simulated it.

n = int(input())
taro = [int(input()) for _ in range(n)]

taro.sort()
hana = []
for i in range(1,2*n+1): #There is no duplication, so hana has cards that taro doesn't have
    if i not in taro:
        hana.append(i)

m = taro.pop(0)
for _ in range(2*n):
    for i in range(len(hana)): #Find out the minimum number of cards you can play
        if hana[i] > m:
            m = hana.pop(i)
            break
    else:
        m = 0
    for i in range(len(taro)): #Find out the minimum number of cards you can play
        if taro[i] > m:
            m = taro.pop(i)
            break
    else:
        m = 0
    if len(hana) == 0 or len(taro) == 0: #Finish when either becomes 0
        break

print(len(hana)) #Last number
print(len(taro)) #Last number

C-Party

** Thoughts ** Make a list that summarizes the distance between you and $ n $ friends (how many friends you go through) and count the number of people 2 or less

n = int(input())
m = int(input())
f = [list(map(int,input().split())) for _ in range(m)]

d = [0] * n
for i in range(m): #friend(Distance 1)To find out
    if f[i][0] == 1:
        d[f[i][1]-1] = 1

for i in range(m): #A friend of a friend(Distance 2)To find out
    if d[f[i][0]-1] == 1:
        if d[f[i][1]-1] == 0:
            d[f[i][1]-1] = 2 #Friend of a friend is a distance 2
    elif d[f[i][1]-1] == 1:
        if d[f[i][0]-1] == 0:
            d[f[i][0]-1] = 2 #Friend of a friend is a distance 2

ans = d.count(1) + d.count(2) - 1

print(max(0,ans))

** Thoughts ** Calculate the distance from any of the left, right, top, and bottom edges, and divide it by 3 to process it. The colors are painted in order from the closest edge, so it is necessary to separate the cases for each square.

n = int(input())
k = int(input())
ab = [list(map(int,input().split())) for _ in range(k)]

for i in range(k):
    x1 = ab[i][0]-1
    x2 = n - ab[i][0]
    y1 = ab[i][1]-1
    y2 = n - ab[i][1]
    m = min(x1,x2,y1,y2) % 3
    if m == 0:
        print(1)
    if m == 1:
        print(2)
    if m == 2:
        print(3)

C-Signboard

** Thoughts ** It is troublesome to count all the possible combinations by counting the target characters, so determine the distance first and simulate.

n = int(input())
s = input()
plate = [input() for _ in range(n)]

ans = 0
for i in range(n):
    p = plate[i]
    start =[]
    check = False

    for k in range(len(p)):
        if p[k] == s[0]: #Find out the starting point
            start.append(k)

    for k in range(1,len(p)+1): #Distance between letters
        if check:
            break
        for j in start: #Choose the first letter you looked up earlier
            flag = 0
            c = 0 #Expressing the same size of distance by increasing c
            while j + k * c < len(p) and c < len(s): #j(First letter)Distance from the cth character
                if p[j+k*c] != s[c]:
                    break
                else:
                    c += 1
                    flag += 1
            if flag == len(s): #If you can create the desired character, use ans+1
                ans += 1
                check = True
                break

print(ans)

flag is dirty

C --Super Metropolis

** Thoughts ** I misread the initial value as (1,1). The initial value is (x1, y1). There is a route that goes diagonally only when going northeast or southwest, so it is necessary to separate cases, otherwise it is usually the shortest route of grid. Separated for demons ()

--In case of vertical or horizontal movement only, the difference between either coordinates will be 0, so take max. ――When you go northeast, you can calculate it, but you can find that you should take the max of the difference between the coordinates. This is the same in the southwest --In other cases, the diagonal road cannot be used, so the sum of the absolute values of the differences between the coordinates is taken.

w, h, n = map(int,input().split())
spots = [list(map(int,input().split())) for _ in range(n)]

def search_route(s,g):
    if s[0] == g[0] or s[1] == g[1]: #Vertical or horizontal movement only
        return max(abs(g[1] - s[1]), abs(g[0] - s[0]))

    elif s[0] < g[0] and s[1] < g[1]: #Go northeast
        return max(g[0] - s[0], g[1] - s[1])

    elif s[0] > g[0] and s[1] > g[1]: #Go southwest
        return max(s[0] - g[0], s[1] - g[1])

    else: #other than that
        return abs(s[0] - g[0]) + abs(s[1] - g[1])

ans = 0
for i in range(n-1):
    ans += search_route(spots[i],spots[i+1])
print(ans)

A-Poster

** Thoughts ** Let's consider each case by fixing the operation of rotating the poster. The rotation is $ 0 °, 90 °, 180 °, 270 ° $. All you have to do now is count the squares that are different in color from the desired poster.

I change the input depending on my mood, but normal input is okay

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np #The operation of rotating uses numpy

n = int(readline())
s = np.array([list(readline().rstrip().decode()) for _ in range(n)])
t = [readline().rstrip().decode() for _ in range(n)]

ans = float('inf')
for i in range(4):
    check = np.rot90(s,i) #rotation
    c = min(4-i,i)
    for j in range(n):
        for k in range(n):
            if check[j][k] != t[j][k]:
                c += 1
    ans = min(ans,c)
print(ans)

Summary

I have a lot of dirty code, so I will fix it and finally write it in C ++. I feel that difficulty level 4 is the appropriate level for me now, but I will continue to devote myself to further improving it. See you ~