[AtCoder] ABC 204 C – Tour
スタートとゴールの組合せは最大でも \( N^2 \) であることが分かります.ある国から到達することが可能な国を探索するために必要な計算量は,同じ道を通る必要がないことを考慮して \( O(N + M)\) となります.した ...
[AtCoder] ABC 184 E – Third Avenue
文字列 ‘a’ のマスのリストを \( a \) とし、マス ‘S’ からマス \( p \) の最短距離を \( d(p) \) とします。探索は迷路で使われるような幅優先探索 ...
[AtCoder] ACL Beginner Contest C – Connect Cities
グラフが連結かどうかを調べるには Union-Find を使えば良いので、ライブラリの dsu を使います。グループの数から \( 1 \) を引いた値が必要な道路の本数です。グループの数は、groups( ...
[AtCoder] ABC 177 D – Friends
友達同士のグループの人数の最大値の分だけグループがあれば、「同じグループの中に友達がいない」という状況がつくれます。したがって、連結成分の最大値を求めます。これは、幅優先探索や Union-Find を使うことで求めることがで ...
[AtCoder] ABC 176 D – Wizard in Maze
徒歩で行くことができるマスをグループ化し、IDを振ります。マス \( (i, j) \) の ID が \( 0\) であることを \( G(i, j) = 0 \) と表し、そのマスから徒歩でいけるマスの ID は ...
[AtCoder] ABC 168 D – .. (Double Dots)
幅優先探索で迷路を解くような感じで考えます。始点 \( 1 \) から幅優先探索を行い、到達した部屋の道しるべは、直前に来た部屋となります。隣接リストを作成し、到達した部屋のフラグを管理することで探索を行います。
コード ...
[AtCoder] ABC 151 D – Maze Master
良くある迷路の探索のアルゴリズムを使って、全探索を行います。ここでは、全ての道となっているマスから幅優先探索を行い、到達可能なマスの最短距離を求めます。
コード#include <bits/stdc++.h>usi ...
[AOJ] No. 0321 部活動調査
各生徒をノードに見立てて、隣接リストを構築します。生徒 \( i \) が所属している部活動を \( g_i \) とし、所属が未確定のときを \( g_i = 0 \) とします。生徒 \( a, b \) が同じ部活動に所 ...
[AtCoder] ABC 146 D – Coloring Edges on Tree
必要な色の数は、頂点の最大次数となるので、任意の頂点から幅優先探索を行い、色を振り分けていきます。辺の色を順番に出力する必要があるので、マップを使って管理します。また、色を分けるときに使用できない色を管理するためにセットを使い ...
[AtCoder] ABC 087 D – People on a Line
座標間の距離が与えられるので、相対的な位置が分かります。したがって、ある座標の値を \( x_i = 0 \) として、\( M \) 個の情報に誤りがあるかどうかを調べます。
グラフ各座標をグラフの頂点として、\ ...