abc 168 (python)

4完。Eは難しかった。Dが bfs するだけなのは分かったが一から実装するのに手間取った。dfs だけライブラリとして持っていたのに... bfs も作りました。

# 木(辺のリスト作成)
n, m = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

# dfs
import sys
sys.setrecursionlimit(4100000)

def dfs(now, prev):
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            dfs(next, now)

#bfs (今回のD)
ans = [-1]*n
from collections import deque
 
que = deque()
que.append((0,1))
cnt = 1
while que:
    now,p = que.popleft()
    if cnt == n: #全頂点通ったら終わってよい
      break
    for i in g[now]:
        if not chk[i]:
          ans[i] = p # 1 から i+1 まで最短で来たとき、その前の頂点の番号が頂点 i +1 の答え
          cnt += 1
          que.append((i,i+1))

提出例(コンテスト中に出したので要らない記述もある）
Submission #13328665 - AtCoder Beginner Contest 168
Cは半信半疑で余弦定理使いました。正攻法なのかわからなかったけど、コンテスト後にトレンドにものってて驚き
余弦定理自体は覚えてました。2ab*cosC の符号は正三角形の時を考えれば楽かも。
むしろ cosC ってどうやってやるのかを調べました。
提出：
Submission #13310399 - AtCoder Beginner Contest 168

Eは 添え字をまとめて Ai/Bi = -Bj/Aj とするのはすぐできましたが、どう数えればいいかわからず終了。また解説を読んでも、python では小数点を１７桁程度で四捨五入を行うため、
Ai/Bi = 1/(Bi/Ai) とはならないのを知らなかったため、ずっとWAを出していました。
((A, B) = (1252581831207977, 465141368948)とかでやってみるとわかる）
そのため、Ai と Bi の最大公約数を g として、Ai/Bi を (Ai/g, Bi/g) として値を整数値で管理することで解決します。
ただし、Ai をつねに正とするなどの制約をしないと (-a,b) と (a,-b) を区別するので注意。
やること多すぎ。

Fは座標圧縮してbfs するのは分かるんだけど実装はできぬ。
座圧わからん。