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

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

BFS

AtCoder ABC 146 D - Coloring Edges on Tree (400 点)

軽めの構築問題!! 今回は「最大次数」というのが割と明らかだけど、しっかり構築法踏まえて証明する練習をすると、高難易度問題にも繋がりそう! 問題へのリンク 問題概要 頂点の木が与えられる。 本の辺に色を塗っていきたい。ただし、どの頂点についても…

JOI 二次予選 2020 D - テンキー (Tenkey)

本選参加のボーダーとなった問題らしい!それにしても JOI は実装が重たい...!!! 問題へのリンク 問題概要 初期状態では下図のようなテンキーの「0」のところにカーソルがある。 上下左右への移動 ボタンを押す (315 に 4 を押すと 3154 になる) を最小回…

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

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

AtCoder ABC 161 D - Lunlun Number (400 点)

この手の DFS、一時期全然見なかったけど、最近復活してきた! 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…

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

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

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 などでは特に、この手の問題は何度も何度も出題されていた。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えらえる。頂点 から頂点 へと、けんけんぱで…

AtCoder AGC 033 A - Darker and Darker (300 点)

また一つ、教育的 & 典型的な BFS 問が誕生した!!! 問題へのリンク 問題概要 × のグリッドがあって、各マスは「白」「黒」に塗られている。 1 秒ごとに、各黒マスに対し、その上下左右に隣接したマスが存在するならば、そのマスを黒く上塗りしていく。全…

AtCoder ABC 088 D - Grid Repainting (400 点)

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

AISing Programming Contest 2019 C - Alternating Path (300 点)

DP とかメモ化再帰とか考え出すとドツボにはまる...素直な考察が大事だね。 問題へのリンク 問題概要 H × W のグリッドが与えられる。各マスは白か黒で塗られている。「黒」マスと「白」マスのペアであって、 黒マスから出発して、隣接するマスを辿っていく…

AOJ 2891 な◯りカット (AUPC 2018 day3 C)

なもりなもり。サイクルが 1 個だけある連結グラフ、すなわち「木」に辺を 1 個くわえてできるグラフのことなん。 問題へのリンク 問題概要 N 頂点のなもりグラフが与えられる。以下の Q 個のクエリに答えよ。 2 頂点 a, b の間を分断するのに最小何個の辺を…

Codeforces Manthan Codefest 18 D - Valid BFS?

こういうの超苦手。。。解き方はわかるけど実装を工夫する感じの。 問題へのリンク 問題概要 N 頂点のツリー (頂点番号は 1, 2, ..., N) と、(1, 2, ...., N) の順列 a が与えられる。 このツリーを頂点 1 から出発して BFS したとして、その頂点訪問順序が …

AtCoder ARC 099 E - Independence (700 点)

いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たいのん。こういうのを素早く通せるようになりたいん。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷…