幾何の問題。特に「線分と線分の交差判定」に関する問題！ 問題へのリンク 問題概要 凸とは限らない 角形 が与えられる。 番目の頂点の座標は である。 この多角形 の外部に 2 点 , がある。この 2 点を結ぶことによって、多角形 をいくつかのピースに分ける…

グラフの入門に！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。 各頂点 に対して、「友達の友達」、つまり頂点 からの距離が 2 であるような頂点の個数を求めてください。 自分自身や、友達 (距離が 1 である頂点) は含めないも…

今の時代なら確実に灰色 diff ですね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。 頂点 と頂点 とを結ぶ辺は存在しないことがわかっている。 ある頂点 から 2 本の辺を辿ることで頂点 に到達できるかどうかを判定せよ。 制約 …

グラフで考えよう！ 問題へのリンク 問題概要 階建てのビルがあります。 ハシゴが 個あり、 個目のハシゴは 階と 階を結んでいます。これらのハシゴは双方に行き来できます。ただし、ハシゴ以外の手段によって、異なる階の行き来はできません。 高橋くんは最…

とてもいい感じの BFS の練習問題！ 問題へのリンク 問題概要 "atcoder" の並び替えである文字列 が与えられます。 文字列 に対して「隣接する 2 要素を swap する」という操作を繰り返すことで、"atcoder" となるようにしたいとします。 最小何回の操作で実…