最短路問題
多重 for 文の練習問題！ 問題へのリンク 問題概要 二次元平面上に 人の学生と、 個のチェックポイントがある。学生 は座標 にいて、チェックポイント は座標 にいる。 各学生について、その学生からマンハッタン距離が最も近いチェックポイントを求めよ (タ…
DP の経路復元を学ぶ問題。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 あるダンジョンには 個の部屋があり、 と番号がついている。このダンジョンは一方通行であり、通路を介して 1 つ先または 2 つ先の部屋に移動することができる。各通路に…
Frog 1 とほぼ同じ問題！ 問題へのリンク 問題概要 あるダンジョンには 個の部屋があり、 と番号がついている。このダンジョンは一方通行であり、通路を介して 1 つ先または 2 つ先の部屋に移動することができる。各通路における移動時間は以下の通り。 部屋…
「実は各点から左右に見て最も近い点だけ見れば良い」という点気考察をする！ 問題へのリンク 問題概要 数直線上に 個の絵がある。 番目の絵のある位置の座標は であり、'J', 'O', 'I', 'G' のいずれかの文字 が書かれている。 これらの絵に対して、以下の …
実はクエリごとに毎回愚直に Dijkstra 法を回しても間に合う！ 問題へのリンク 問題概要 最初、辺数 0 本、頂点数 個のグラフが与えられる。頂点番号は である。このグラフに対して 回のクエリが投げられる。 クエリタイプ 0：2 頂点 が指定されるので、頂点…
とても重たくて大変な問題。いろんな整理の仕方があると思う。 問題へのリンク 問題概要 下図のように、座標平面が 1 x 2 の長方形に区切られている。 座標 から座標 へと至るまでに、通過する必要のある長方形の境界の個数の最小値を求めよ。 制約 考えたこ…
よくある、パズルの最小手数を求める問題！ この手の問題では、まず「あり得る状態」がどれだけあるかを見積もろう！ 問題へのリンク 問題概要 マスがあって、最初、前から マスには白石か黒石のいずれかが置かれている。置かれ方は文字列 で表される。後ろ …
この時代は Greedy が多かった。そして、実はすごく単純なことに気がつくかどうかが問われる問題！ 問題へのリンク 問題概要 数直線上 (東西方向) に 個の町があり、それぞれの町の座標は である。町 1 から出発して、すべての町を訪れたい。次の 2 つの手が…
この頃によくあった 3 個の入力をどうのこうのする系！ 問題へのリンク 問題概要 3 つの空港 A, B, C がある。 A-B 間の移動の所要時間は B-C 間の移動の所要時間は A-C 間の移動の所要時間は 今、これらの空港を順に訪れる (たとえば、B → A → C)。最短の所…
実は DP の添字の取りうる範囲が log オーダーであることを見抜く問題。より高度な問題でもしばしば見られる考え方。 問題へのリンク 問題概要 二次元平面上に点 がある。点 の座標は である。 今、点 1 にいて、原則として点 を順に通過して最終的に点 に到…
少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題！ 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…
とても教育的問題！！ 蟻本の二分探索の節に「平均値の最大化」があるけど、まさにそれ！！！ 問題へのリンク 問題概要 頂点数 、辺数 の DAG が与えられる。各辺 について、 であることが保証される。 各辺 には、美しさ と、コスト がついている。 頂点 0 …
怒りの場合分け。ちょっと苦手系だけど一発 AC できてよかった。 問題へのリンク 問題概要 高橋君は現在 にいて、荷物は にあり、荷物を目的地 に届けたい。 高橋君は荷物のある位置に入ることはできず、荷物と隣接した状態から荷物の方向に移動すると、荷物…
Library Checker というと難しいイメージがあるけど、この問題のように基本的な問題もある。でも、「最短路の復元」を要求する問題は意外と少ないので、とても貴重な問題！ 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き有向グラフが与えられる。…
セグ木上二分探索使ったというコメントをよく見たけど、僕の方針でも使うことになった 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き無向グラフが与えられる。 日目、 個の頂点 がウィルスに感染した。一度ウィルスに感染した頂点はずっと感染し…
人生で最初に解きたい BFS の問題！ 問題へのリンク 問題概要 のグリッドが与えられます。各マスは壁 (文字 '#')、通路 (文字 '.') のいずれかです。通路マスに入ることはできますが、壁マスに入ることはできません。 スタートマス (入力で与えられる) から…
最小回数を求めるには BFS！！(素振り) 問題へのリンク 問題概要 黒板に整数値 が書かれています。次のいずれかの操作を最小回数繰り返すことによって、整数値 の値を にしたいとします。 を 倍して にする を十進法表記したときに、末尾の値を先頭に持って…
「最適解の個数」を求めるという超典型！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。 頂点 から頂点 へと至る最短経路の本数を 1000000007 で割った余りを答えてください。 制約 解法 最短路を求めるだけならば、BFS を使うこ…
「ABC 301 E - Pac-Takahashi」の類題とも言うべき ICPC 系の問題！ 問題へのリンク (AOJ) 問題へのリンク (AtCoder) editorials 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点番号は とする。 番目の辺は頂点 を結んでおり、その重みは …
残り 1 分でなんとか通せた。 問題へのリンク 問題概要 頂点数 の連結な単純無向グラフ (頂点番号は であって、次の条件を満たすものの個数を で割ったあまりを求めよ。 なお、ここで、頂点 から各頂点 までの最短距離を としている。 制約 考えたこと グラ…
重み付き Union-Find が有効活用できる問題！ 問題へのリンク 問題概要 個の変数 の値を決定したい。 これらの値を決定するための 本の制約条件がある。このうち 個めの情報は 3 つの値 によって与えられ、 であるという制約条件を表す。 これら 本の制約条…
重み付き Union-Find が使える鮮やかな楽しい問題！ 問題へのリンク 問題概要 頂点数 (頂点番号が ) のグラフが与えられる。このグラフには 組の辺があり、 組目の辺は、 頂点 から頂点 へと、長さ の有向辺 頂点 から頂点 へと、長さ の有向辺 となっている…
迷路の最短路問題なので BFS でやりたくなるが、まともにやると で TLE してしまう！！ 頂点の持ち方を工夫して 0-1 BFS で解く！ 別解として枝刈り BFS も。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられます。各マスは通路 (文…
かの有名な「器物損壊！高橋君」の類題ですね。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドがあって、各マスは通路マス (.) か壁マス (#) のいずれかです。 今、左上のマス から右下のマス へと移動したいです。上下左右に移動することが…
「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。 問題へのリンク editorial なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2…
これほどシンプルな問題がグラフ最短路問題になるのは感動的ですね！ 問題へのリンク 問題概要 の正の倍数をすべて考えたときの、各桁の和として考えられる最小値を求めてください。 制約 うまく数字を並べるゲームと捉える の倍数をひたすら試す方法をまず…
通称 0-1 BFS と呼ばれるアルゴリズムが使える問題ですね。 問題へのリンク 問題概要 のマス目で表現された地図が与えられます。 . は通路、# は壁を表します。s マスから出発して、上下左右への移動を繰り返しながら g マスへと到達したいとします。. マス…
DIjkstra をするときに、直前の頂点ももつ系 問題へのリンク 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点 の座標は となっている。 頂点 1 から頂点 2 へと至る経路のうち、鋭角に曲がる箇所がないようなものを考える (頂点 の前の頂点…
難易度 8 でもおかしくないと思った。 B や C より易しい気がしなくもないけど、本番の緊張感で B や C を飛ばして D を本気で考える決断はなかなかできなさそう。今回は B - パンケーキを見て冷静になれたか勝負だね... 問題へのリンク 問題概要 個の工場が…
dp の値そのものを用いて現在状態を復元する系の問題。 問題へのリンク editorial 問題概要 個の木 があって、それぞれ高さは である。 フクロモモンガは最初は、木 1 の高さ の地点にいる。フクロモモンガは木を飛び移りながさ、最終的に木 の頂上にたどり…
