BFS
おおむね BFS だけど、ちょっとだけ TLE に注意。。。 問題へのリンク 問題概要 のグリッドが与えられる。"." は通路マス、"#" は壁で侵入不能マス、"S" はスタート、"G" はゴールである。さらに英小文字で表された各マス間は 1 手で自由にワープで行き来可…
状態空間を上手に削減する系の問題 問題へのリンク editorial 問題概要 種類の長方形形状 () をしたスタンプがある (それぞれ「赤」「緑」「青」の 3 種類がある)。 これらを使って 4 × 4 のグリッド上に所望の模様を作りたい。グリッドからはみ出して押して…
条件反射で二分探索してしまった！！！この問題めっちゃ面白くて好き！！！ 問題へのリンク editorial 問題概要 平面上に 2 直線 で囲まれた通路がある。この通路の中の の部分に 本の大きさの無視できる釘が打たれており、 本目の釘の座標は である。 高橋…
LCA ライブラリを持っていれば書くだけ！ 問題へのリンク editorial 問題概要 頂点の根付き木が与えられる (根は頂点 0)。この木上で幅優先探索を行う (隣接する頂点のうち、頂点番号が小さい順にキューに push する)。 このとき、探索順序が であったとした…
Union-Find の典型的な問題！！ でも、DFS や BFS でも解くことができる。 問題へのリンク 問題概要 人 から 人 までの 人の人がいます。 「人 と人 は友達である」という情報が 個与えられます。同じ情報が複数回与えられることもあります。 と が友達、か…
Union-Find の練習問題という雰囲気ながら、DFS や BFS でも解ける 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。これに最小本数の辺を追加することで全体が連結となるようにしたい。その最小本数を求めよ。 制約 考えたこと 全体…
フローって確かに天才パズルな問題はすごく天才的なんだけど、典型的な問題もたくさんある！ 問題へのリンク 問題概要 下図のような の盤面が与えられる。盤面は通路 ('.') と壁 ('#') がある。いくつかの通路にはコマ ('o') が配置されている。 コマは下方…
BFS 木とか、BFS による経路復元とか、その辺りの理解を問いかける教育的問題だった！！！ 問題へのリンク 問題概要 頂点、 辺の無向グラフが与えられる。頂点 1 以外のすべての頂点に対し「みちしるべとなる頂点」を、以下の条件を満たすように設定すること…
軽めの構築問題！！ 今回は「最大次数」というのが割と明らかだけど、しっかり構築法踏まえて証明する練習をすると、高難易度問題にも繋がりそう！ 問題へのリンク 問題概要 頂点の木が与えられる。 本の辺に対して、なるべく少ない種類の色を用いて色を塗っ…
本選参加のボーダーとなった問題らしい！それにしても JOI は実装が重たい...！！！ 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 初期状態では下図のようなテンキーの「0」のところにカーソルがある。 上下左右への移動 ボタンを押す (315 …
すごく色んな考え方ができる問題ですね！ 問題へのリンク 問題概要 個の頂点を持つ無向グラフ がある。 の辺集合は と とを結ぶ辺 頂点 と頂点 とを結ぶ辺 とで構成されている。各 に対して、最短距離が であるような頂点対が何個あるかを求めよ。 制約 考え…
この手の DFS、一時期全然見なかったけど、最近復活してきた！ 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…
似たようなことは考えたことがあった。経路復元に関する理解を問う教育的問題！ 問題へのリンク 問題概要 重みなしの有向グラフと、2 頂点 s, t を始点と終点にもつパスが与えられる。今、われわれはナビに沿ってこのパスをたどっている。ナビの仕様は次の通…
面白かった。BFS したり、Warshall--Floyd したり。 問題へのリンク 問題概要 の盤面が与えられる。各マスは '.' か '#' のいずれかである。それぞれ「通路」と「壁」を表している。 「通路を 2 箇所 指定したときの、上下左右に通路のみをたどって から へ…
色んな方法がありそう。 問題へのリンク 問題概要 頂点数 、辺数 の単純な有向グラフが与えられる。なお各有向辺の向きをなくして得られる無向グラフも単純であるとする (有向辺 (u, v) があったら辺 (v, u) はない)。 このグラフの有向サイクルであって、有…
勉強になった！！！！！ 「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。 最短路として使われうる辺を列挙しておく (この考え方自体が典型) その辺をうまいこと活用しながら探索する という典型の流れになっている。 問題への…
グラフの頂点を倍加するタイプの問題ですね。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えらえます。頂点 から頂点 へと、けんけんぱで移動したいものとします。 1 回のけんけんぱでは、「自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接…
また一つ、教育的 & 典型的な BFS 問が誕生した！！！ 問題へのリンク 問題概要 × のグリッドがあって、各マスは「白」「黒」に塗られている。 1 秒ごとに、各黒マスに対し、その上下左右に隣接したマスが存在するならば、そのマスを黒く上塗りしていく。全…
グリッド上をスタートからゴールまで行く系の問題において、しばしばある 盤面に対し、何らかの形でコストを払ったりスコアを獲得したりしながら変更を加えられる という設定の問題。その設定が加わると難しい問題になることも多いが、この問題は比較的素直…
DP とかメモ化再帰とか考え出すとドツボにはまる...素直な考察が大事だね。 問題へのリンク 問題概要 のグリッドが与えられる。各マスは白か黒で塗られている。「黒」マスと「白」マスのペアであって、 黒マスから出発して、隣接するマスを辿っていくことで…
サイクルが 1 個だけある連結グラフ、すなわち「木」に辺を 1 個くわえてできるグラフのことを、なもりグラフと呼ぶことにする。 問題へのリンク 問題概要 N 頂点のなもりグラフが与えられる。以下の Q 個のクエリに答えよ。 2 頂点 a, b の間を分断するのに…
こういうの超苦手。。。解き方はわかるけど実装を工夫する感じの。 問題へのリンク 問題概要 N 頂点のツリー (頂点番号は 1, 2, ..., N) と、(1, 2, ...., N) の順列 a が与えられる。 このツリーを頂点 1 から出発して BFS したとして、その頂点訪問順序が …
いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たい。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷似) POJ 3692 Kindergarten (補グラフとって二部グ…
