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

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

# A - Nine

## 問題ページ
https://atcoder.jp/contests/abc309/tasks/abc309_a

## 考察
「左右」に隣接する組み合わせなのに注意しましょう。
Yesを出力する $(A,B)$ の組み合わせは $6$ つです。エレガントな書き方もありそうですが、これくらいなら全部書いちゃうのが楽だと思います。
## コード
```Python
A, B = map(int, input().split())
P = [
    (1, 2),
    (2, 3),
    (4, 5),
    (5, 6),
    (7, 8),
    (8, 9)
]
if (A, B) in P:
    print("Yes")
else:
    print("No")

```
# B - Rotate

## 問題ページ
https://atcoder.jp/contests/abc309/tasks/abc309_b

## 考察
問題文の通りに、外側のマスを時計回りに動かします。
入力で受け取った $A$ とは別に、答えとして出力する用のリスト $B$ を用意してあげると楽です。
実装については、下のコードを参考にしてください。

## コード
```Python
N = int(input())
A = [input() for _ in range(N)]

B = [list(a) for a in A]

for i in range(N - 1):
    B[0][i + 1] = A[0][i]  # 上の辺
    B[N - 1][i] = A[N - 1][i + 1]  # 下の辺
    B[i + 1][N - 1] = A[i][N - 1]  # 右の辺
    B[i][0] = A[i + 1][0]  # 左の辺
for b in B:
    print(*b, sep="")

```
# C - Medicine

## 問題ページ
https://atcoder.jp/contests/abc309/tasks/abc309_c

## 考察
「 $a$ 日目まで薬を $b$ 錠だけ飲む」を、「 $a+1$ 日目以降は飲む薬が $b$ 錠だけ減る」と言い換えてみます。
入力で与えられる $(a,b)$ を $a$ の昇順にソートしてあげます。また、 $1$日目に飲む薬の数を事前に計算しておきます。
 $a$ の小さいものから順に見ていって、飲む薬の数を実際にシミュレートしていき、その数が $K$ 以下になった時点でその日にちを出力してあげればACです。
実装の工夫として、 「$1$ 日目以降は飲む薬が $0$ だけ減る」を表す $(1,0)$ も追加してあげると、初日から飲む薬の数が $K$ 以下の場合にも正しくACできます。

## コード
```Python
N, K = map(int, input().split())
A = [(1, 0)]
cnt = 0
for _ in range(N):
    a, b = map(int, input().split())
    A.append((a + 1, b))
    cnt += b
A.sort()

for a, b in A:
    cnt -= b
    if cnt <= K:
        print(a)
        exit()

```
# D - Add One Edge

## 問題ページ
https://atcoder.jp/contests/abc309/tasks/abc309_d

## 考察
「頂点 $1$ から最も遠い点」と、「頂点 $N_1+N_2$ から最も遠い点」の $2$ 点を結んであげればokです。
問題で聞かれているのは距離だけです。 
「頂点 $1$ から最も遠い点までの距離」と、「頂点 $N_1+N_2$ から最も遠い点までの距離」を求めて、そこに $2$点を結んだ分の距離 $1$ を足してあげて答えになります。

## コード
```Python
from collections import deque

N1, N2, M = map(int, input().split())

G = [[] for _ in range(N1 + N2)]

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)


def bfs(s):
    que = deque()
    que.append(s)
    dist = [-1] * len(G)
    dist[s] = 0
    while que:
        v = que.popleft()
        for nv in G[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                que.append(nv)
    return max(dist)


print(bfs(0) + bfs(N1 + N2 - 1) + 1)

```
# E - Family and Insurance

## 問題ページ
https://atcoder.jp/contests/abc309/tasks/abc309_e

## 考察
「 $y_i$ 代先までの子たちが対象」を「 $y_i + 1$ のパワーを持っている」と言い換えます。
パワーは、 $1$ つ下の代に行くごとに $1$ だけ減っていくものとします。そして、下の代へと受け継いでいる過程で、より大きなパワーを持っている人が現れた場合、そのパワーを採用することにします。
答えは、パワーが $1$ 以上の人の数になります。
人 $1$ から順に下の代へと見ていくのは BFSでもDFSでもいいです。個人的にBFSの方が書きやすいので、下のコードではBFSで人 $1$ から人 $N$ まで見ています。

## コード
```Python
from collections import deque

N, M = map(int, input().split())
p = [-1] + list(map(int, input().split()))

# chs[i]: 人iの子リスト
chs = [[] for _ in range(N)]
for i, pa in enumerate(p):
    if i == 0:
        continue
    chs[pa - 1].append(i)

power = [0] * N
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y += 1
    power[x] = max(power[x], y)

que = deque()
que.append(0)
seen = set()
while que:
    v = que.popleft()
    cost = power[v]
    for ch in chs[v]:
        que.append(ch)
        power[ch] = max(power[ch], cost - 1)

ans = 0
for el in power:
    if el > 0:
        ans += 1
print(ans)

```
# F - Box in Box

## 問題ページ
https://atcoder.jp/contests/abc309/tasks/abc309_f

## 考察
幅・高さ・奥行きの $3$ つは入れ替えが自由ですが、幅 $\leq$ 高さ $\leq$ 奥行き と固定することにします。こうしなくてもすっぽりとハマる箱のペアがあったとき、その箱のペアは 幅 $\leq$ 高さ $\leq$ 奥行き としてもすっぽりはめられるからです。

幅が昇順になるように、箱たちをソートします。こうすると、箱リストを左から順に見ていったときに、箱の幅は気にする必要がなくなります。

こうして左から順に見ていくと、「今までで見終わった箱たちの中で、今見ている箱の高さ・奥行き $\geq$ ある箱の高さ・奥行き、 になるような箱が存在するか」が分かるようにしたくなります。
愚直にするなら、 Height[depth]: 奥行きdepthのときの最小の高さ、となるリストを用意してあげることになりますが、これだとしんどそうです。
具体的にしんどいのは次の2つです。
- しんどいポイント1: 奥行きの最大値が $10^9$ なせいで、長さ $10^9$ のリストが必要になる。
- しんどいポイント2: 奥行きが $d$ 未満のものについて調べたいとき、 [1,d) の区間を1つ1つ調べないといけない。

実は、この2つはどちらも解決してあげられます。
奥行きの最大値が $10^9$ なのについては、今回は奥行きの実際の値は全く気になってなくて、気になっているのは奥行き同士の大小関係だけです。これは座圧することで解決できて、Heightリストは 長さ$N$ だけ用意すればよくなりました。

[1,d) の区間を1つ1つ調べないといけないのについては、セグメントツリーをつかえば解決できます。さっきHeightリストの長さが $N$ で大丈夫なのが分かったので、[1,d)の区間の最小値を調べるの1回あたりで $O(logN)$ の計算量で済むので、全体でも $O(NlogN)$ の計算量で済みます。

これでほぼ解けました。

あと実は、同じ幅や高さのものも存在していて、判定に気をつける必要があります。
これは、幅の小さい順にソートしたときに、同時に2つ目のキーとして高さの大きい順にソートしてあげることで解決できます。
また別のやり方として、同じ幅のものはまとめて管理して、まとめたものそれぞれでYesになるかどうかを判定した後に、まとめたものをすべてセグメントツリーにつっこんであげてもokです。

## コード
```Python
'''
syakayamiさん作、PythonバージョンのACLよりコピペしたものです。
使わせていただきありがとうございます！
https://github.com/shakayami/ACL-for-python/blob/master/segtree.py

・使い方(個人的なまとめ)
sg=segtree((初期値リストA), (演算func), (単位元ide_ele))
A: 初期値リスト。問題で与えられてるのをそのまま入れることが多い。
func, ide_ele: 演算とそれに対応する単位元。
　例）add,0 (足し算、単位元0)
詳しいことは下のURLに書いてます。
https://github.com/shakayami/ACL-for-python/wiki/segtree
'''
# (コードが長くなるから省略。上のURLからコピペしてね。)

N = int(input())
Box = []
Vs = [[] for _ in range(3)]
for _ in range(N):
    bi = list(map(int, input().split()))
    bi.sort()
    for i in range(3):
        Vs[i].append(bi[i])
    Box.append(bi)

# 座圧する
for i in range(3):
    Vs[i].sort()
dic = [dict() for _ in range(3)]
for i in range(3):
    for el in Vs[i]:
        if el not in dic[i]:
            v = len(dic[i])
            dic[i][el] = v
for i in range(N):
    for j in range(3):
        Box[i][j] = dic[j][Box[i][j]]
# print(Box)

# box[0]の小さい順に箱を見てく
Box.sort(key=lambda x: (x[0], -x[1]))
st = segtree([1 << 60] * (N + 1), min, 1 << 60)
for a, b, c in Box:
    if st.prod(0, b) < c:
        print("Yes")
        exit()
    if st.prod(b, b + 1) > c:
        st.set(b, c)
print("No")

```