keyword dijkstra 無向グラフ C++ 概要 長さ付きの無向辺が与えられる。ノードNからノード1への最短路を求める問題。 純粋なdijkstraの問題。ここぞとばかりにライブラリの実験をしてみた。一応無事AC。ちなみに同じノード間を繋ぐが長さが違う辺もあるらし…

keyword greedy C++ 概要 円の半径Rと数列x_iが与えられる。円の中心をx_iのいずれかに置いて円が全ての点x_iを被覆するようにしたい。置く円の最小個数を求める問題。 x_iをソートして小さい方から順に処理する。x_i+kに円を置いてもx_iが被覆されるならx_i…

keyword swap回数 行列 greedy C++ 概要 行列が与えられる。隣接する行を入れ替えることにより行列を下三角化したい。必要なswapの最小回数を求める問題。ただし下三角化できることは仮定してよい。 swapの回数は貪欲にやれば最小回数になるはず。それが分か…

keyword C++ 概要 同じ長さの数列が2つ与えられる。適当に順序を入れ替えてできる内積の最小値を求める問題。 小さい値の寄与を大きくして、大きい値の寄与を小さくすればいいんだから降順と昇順にしたものの内積をとれば良さそう。本当か？取りあえず書く量…

keyword 幾何 C++ 概要 平面上に犬とリスがいる。穴がいくつかある。犬はリスの2倍の速度で動く。リスが犬より早くたどり着けるような穴があるかどうか判定する問題。 距離が2倍以上離れているかどうかだけ見れば良い。出力の際にピリオド忘れてWAもらったけ…