【問題集】最短路問題
実は DP の添字の取りうる範囲が log オーダーであることを見抜く問題。より高度な問題でもしばしば見られる考え方。 問題へのリンク 問題概要 二次元平面上に点 がある。点 の座標は である。 今、点 1 にいて、原則として点 を順に通過して最終的に点 に到…
少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題！ 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…
Library Checker というと難しいイメージがあるけど、この問題のように基本的な問題もある。でも、「最短路の復元」を要求する問題は意外と少ないので、とても貴重な問題！ 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き有向グラフが与えられる。…
人生で最初に解きたい BFS の問題！ 問題へのリンク 問題概要 のグリッドが与えられます。各マスは壁 (文字 '#')、通路 (文字 '.') のいずれかです。通路マスに入ることはできますが、壁マスに入ることはできません。 スタートマス (入力で与えられる) から…
最小回数を求めるには BFS！！(素振り) 問題へのリンク 問題概要 黒板に整数値 が書かれています。次のいずれかの操作を最小回数繰り返すことによって、整数値 の値を にしたいとします。 を 倍して にする を十進法表記したときに、末尾の値を先頭に持って…
「最適解の個数」を求めるという超典型！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。 頂点 から頂点 へと至る最短経路の本数を 1000000007 で割った余りを答えてください。 制約 解法 最短路を求めるだけならば、BFS を使うこ…
前処理して頂点数を減らしたグラフ上で TSP！！！ ICPC ではすごくよく見るパターンですね！ 問題へのリンク 問題概要 サイズのグリッドがある。各マスは 壁マス：'#' 通路マス：'.' お菓子マス：'o' (18 個以内であることが保証される) スタートマス：'S' …
迷路の最短路問題なので BFS でやりたくなるが、まともにやると で TLE してしまう！！ 頂点の持ち方を工夫して 0-1 BFS で解く！ 別解として枝刈り BFS も。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられます。各マスは通路 (文…
かの有名な「器物損壊！高橋君」の類題ですね。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドがあって、各マスは通路マス (.) か壁マス (#) のいずれかです。 今、左上のマス から右下のマス へと移動したいです。上下左右に移動することが…
通称 0-1 BFS と呼ばれるアルゴリズムが使える問題ですね。 問題へのリンク 問題概要 のマス目で表現された地図が与えられます。 . は通路、# は壁を表します。s マスから出発して、上下左右への移動を繰り返しながら g マスへと到達したいとします。. マス…
DIjkstra をするときに、直前の頂点ももつ系 問題へのリンク 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点 の座標は となっている。 頂点 1 から頂点 2 へと至る経路のうち、鋭角に曲がる箇所がないようなものを考える (頂点 の前の頂点…
難しかった！！！ 予選の問 2 からこういうの出るのびっくり！！！ 問題へのリンク 問題概要 "A", "B", "C" からなる文字列 に対して、以下の操作を繰り返すことでソートされた状態 ("A" の前には "B" や "C" がなく、"B" の前には "C" がない状態) にするこ…
おおむね BFS だけど、ちょっとだけ TLE に注意。。。 問題へのリンク 問題概要 のグリッドが与えられる。"." は通路マス、"#" は壁で侵入不能マス、"S" はスタート、"G" はゴールである。さらに英小文字で表された各マス間は 1 手で自由にワープで行き来可…
TSP だ！！ 問題へのリンク 問題概要 3 次元空間内に 個の都市、都市 1 から 都市 N がある。 座標 の都市から の都市に移動する際には のコストがかかる。 都市 1 からスタートし、全ての都市を 1 度以上巡って都市 1 に戻るまでの最小コストを求めよ。 制…
難しかった 問題へのリンク 問題概要 体重が であるような 体のラクダがいる。ラクダを一列に並べる方法のうち、次の条件を満たすものについて、左端のラクダと右端のラクダの距離として考えられる最小値を求めよ。また、そのようにラクダを並べることが不可…
これ、頂点を倍加してダイクストラする系。 問題へのリンク 問題概要 頂点 辺の連結な無向グラフが与えられる。各辺 には 通行に要する料金 円 (所持金が 以上でなければ通行できない) 通行に要する所要時間 秒 という属性がある。また、各頂点 では所持金を…
すごく色んな考え方ができる問題ですね！ 問題へのリンク 問題概要 個の頂点を持つ無向グラフ がある。 の辺集合は と とを結ぶ辺 頂点 と頂点 とを結ぶ辺 とで構成されている。各 に対して、最短距離が であるような頂点対が何個あるかを求めよ。 制約 考え…
Floyd--Warshall と、あとグリッド上の各マスは独立に考えて OK。 問題へのリンク 問題概要 のグリッドがあって、各マスには -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 のいずれかの数値が書かれている。目的は -1 以外のマスをすべて 1 に変えることである。 各マ…
「予め盤面をいじることができる」という設定の問題にはある程度の定石があるように思う！ 問題へのリンク 問題概要 の盤面が与えられ、左上から右下まで行きたい。'#' マスは壁を表し、'.' マスは通路を表す。 予め盤面に以下の操作を行うことができる。最…
面白かった。BFS したり、Warshall--Floyd したり。 問題へのリンク 問題概要 の盤面が与えられる。各マスは '.' か '#' のいずれかである。それぞれ「通路」と「壁」を表している。 「通路を 2 箇所 指定したときの、上下左右に通路のみをたどって から へ…
この Floyd--Warshall は天才すぎる！ 問題へのリンク 問題概要 頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。 各頂点では燃料を補給できて、補給すると満タン (容量 の…
グラフの頂点を倍加するタイプの問題ですね。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えらえます。頂点 から頂点 へと、けんけんぱで移動したいものとします。 1 回のけんけんぱでは、「自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接…
また一つ、教育的 & 典型的な BFS 問が誕生した！！！ 問題へのリンク 問題概要 × のグリッドがあって、各マスは「白」「黒」に塗られている。 1 秒ごとに、各黒マスに対し、その上下左右に隣接したマスが存在するならば、そのマスを黒く上塗りしていく。全…
こういうの超苦手系だけど、苦手なりに解法を詰められたのは成長の証で嬉しい！ olphe さん、ナンさんとチームを組んでいて、olphe さんに考察を話して、詰めてくれて、爆弾周りの見落としがあって詰まって、みんなでデバッグして...とチーム戦ならではの考…
Floyd-Warshall で前処理してどうのこうのする問題。特に ICPC 系などでよくある！ 問題へのリンク 問題概要 頂点 辺の重み付き無向グラフが与えられる。 このグラフ上で 個のチェックポイントをなす頂点集合が指定されている。好きなチェックポイントからス…
一見、ツリー上のパスクエリ (オイラーツアーとかするやつ) な問題に見えるけど、そんなことはなかった 問題へのリンク 問題概要 頂点のツリー (辺に重み付き) が与えられる。ツリー上の 1 点 が与えられて、以下のクエリに 個答えよ: クエリ (): から を経…
Bellman-Ford 法を活用する典型問題ですが、少し注意が必要な問題ですね。 問題へのリンク 問題概要 頂点 辺の重み付き有向グラフが与えられます。 頂点 から頂点 へと至る最長路の長さを求めてください。 ただし、いくらでも長い路が存在する場合は inf と…
「最短路として選ばれる可能性がないところを挙げる」というのは、それ自体、高難易度問題で部分的に必要になる考察だったりするね。 問題へのリンク より高難易度な問題の部分問題となる例として、 RUPC 2018 day3-F 最短距離を伸ばすえびちゃん がある。こ…
ソートする問題。 問題へのリンク 問題概要 個のコマを数直線上に配置して、それぞれ移動させる。 それによって、 個の地点 をすべて訪れるようにしたい。総移動距離の最小値を求めよ。 制約 考えたこと とりあえず、各コマについて、「行って、引き返して」…
昔の AtCoder はこういうのもあったのか！！！ 問題へのリンク 問題概要 二次元平面上に、 個の円がある。二次元平面上の点 から点 へと進むことを考える。秒速 1 だけ進む。 そのような方法のうち、円外の領域を進んでいる時間の最小値を求めよ。 制約 考え…
