ABC320をPythonで解いてみたよ。(A～E問題)

[AtCoder Beginners Contest 320 (ABC320)](https://atcoder.jp/contests/abc320) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。


# A - Leyland Number

## 問題ページ
https://atcoder.jp/contests/abc320/tasks/abc320_a

## 考察
Pythonでは、累乗は次のように書けます。
```Python
# 3の5乗
x = 3 ** 5  # 243
```
これをつかってACできます。

## コード
```Python
a, b = map(int, input().split())
print(a ** b + b ** a)
```

## 別解
<details>  <summary>for文をつかった解法 (累乗の書き方を知らなかった世界線のおはなし)</summary>

「累乗の書き方なんて知りませーん！！」

そんなこともあると思います。

for文をつかって同じ数字をかけることでもACできます。

```Python
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)
```

</details>

<details> <summary>pow関数 (発展)(おまけ)</summary>

累乗を計算するためだけの、pow関数というのもPythonにはありまして...

```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問題くらいから頻出です。今のうちに覚えておくといいことあるかもしれないです。

</details>

# B - Longest Palindrome

## 問題ページ
https://atcoder.jp/contests/abc320/tasks/abc320_b

## 考察
たとえば入力で与えられた文字列が「TOYOTA」(サンプル1)だったら、「OYOT」や「TOYOT」や「OTA」など、考えられる部分文字列を全パターン列挙してみて、それぞれについて回文かどうかを判定します。
回文の判定は、次のように書けます。
```Python
A = input()  # 何か文字列を受け取る
B = A[::-1]  # Aを反転させた文字列 (重要!!)
if A == B:
    print("Aは回文です")
else:
    print("Aは回文じゃないです")
```
これをつかってACできます。

## コード
```Python
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)

## 問題ページ
https://atcoder.jp/contests/abc320/tasks/abc320_c

## 考察
$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$ に押すことにします(ここの実装に関しては下のコードを参考にしてください)。


## コード
```Python
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

## 問題ページ
https://atcoder.jp/contests/abc320/tasks/abc320_d

## 考察
たとえば入力で「 $1, 3, 5, 7$ 」が与えられたら、「人 $1$ からx軸方向に $5$、y軸方向に $7$ だけ移動した先に人 $3$ がいる」ということを表しています。
これは、「人 $3$ からx軸方向に $-5$、y軸方向に $-7$ だけ移動した先に人 $1$ がいる」と言い換えることもできます。

- 人 $1$ が最初に原点にいるので、まずは人 $1$ から分かる人の座標を求めていきます。
- さっき座標が分かった人たちから、新たに座標が分かる人たちの座標を求めていきます。
- (おなじことの繰り返し...)

といった感じで、人 $1$ を起点にして、つながっている人全員の座標を求めます。幅優先探索BFSと同じアルゴリズムです。

## コード
```Python
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

## 問題ページ
https://atcoder.jp/contests/abc320/tasks/abc320_e

## 考察
気合いの実装問題です。

列から外れている人について、(列に戻る時刻、人の番号)を格納するヒープキューを用意します。
そうめんを待機している人の列について、最小の番号の人がそうめんを食べるので、これもヒープキューを用意します。

そうめんが流れてくるごとに、その時刻を $t$ とすると、
- 列から外れている人のヒープキューから、時刻 $t$ 以下の時刻に戻ってくる人をみんな列に戻します。
- そうめんを待機している人のヒープキューから、最小の番号の人を取り出して、その人が今流れているそうめんを食べます。
- そうめんを食べた人は列から外れます。列から外れている人のヒープキューに追加します。
- そうめんを待機している人が誰もいない特殊なケースもあります。このときは、そうめんは誰も食べられません。なのでなんの処理もしません。

といった感じです。これを気合いで実装します。

## コード
```Python
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)

```