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

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

DAG

AtCoder ABC 315 F - Shortcuts (青色, 500 点)

実は DP の添字の取りうる範囲が log オーダーであることを見抜く問題。より高度な問題でもしばしば見られる考え方。 問題へのリンク 問題概要 二次元平面上に点 がある。点 の座標は である。 今、点 1 にいて、原則として点 を順に通過して最終的に点 に到…

AtCoder ABC 324 F - Beautiful Path (青色, 500 点)

とても教育的問題!! 蟻本の二分探索の節に「平均値の最大化」があるけど、まさにそれ!!! 問題へのリンク 問題概要 頂点数 、辺数 の DAG が与えられる。各辺 について、 であることが保証される。 各辺 には、美しさ と、コスト がついている。 頂点 0 …

AOJ 2828 マトリョーシカ (JAG 模擬国内 2017 F) (550 点)

DAG の最小パス被覆、忘れた頃に出て来るイメージ! 問題へのリンク editorials 問題概要 個の直方体があり、 番目の直方体の大きさは である。 今、ある直方体の中に他のある直方体を入れたりすることで、外部から見えている直方体の体積を小さくしたい。た…

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

「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。 問題へのリンク editorial なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2…

AtCoder ARC 115 C - ℕ Coloring (茶色, 500 点)

これ茶色はさすがにびっくりした! 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…

JOI 本選 2007 D - 最悪の記者 (AOJ 0519, 難易度 7)

トポロジカルソートせよ、という問題! 問題へのリンク 問題概要 頂点数 、辺数 の DAG (閉路のない単純有向グラフ) が与えられる。 このグラフのトポロジカルソート順を一つ求めよ。また、トポロジカルソート順が唯一かどうかを判定せよ。 制約 考えたこと …

AOJ 2726 Black Company (JAG 夏合宿 2015 day4-J) (500 点)

素直に考えるとグラフの辺数が のオーダーになってしまうので、いかに削減するかを考える問題だった 問題へのリンク editorials 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。各頂点 には値 が振られている。今、各頂点にスコア を割り振りたい。…

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

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

早稲田大学プログラミングコンテスト WUPC 2019 F - RPG

フロー大好き!!!!!!!! 問題へのリンク 問題概要 頂点 辺の DAG が与えられる。頂点 からスタートして頂点 へと向かいたい。すべての頂点 に対し、 から へと向かうパスと、 から へと向かうパスが存在することが保証されている。 頂点のうちいくつか…

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

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

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

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