The 3rd Algorithm Practical Test (PAST) Explanation (Python)

Use Python 3rd Algorithm Practical Test

What is an algorithm practice test?

The algorithm practice test is a competitive programming (algorithm power) test provided by AtCoder. PAST is an abbreviation for Practical Algorithm Skill Test. googleability is a little bad.

It usually costs 8800 yen / person (tax included), but the 3rd time is free. The normal AtCoder rating is a relative evaluation color display, but in PAST there are 5 levels of absolute evaluation. All 15 questions are 5 hours, so 20 minutes per question.

Competitive professional major premise review

With a 1GHz CPU, you can roughly execute a loop 10 ^ 9 times in 1s. The time limit for execution depends on the time, but it is about 2s. Python is about 1/10 faster than C ++, and if it is a simple loop, it will be executed a little faster by optimization, but in any case, if it exceeds 10 ^ 10, it will not finish in time.

A-Case Sensitive

Comparison in lowercase letters. 3 characters x 2 is a moment, so it has nothing to do with the amount of calculation.

#!/bin/python3

import sys
input = sys.stdin.readline

def main():
  s = input().strip()
  t = input().strip()
  if s == t:
    print("same")
  elif s.lower() == t.lower():
    print("case-insensitive")
  else:
    print("different")

main()

B-Dynamic scoring

The point that each person can get is not fixed when the problem is solved, and when another person solves the problem, the points are deducted retroactively.

Honestly, if you update the score array for max 10 ^ 5 people every time in a loop of queries with max 10 ^ 5, it will not end at 10 ^ 10. You can reduce the amount of calculation by writing down the score of the problem and the problem you solved.

#!/bin/python3

import sys
input = sys.stdin.readline
from collections import defaultdict

def print_score(score, solved, n):
  result = 0
  for i in solved[n]:
    result += score[i]
  print(result)

def solve_problem(score, solved, n, m):
  solved[n].append(m)
  score[m] -= 1

def main():
  n, m, q = list(map(int, input().strip().split()))
  score = [n]*m
  solved = defaultdict(list)
  for i in range(q):
    query = list(map(int, input().strip().split()))
    if query[0] == 1:
      print_score(score, solved, query[1]-1)
    elif query[0] == 2:
      solve_problem(score, solved, query[1]-1, query[2]-1)

main()

C-Geometric progression

If you apply it honestly, the calculation of 10 ^ 9 times will not be completed, so it will be terminated when it becomes large to some extent.

Depending on the language, there seems to be a technique to discontinue the calculation if N> = 31 by utilizing the fact that 2 ^ 30> 10 ^ 9 due to overflow.

#!/bin/python3

import sys
input = sys.stdin.readline

def main():
  a, r, n = list(map(int, input().strip().split()))
  v = a
  LIMIT = 10**9
  for _ in range(n-1):
    v *= r
    if v > LIMIT:
      print('large')
      sys.exit()

  print(v)

main()

D --Electric bulletin board

Since the example is each character of 0-9, just use it to parse. Since it is 50 (N) x width 4 x column 5, the calculation ends in time. It is easier to implement if you think that each of the width 4 including the non-display part corresponds to each number rather than considering only the display part.

#!/bin/python3

import sys
input = sys.stdin.readline

def main():
  n = int(input().strip())
  s = []
  for i in range(5):
    s.append(input().strip())

  num = ['.###..#..###.###.#.#.###.###.###.###.###',
        '.#.#.##....#...#.#.#.#...#.....#.#.#.#.#',
        '.#.#..#..###.###.###.###.###...#.###.###',
        '.#.#..#..#.....#...#...#.#.#...#.#.#...#',
        '.###.###.###.###...#.###.###...#.###.###']
  board = []
  for i in range(10):
    tmp = []
    for j in range(5):
      tmp.append(num[j][4*i:4*i+4])
    board.append(tmp)

  result = ''
  for k in range(n):
    for i in range(10):
      count = 0
      for j in range(5):
        if board[i][j] == s[j][4*k:4*k+4]:
          count += 1
        else:
          break
      if count == 5:
        result += str(i)
        break

  print(result)

main()

E-Sprinkler

At first I thought that sprinklers would always be running and the colors would propagate, but that's not the case. Overwrite the color of nearby nodes only at startup.

It is difficult to find the adjacent node from the list of adjacent pairs later, so make a note of the adjacent node of a certain node first.

#!/bin/python3

import sys
input = sys.stdin.readline
from collections import defaultdict

def print_color(c, x):
  print(c[x])

def launch_sprinkler(c, vdict, x):
  for i in vdict[x]:
    c[i] = c[x]

def change_color(c, x, y):
  c[x] = y

def main():
  n, m, q = list(map(int, input().strip().split()))
  vdict = defaultdict(list)
  for i in range(m):
    u, v = list(map(int, input().strip().split()))
    vdict[u-1].append(v-1)
    vdict[v-1].append(u-1)
  c = list(map(int, input().strip().split()))

  for i in range(q):
    query = list(map(int, input().strip().split()))
    if query[0] == 1:
      print_color(c, query[1]-1)
      launch_sprinkler(c, vdict, query[1]-1)
    elif query[0] == 2:
      print_color(c, query[1]-1)
      change_color(c, query[1]-1, query[2])
main()

F-Palindromic matrix

At first I thought it was a palindrome when I was deceived by the example and cut out in the column direction, but it is not. A palindrome created when one character is taken from each line

If there is a product of the set of each row on the head side and the set of each row on the buttock, save one appropriately. Palindrome generation is divided into cases where the column length is odd-numbered and even-numbered.


#!/bin/python3

import sys
input = sys.stdin.readline
from collections import defaultdict

def main():
  n = int(input().strip())
  a = []
  for i in range(n):
    a.append(set(list(input().strip())))

  s = []
  for i in range(n//2):
    common = list(a[i] & a[-i-1])
    if len(common) > 0:
      s.append(common[0])
    else:
      print(-1)
      sys.exit()

  if n % 2 == 0:
    print(''.join(s + s[::-1]))
  else:
    print(''.join(s + [list(a[n//2])[0]] + s[::-1]))

main()

G-Grid Gold Move

Shortest path problem. It seems that it can be solved with BFS, but with Dijkstra. Obstacles may be lined up in a straight line like a wall in an infinitely wide area, so it is necessary to set a wider place for movement than the place where obstacles can be placed.

Since it was troublesome to express that I could not reach, I used a large enough number for places that I could not pass.

#!/bin/python3

import sys
input = sys.stdin.readline
from collections import defaultdict

# n:Number of vertices
# g[v] = {(w, cost)}:
#Vertices that can be transitioned from vertex v(w)And its cost(cost)
# s:The apex of the starting point

from heapq import heappush, heappop
INF = float("inf")

def dijkstra(n, g, s):
    dist = [INF] * n
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in g[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

def main():
  n, x, y = list(map(int, input().strip().split()))
  x = x + 210
  y = y + 210
  weight = [[1] * 420 for i in range(420)]
  move = [(1,1), (0,1), (-1,1), (1,0), (-1,0), (0,-1)]

  for i in range(n):
    a, b = list(map(int, input().strip().split()))
    a += 210
    b += 210
    weight[a][b] = 10000

  g = defaultdict(list)
  for i in range(5, 415):
    for j in range(5, 415):
      for a,b in move:
        pos = 420*(i+a)+j+b
        cost = weight[i+a][j+b]
        g[420*i+j].append((pos, cost))

  start = 420*210+210
  dist = dijkstra(1700*1700, g, start)
  end = 420*x+y
  result = dist[end]
  if result >= 10000:
    print(-1)
  else:
    print(result)

main()

H --Hurdle running

Most people solve it with pure dynamic programming. But with Dijkstra. It needs to be corrected because the arrival is judged at the timing of passing.

#!/bin/python3

import sys
input = sys.stdin.readline
from collections import defaultdict

# n:Number of vertices
# g[v] = {(w, cost)}:
#Vertices that can be transitioned from vertex v(w)And its cost(cost)
# s:The apex of the starting point

from heapq import heappush, heappop
INF = float("inf")

def dijkstra(n, g, s):
    dist = [INF] * n
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in g[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

def main():
  n, l = list(map(int, input().strip().split()))
  x = list(map(int, input().strip().split()))
  t = list(map(int, input().strip().split()))

  board = [0] * (l+5)
  for i in x:
    board[i] = 1

  g = defaultdict(list)
  for i in range(l):
    for j in range(3):
      if j == 0:
        pos = i+1
        cost = t[0]
      elif j == 1:
        pos = i+2
        cost = t[0] + t[1]
        if pos > l:
          pos = l
          cost = (t[0] + t[1])/2
      else:
        pos = i+4
        cost = t[0] + t[1] * 3

        if pos > l:
          pos = l
          cost = t[0]*0.5 + t[1]*0.5 + t[1]*(l-i-1)

      if board[i] == 1:
        cost += t[2]
      g[i].append((pos, round(cost)))

  start = 0
  dist = dijkstra(l+5, g, start)
  end = l
  result = dist[end]
  print(result)

main()

I-Matrix operation

When the NxN array is rearranged, it does not finish in time at 10 ^ 10. For transposition, it is OK if the rows and columns are swapped and the rows and columns are swapped at the next reference. If you create a conversion array to replace rows and columns, you do not need to actually modify the matrix.

Also, if the NxN matrix is initialized as a two-dimensional array, it will be 10 ^ 5 * 10 ^ 5 = 10 ^ 10, so it is necessary to calculate it when printing at the end.

import sys
input = sys.stdin.readline
from collections import defaultdict

def replace_column(convert_column, a, b):
  tmp_a = convert_column[a]
  tmp_b = convert_column[b]
  convert_column[a] = tmp_b
  convert_column[b] = tmp_a

def replace_row(convert_row, a, b):
  tmp_a = convert_row[a]
  tmp_b = convert_row[b]
  convert_row[a] = tmp_b
  convert_row[b] = tmp_a

def print_matrix(n, a, b):
  print(n*a+b)

def main():
  n = int(input().strip())
  q = int(input().strip())
  convert_column = []
  for i in range(n):
    convert_column.append(i)
  convert_row = []
  for i in range(n):
    convert_row.append(i)

  transpose = False
  for i in range(q):
    query = list(map(int, input().strip().split()))
    if query[0] == 1:
      if transpose:
        replace_column(convert_column, query[1]-1, query[2]-1)
      else:
        replace_row(convert_row, query[1]-1, query[2]-1)
    elif query[0] == 2:
      if transpose:
        replace_row(convert_row, query[1]-1, query[2]-1)
      else:
        replace_column(convert_column, query[1]-1, query[2]-1)
    elif query[0] == 3:
      transpose = not transpose
    elif query[0] == 4:
      if transpose:
        print_matrix(n, convert_row[query[2]-1], convert_column[query[1]-1])
      else:
        print_matrix(n, convert_row[query[1]-1], convert_column[query[2]-1])

main()

Summary

https://github.com/hiromichinomata/atcoder

Recommended Posts

The 3rd Algorithm Practical Test (PAST) Explanation (Python)
1st Algorithm Practical Test Solve past questions with python
2nd Algorithm Practical Test Solve past questions with python (unfinished)
AtCoder 3rd Algorithm Practical Test Participation Report
Algorithm in Python (primality test)
AtCoder: Python: Daddy the sample test.
Write the test in a python docstring
Python algorithm
Search the maze with the python A * algorithm
Algorithm learned with Python 3rd: Radix conversion
python setup.py test the code using multiprocess
Aggregate test results using the QualityForward Python library
[Python] Test the moon matagi of relative delta
AtCoder 2nd Algorithm Practical Test Virtual Participation Report
[Algorithm x Python] How to use the list
[Introduction to Algorithm] Find the shortest path [Python3]
Find the shortest path with the Python Dijkstra's algorithm
Solving the Python knapsack problem with the greedy algorithm
About the test
Python memorandum (algorithm)
Python Integrity Test
Explanation of the concept of regression analysis using python Part 2
The first algorithm to learn with Python: FizzBuzz problem
Python --Explanation and usage summary of the top 24 packages
Install the 3rd party python library on Cinema 4D
Explanation of the concept of regression analysis using Python Part 1
Implemented the algorithm of "Algorithm Picture Book" in Python3 (Heapsort)
Explanation of the concept of regression analysis using Python Extra 1