Qiita Teams that are logged in
You are not logged in to any team

Community
Service
Qiita JobsQiita ZineQiita Blog
2
Help us understand the problem. What is going on with this article?

More than 1 year has passed since last update.

@hiromichinomata

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

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

## 競プロ大前提復習

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

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

``````#!/bin/python3

import sys

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

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

``````#!/bin/python3

import sys
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 - 等比数列

``````#!/bin/python3

import sys

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

``````#!/bin/python3

import sys

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

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

``````#!/bin/python3

import sys
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 - 回文行列

``````
#!/bin/python3

import sys
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 - グリッド金移動

``````#!/bin/python3

import sys
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
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で時間内に終わらない。

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

``````import sys
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()
``````

## まとめ

2
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
1. We will deliver articles that match you
By following users and tags, you can catch up information on technical fields that you are interested in as a whole
2. you can read useful information later efficiently
By "stocking" the articles you like, you can search right away
2
Help us understand the problem. What is going on with this article?