atcoder.jp二分探索で求める方法もありますが、ここでは直接求めていきます。平面上で (0,0), (A,0), (A,B), (0,B) を頂点とする長方形の内部に入る正三角形を考えていくことにします。 1辺の長さが の正三角形の頂点の一つを原点(0,0) におくと、残りの2つ…

atcoder.jp 単純グラフ：多重辺も自己ループももたないグラフ 有向グラフ：辺に向きがある（矢印）グラフ条件から、「頂点 b を中心として、"入ってくる辺 a → b"と"出ていく辺 b → c"の各ペアについて、 bの相手の頂点を直接結ぶ辺 a → c が無ければ追加す…

atcoder.jp 連結成分を調べたいときは Union-Find 木 Union-Find 木 (「競技プログラミングの鉄則」 9.6 Union-Find 木) の考え方を利用します。 同じグループに属する頂点を木構造で表現することにして、頂点 x の親を parent[x] に記録していきます。 頂点…