AtCoder Beginner Contest 168 振り返り
D - .. (Double Dots)
N本の部屋，M本の通路を持つ洞窟
洞窟内の各部屋から外に出るための最短ルートを進む際，次に向かうべき部屋を出力
達成できない部屋がある場合は"No"を出力
graph = [ for _ in range(N+1)]
graph[a].append(b)
graph[b].append(a)
これによって各部屋がどの部屋に繋がっているか書ける
入力1でのgraphは
[, [2], [1, 3, 4], [2, 4], [3, 2]]
幅優先探索の実装
queue = deque([1])
signposts = [0] * (N+1)
signposts[1] = 1
while queue:
u = queue.popleft()
for v in graph[u]:
if not signposts[v]:
signposts[v] = u
queue.append(v)
（入力１の処理例）
部屋1について
…
部屋2について
2からは1,3,4に移動できる
1については既出
3について，signpost = 2
4について，signpost = 2
queueには[3,4]が格納される
…
部屋3について，部屋4について…
全ての部屋に入っているかどうかは
if all(signposts[2:]):
print("Yes")
print("\n".join(map(str,signposts[2:])))
で確かめられる
・参考
Submission #13358850 - AtCoder Beginner Contest 168
E - ∙ (Bullet)
N匹のイワシについて，それぞれステータスA,Bが設定されている
この中から，Ai・Aj + Bi・Bj ＝ 0を満たす組み合わせが存在しないように，イワシを選ぶ方法は何通りあるか？
この問題で重要なのは，
イワシの「傾き」Ai/Biについて，A,Bのパラメーターの範囲が広く精度が足りないこと，
である
そこで行うこととして，まず「傾き」を既約分数の有理数で表す（具体的にはA,Bのgcdで割り，a,bで表現）ここでの出現回数をCounterで数え上げる．
例): Counter({(1, 2): 1, (1, -1): 1, (2, -1): 1})
最初に(0,0)を別物として扱う．
①「直交」している部分については，直交するところが一緒にならないように選ぶ
各要素 (a, b, v個) について，「直交」(b,-a)しているものがw個あったら -1 + 2^v + 2^w 通り
(それぞれ片方のみを選ぶ場合から一つも選ばないパターンを引く)
②それ以外の部分については 2^(直交していない要素の数和)
ここから誰も選ばなかった場合1通りを引き，
またこれにA,Bが（0,0）の場合の通りを足す（個数分だけ足す）
Submission #13414936 - AtCoder Beginner Contest 168
F - . (Single Dot)
草原に柵がおいてあり，この中で牛が動ける範囲を求める
方針：
線分のある座標だけ残し，圧縮座標に変換
壁の座標も考慮して2倍のグリッドを作成することで，DFSで解きやすくなる
DFSの例
while q:
x, y = q.pop()
if not x or not y:
print("INF")
sys.exit()
ans += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
if x and not wallx[x][y] and not cow[x - 1][y]:
cow[x - 1][y] = True
q.append*1
if y and not wally[x][y] and not cow[x][y - 1]:
cow[x][y - 1] = True
q.append*2
if x + 1 < n and not wallx[x + 1][y] and not cow[x + 1][y]:
cow[x + 1][y] = True
q.append*3
if y + 1 < m and not wally[x][y + 1] and not cow[x][y + 1]:
cow[x][y + 1] = True
q.append*4
圧縮座標の面積を足した後，上下左右方向に進む
x,yのどちらかが見つからない（つまりどちらかの次元で開いている）なら，答えは無限大
参考：
