けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

最短路問題

AOJ ???? Flipping a Path (HUPC 2020 day3-L)

こういう系すごく楽しいよね 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向単純グラフ が与えられる。 このグラフ上で次の条件を満たすパス (同じ頂点を二度通らないものに限る) が存在するかどうかを判定し、そのようなパスの重みの最小値を求めよ…

AtCoder ABC 168 D - .. (Double Dots) (400 点)

BFS 木とか、BFS による経路復元とか、その辺りの理解を問いかける教育的問題だった!!! 問題へのリンク 問題概要 頂点、 辺の無向グラフが与えられる。頂点 1 以外のすべての頂点に対し「みちしるべとなる頂点」を、以下の条件を満たすように設定すること…

AtCoder ABC 164 E - Two Currencies (500 点)

これ、頂点を倍加してダイクストラする系。 問題へのリンク 問題概要 頂点 辺の連結な無向グラフが与えられる。各辺 には 通行に要する料金 円 (所持金が 以上でなければ通行できない) 通行に要する所要時間 秒 という属性がある。また、各頂点 では所持金を…

AtCoder ABC 160 D - Line++ (400 点)

すごく色んな考え方ができる問題ですね! 問題へのリンク 問題概要 個の頂点を持つ無向グラフ がある。 の辺集合は と とを結ぶ辺 頂点 と頂点 とを結ぶ辺 とで構成されている。各 に対して、最短距離が であるような頂点対が何個あるかを求めよ。 制約 考え…

AtCoder ABC 079 D - Wall (400 点)

Floyd--Warshall と、あとグリッド上の各マスは独立に考えて OK。 問題へのリンク 問題概要 のグリッドがあって、各マスには -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 のいずれかの数値が書かれている。目的は -1 以外のマスをすべて 1 に変えることである。 各マ…

Educational Codeforces Round 83 G. Autocompletion

頑張って DFS だけで通した!!! 問題へのリンク 問題概要 頂点数 の Trie 木と、そのうちの 個の頂点集合 が与えられる。 の各頂点 について、トライ木の根から出発して、以下の操作によって到達するまでの最小コストを求めよ。 トライ木の辺を 1 本先に進…

Codeforces Round #625 (Div. 1) B. Navigation System (R1800)

似たようなことは考えたことがあった。経路復元に関する理解を問う教育的問題! 問題へのリンク 問題概要 重みなしの有向グラフと、2 頂点 s, t を始点と終点にもつパスが与えられる。今、われわれはナビに沿ってこのパスをたどっている。ナビの仕様は次の通…

フォルシアゆるふわ競プロオンサイト #3 E - Sweets Distribution(Hard)

面白かった。セグ木にこういうの乗っけるの楽しい! 問題へのリンク 問題概要 の盤面の各マスに整数値が書かれている。このマスに対して、適切に を決めて、 盤面の 0 行目の区間 の総和 盤面の 1 行目の区間 の総和 盤面の 2 行目の区間 の総和 盤面の 3 行…

AtCoder ABC 151 D - Maze Master (400 点)

面白かった。BFS したり、Warshall--Floyd したり。 問題へのリンク 問題概要 の盤面が与えられる。各マスは '.' か '#' のいずれかである。それぞれ「通路」と「壁」を表している。 「通路を 2 箇所 指定したときの、上下左右に通路のみをたどって から へ…

AtCoder ABC 143 E - Travel by Car (500 点)

この Floyd--Warshall は天才すぎる! 問題へのリンク 問題概要 頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。 各頂点では燃料を補給できて、補給すると満タン (容量 の…

AtCoder ABC 142 F - Pure (600 点)

色んな方法がありそう。 問題へのリンク 問題概要 頂点数 、辺数 の単純な有向グラフが与えられる。なお各有向辺の向きをなくして得られる無向グラフも単純であるとする (有向辺 (u, v) があったら辺 (v, u) はない)。 このグラフの有向サイクルであって、有…

Codeforces Round #584 - Dasha Code Championship F. Koala and Notebook (R2600)

勉強になった!!!!! 「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。 最短路として使われうる辺を列挙しておく (この考え方自体が典型) その辺をうまいこと活用しながら探索する という典型の流れになっている。 問題への…

AtCoder ABC 132 E - Hopscotch Addict (500 点)

こういうのを僕が初めて解いたのは、はまづさんのこの問題だった。 atcoder.jp そして、昔の ICPC などでは特に、この手の問題は何度も何度も出題されていた。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えらえる。頂点 から頂点 へと、けんけんぱで…

Mujin 2018 E - 迷路 (500 点)

各地点に早くたどり着いておくに越したこと無い系問題!! atcoder.jp 問題概要 のグリッドがあってスタートからゴールへと行きたい。壁のあるマスは通れない。 ただし毎秒ごとに移動できる方向に制限がある。 で割ったあまりがそれぞれの場合についてどの方…

AOJ 2171 Strange Couple (AOJ-ICPC 600 点)

ランダムウォークな問題! 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…

AOJ 3055 こたつがめを燃やさないで (RUPC 2019 day2-E)

こういうの超苦手系だけど、苦手なりに解法を詰められたのは成長の証で嬉しい! olphe たん、ナンさんとチームを組んでいて、olphe たんに考察を話して、詰めてくれて、爆弾周りの見落としがあって詰まって、みんなでデバッグして...とチーム戦ならではの考…

AtCoder ABC 088 D - Grid Repainting (400 点)

グリッド上をスタートからゴールまで行く系の問題において、しばしばある 盤面に対し、何らかの形でコストを払ったりスコアを獲得したりしながら変更を加えられる という設定の問題。その設定が加わると難しい問題になることも多いが、この問題は比較的素直…

AOJ 3053 Phone Number (RUPC 2019 day2-C)

一瞬詰まった。とりあえず 9! できるなと思ったあと、長さ の文字列を処理するのはどうするんだろ...となっていた。前処理が本質な感じがする。 問題へのリンク 問題概要 "31415926535" のような 1 〜 9 からなる長さ の文字列 が与えられる。 今、 137 456 …

AtCoder ABC 073 D - joisino's travel (400 点)

Floyd-Warshall で前処理してどうのこうのする問題。特に ICPC 系などでよくある! 問題へのリンク 問題概要 頂点 辺の重み付き無向グラフが与えられる。このグラフ上で 個のチェックポイントをなす頂点集合が指定されている。好きなチェックポイントからス…

AtCoder ABC 061 D - Score Attack (400 点)

ちょっと注意が必要な Bellman-Ford 法の典型題。昔の AtCoder はこういうのもあったのか... 問題へのリンク 問題概要 頂点 辺の重み付き有向グラフが与えられる。頂点 1 から頂点 N への最長路の長さを求めよ。無限に大きくできる場合は "inf" と出力せよ。…

AOJ 2872 最短距離を伸ばすえびちゃん (RUPC 2018 day3-F)

ABC 051 D - Candidates of No Shortest Paths をやった流れで。この問題なら自然だけど、ちょっと設定変えた問題に超グロ問があったりする (AOJ 2230 How to Create a Good Game)。 問題へのリンク 問題概要 頂点 辺の重み付き有向グラフが与えられる。グラ…

AtCoder ABC 051 D - Candidates of No Shortest Paths (400 点) 〜 3 通りの解法 〜

「最短路として選ばれる可能性がないところを挙げる」というのは、それ自体、高難易度問題で部分的に必要になる考察だったりするね。 問題へのリンク より高難易度な問題の部分問題となる例として、 RUPC 2018 day3-F 最短距離を伸ばすえびちゃん がある。こ…

AtCoder ARC 064 E - Cosmic Rays (600 点)

昔の AtCoder はこういうのもあったのか!!! 問題へのリンク 問題概要 二次元平面上に、 個の円がある。二次元平面上の点 から点 へと進むことを考える。秒速 1 だけ進む。 そのような方法のうち、円外の領域を進んでいる時間の最小値を求めよ。 制約 考え…

AOJ 2200 Mr. リトー郵便局 (ICPC 模擬国内 2010 D)

問題文長い... 問題へのリンク 問題概要 頂点、 辺の重み付き無向グラフが与えられる。各辺は「陸路」「海路」の属性がある。このグラフを、最初頂点 にいて、 の順番に最短時間で巡りたい (順番的に後の頂点を先に通ってもよいが、その頂点より前の指定頂点…

AOJ 2402 天の川 (ICPC 模擬国内 2012 D)

コピペできる環境だったからライブラリで殴ったけど、ICPC 環境だったらタイピング量を減らす工夫せなアカンかな... 問題へのリンク 問題概要 下図のような、五角星 個があって、 個目の五角星から 個めの五角星までの最短距離を求めよ。 制約 考えたこと 五…

AOJ 1183 鎖中経路 (ICPC 国内予選 2012 E)

あまり良くない方針でゴリ押してしまった。でもゴリ押しで通せることの証左になるかと思って記録してみることに 問題へのリンク 問題概要 下図のような「円の列」の内部だけを通る折れ線 (最初の円の中心と、最後の円の中心とを結ぶ) の長さの最小値を求めよ…

AOJ 3044 Timing (AUPC 2018 day3 F)

整数の三分探索は闇... 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。時刻 0 に頂点 を出発し、頂点 まで移動するのに要する最小時間を求めよ。 各辺にはパラメータ が設定されていて、時刻 にその辺の片側の頂点から出発した場合、もう片側の…

AOJ 2892 しりとり圧縮 (AUPC 2018 day3 D)

迷走しないようにしたい問題。 問題へのリンク 問題概要 banana at tomb but tos sound does some のようなしりとりが与えられる。同じ文字で始まるところは 1 つにつぶすことができる。上の例で言えば (banana at tomb but) (tos) (sound does some) という…

JOI 2011 本選 E - JOI 国のお祭り事情 (AOJ 0575)

並列二分探索が想定ではなさそうだけど、並列二分探索のいい練習問題になったん!!! 問題へのリンク 問題概要 制約 解法 #include <iostream> #include <vector> #include <queue> #include <map> #include <algorithm> using namespace std; struct UnionFind { vector<int> par, rank, sz; UnionFind(in</int></algorithm></map></queue></vector></iostream>…

AOJ 1150 崖登り

えーーーーー、つらいけどむずかしくはなく、でもつらいん... 崖登り 問題概要 (略) 基本的にはグリッド上を移動していく最短路問題だけど、色々制約が付随している 考えたこと 一目見て Dijkstra 法が使えるとわかるけど、面倒... ポイントになりそうなのは…