AtCoder Beginners Contest 320 (ABC320) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Leyland Number
問題ページ
考察
Pythonでは、累乗は次のように書けます。
# 3の5乗
x = 3 ** 5 # 243
これをつかってACできます。
コード
a, b = map(int, input().split())
print(a ** b + b ** a)
別解
for文をつかった解法 (累乗の書き方を知らなかった世界線のおはなし)
「累乗の書き方なんて知りませーん！！」
そんなこともあると思います。
for文をつかって同じ数字をかけることでもACできます。
a, b = map(int, input().split())
# v1: aのb乗
v1 = 1
for _ in range(b):
v1 *= a
# v2: bのa乗
v2 = 1
for _ in range(a):
v2 *= b
print(v1 + v2)
pow関数 (発展)(おまけ)
累乗を計算するためだけの、pow関数というのもPythonにはありまして...
# 4の5乗
v = pow(4, 5) # 1024
# 3の5乗を7で割ったあまり (3^5=243, 243%7=5)
x = pow(3, 5, 7) # 5
こんな感じで計算してくれます。
詳しくはここでは書かないですが、コードの2つ目にある第3引数に割る数を指定する方法は、E問題くらいから頻出です。今のうちに覚えておくといいことあるかもしれないです。
B - Longest Palindrome
問題ページ
考察
たとえば入力で与えられた文字列が「TOYOTA」(サンプル1)だったら、「OYOT」や「TOYOT」や「OTA」など、考えられる部分文字列を全パターン列挙してみて、それぞれについて回文かどうかを判定します。
回文の判定は、次のように書けます。
A = input() # 何か文字列を受け取る
B = A[::-1] # Aを反転させた文字列 (重要!!)
if A == B:
print("Aは回文です")
else:
print("Aは回文じゃないです")
これをつかってACできます。
コード
S = input()
N = len(S)
ans = 0
for i in range(N):
for j in range(i + 1, N + 1):
T = S[i:j] # Sのi文字目からj-1文字目までの文字列
if T == T[::-1]:
ans = max(ans, len(T))
print(ans)
C - Slot Strategy 2 (Easy)
問題ページ
考察
$S_1$ の$i$ 番目、 $S_2$ の $j$ 番目、 $S_3$ の $k$ 番目、の $i,j,k$ を全探索する方針でいきます。
文字列の長さ $M$ の制約は $M \leq 100$ なので、全探索しても最大で $100 \times 100 \times 100=10^6$ 通りで済みます。
$1$ 秒に $1$ 回しかボタンは押せないので、たとえば $i=j$ だったら、$S_1$ の $i$ 番目を時刻 $i$ に押した後、 $S_2$ の $j$ 番目はリールが $1$ 周まわるのを待ってから 時刻 $j+M$ に押すことにします(ここの実装に関しては下のコードを参考にしてください)。
コード
INF = 1 << 50
M = int(input())
S = [input() for _ in range(3)]
ans = INF
for i in range(M):
for j in range(M):
for k in range(M):
if not (S[0][i] == S[1][j] == S[2][k]):
continue
now_ans = 0
counter = [0] * M # counter[t]: 時刻tに押そうとした回数
for m in [i, j, k]:
now_ans = max(now_ans, m + counter[m] * M)
counter[m] += 1
ans = min(ans, now_ans)
if ans == INF:
print(-1)
else:
print(ans)
D - Relative Position
問題ページ
考察
たとえば入力で「 $1, 3, 5, 7$ 」が与えられたら、「人 $1$ からx軸方向に $5$、y軸方向に $7$ だけ移動した先に人 $3$ がいる」ということを表しています。
これは、「人 $3$ からx軸方向に $-5$、y軸方向に $-7$ だけ移動した先に人 $1$ がいる」と言い換えることもできます。
- 人 $1$ が最初に原点にいるので、まずは人 $1$ から分かる人の座標を求めていきます。
- さっき座標が分かった人たちから、新たに座標が分かる人たちの座標を求めていきます。
- (おなじことの繰り返し...)
といった感じで、人 $1$ を起点にして、つながっている人全員の座標を求めます。幅優先探索BFSと同じアルゴリズムです。
コード
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
a, b, x, y = map(int, input().split())
a, b = a - 1, b - 1
G[a].append((b, x, y))
G[b].append((a, -x, -y))
que = deque()
que.append(0)
coord = [None] * N
coord[0] = [0, 0]
while que:
v = que.popleft()
ox, oy = coord[v]
for nv, x, y in G[v]:
if coord[nv] is not None:
continue
coord[nv] = [ox + x, oy + y]
que.append(nv)
for i in range(N):
if coord[i] is None:
print("undecidable")
else:
print(*coord[i])
E - Somen Nagashi
問題ページ
考察
気合いの実装問題です。
列から外れている人について、(列に戻る時刻、人の番号)を格納するヒープキューを用意します。
そうめんを待機している人の列について、最小の番号の人がそうめんを食べるので、これもヒープキューを用意します。
そうめんが流れてくるごとに、その時刻を $t$ とすると、
- 列から外れている人のヒープキューから、時刻 $t$ 以下の時刻に戻ってくる人をみんな列に戻します。
- そうめんを待機している人のヒープキューから、最小の番号の人を取り出して、その人が今流れているそうめんを食べます。
- そうめんを食べた人は列から外れます。列から外れている人のヒープキューに追加します。
- そうめんを待機している人が誰もいない特殊なケースもあります。このときは、そうめんは誰も食べられません。なのでなんの処理もしません。
といった感じです。これを気合いで実装します。
コード
from heapq import heappop, heappush
from collections import deque
N, M = map(int, input().split())
somen_que = deque()
for _ in range(M):
t, w, s = map(int, input().split())
somen_que.append((t, w, s))
human_comeback_que = [] # 列から外れている人の(戻る時刻, 人番号)を格納するヒープキュー
human_wait_que = [] # そうめんを待機している人のヒープキュー
for i in range(N):
heappush(human_wait_que,i)
ans_lst = [0] * N
while somen_que:
t, w, s = somen_que.popleft()
while human_comeback_que:
ht, hi = heappop(human_comeback_que)
if ht <= t:
heappush(human_wait_que, hi)
else:
heappush(human_comeback_que, (ht, hi))
break
if len(human_wait_que) == 0:
continue
hi = heappop(human_wait_que)
ans_lst[hi] += w
heappush(human_comeback_que, (t + s, hi))
for ans in ans_lst:
print(ans)