第3回アルゴリズム実技検定(PAST)解説(Python)

Pythonでとく第3回アルゴリズム実技検定

アルゴリズム実技検定とは

アルゴリズム実技検定はAtCoder社が提供している競技プログラミング(アルゴリズム力)の試験。PASTはPractical Algorithm Skill Testの略。googleabilityが少し悪いですね。

通常は一般で8800円/人（税込）かかるが第3回は無料。通常のAtCoderのレーティングは相対評価の色表示だが、PASTでは絶対評価で5段階。全15問5時間なので1問あたり20分。

競プロ大前提復習

1GHzのCPUなら1s間にループをざっくり10^9回実行可能。実行の制限時間はものによるが2s程度。PythonはC++などと比べて速度が1/10程度、簡単なループなら最適化でもう少しはやく実行されるが、いずれにせよ10^10を越えると時間内に終わらない。

A - ケース・センシティブ

小文字での比較. 3文字x2で一瞬なので計算量とか関係ないですね。

#!/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 - ダイナミック・スコアリング

それぞれの人がもらえるポイントは問題を解いた時点で確定されず他の人が問題を解くと過去に遡って減点されるのがポイントですね。

愚直にmax 10^5回あるクエリーのループで毎回max 10^5 人分の得点配列を更新すると10^10で終わらない.
問題の得点、解いた問題をメモっておけば計算量が減らせる。

#!/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 - 等比数列

愚直にかけると10^9回の計算が終わらないのである程度大きくなったところで打ち切り。

言語によってはオーバーフローの関係で2^30 >10^9であることを利用してN>=31なら計算打ち切る技もあるようです。

#!/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 - 電光掲示板

例題が0-9の各文字になっているのでそれを利用してパースするだけ。50(N)x幅4x列5なので計算も時間何に終わる。
表示部分だけを考えるよりは非表示部分含めて幅4それぞれが各数字に対応していると考えた方が実装が楽。

#!/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 - スプリンクラー

スプリンクラーというとずっと起動していて常に色が伝播するのかと最初思いましたがそうではないですね。
起動時のみ近くのnodeの色を上書き。

隣接ペアのリストから後から隣接nodeを探すのは大変なので最初にとあるnodeの隣接nodeをメモっておく。

#!/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 - 回文行列

例に騙されて列方向切り取った時に回文かの判定かと最初思いましたが、違いますね。
各行から1文字ずつとった時にできる回文

頭側の各行の集合とお尻がわの各行の集合の積があれば適当に一つ取っておく。回文生成は列長が奇数長と偶数長で場合分け。

#!/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 - グリッド金移動

最短経路問題。BFSでも解けるらしいですがダイクストラで。
無限に広がる場所で障害物がダーっと１直線に壁のように並んだ場合もあるので移動できる場所は障害物の置ける場所より広くとっておく必要がある。

辿り着けないを表現するのが面倒だったので通れない場所には十分大きな数字を使用。

#!/bin/python3

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

# n: 頂点数
# g[v] = {(w, cost)}:
#     頂点vから遷移可能な頂点(w)とそのコスト(cost)
# s: 始点の頂点

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 - ハードル走

pure動的計画法で解いている人がほとんど。でもダイクストラで。通過したタイミングで到達判定するので補正が必要。

#!/bin/python3

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

# n: 頂点数
# g[v] = {(w, cost)}:
#     頂点vから遷移可能な頂点(w)とそのコスト(cost)
# s: 始点の頂点

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 - 行列操作

NxNの配列を張り替えると10^10で時間内に終わらない。
転置は行と列を入れ替えたことにして、次参照する時に行と列を入れ替えればOK。
行、列の入れ替えは変換配列を作れば実際に行列を改変する必要がなくなる.

またNxNの行列は二次元配列として初期化するとそれだけで10^5*10^5=10^10になるので最後にprintする時に計算する必要がある。

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

まとめ