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

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

最適解の数え上げ

AtCoder ABC 211 D - Number of Shortest paths (茶色, 400 点)

「最適解の個数」を求めるという超典型! 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。 頂点 から頂点 へと至る最短経路の本数を 1000000007 で割った余りを答えてください。 制約 解法 最短路を求めるだけならば、BFS を使うこ…

AOJ 2594 Reverse a Road II (JAG 模擬地区 2014 F) (600 点)

ネットワークフローアルゴリズムの構造をちゃんと理解しているかを問う良問ですね!! 問題へのリンク editorials 問題概要 頂点数 、辺数 の有向グラフ と、2 頂点 が与えられます。 いま、グラフの辺を 1 本選んで向きを反転させます。それによって、- 間…

JOI 春合宿 2008 day3-1 Origami (難易度 6)

一見すると典型的な「座標圧縮」+「二次元いもす法」なのだが、それだと TLE / MLE してしまう。 ジャッジへのリンク 問題文へのリンク 問題概要 のグリッド上に 枚の長方形の紙を敷いていく。 枚目の紙は を満たす座標 を覆う領域に配置される。最も多くの…

Educational Codeforces Round 2 E. Lomsat gelral (R2300)

マージテク童貞を卒業した!!! 問題へのリンク 問題概要 頂点の根付き木が与えられる (根の番号は 1)。また各頂点 には色 が塗られている。色は整数値で表される。各頂点 について、以下の問いに答えよ。 その頂点を根とした部分木を考える その部分木で「…

動的計画法で求めた解を全列挙する方法

きっかけは、タピオカ流競プロ優勝ガール、マリーさんのツイートでした。 100個ぐらいある整数から自由に選んでK円になる組み合わせを探せ!複数通りある場合は列挙!みたいな仕事がだるすぎてdpで列挙してくれるやつ作った競プロは事務員を救う— マリー (@C…

AtCoder ABC 057 D - Maximum Average Sets (青色, 400 点)

これは単に二項係数知っているかを問う感じ...? この頃と今とでは、多少問題傾向も違う気がする。 問題へのリンク 問題概要 個の数値が与えられる。このうち 個以上 個以下を選ぶときのその平均値の最大値を求めよ。 また最大を達成する選び方が何通りある…

AtCoder ARC 060 F - 最良表現 (赤色, 900 点)

今回は Suffix Array でやってみたけど、ローリングハッシュとか、KMP とか、Z-Algorithm とか、色んな方法があるみたいなので追々やってみたい。 → やってみた (3/14) 問題へのリンク 問題概要 文字列 がよい文字列であるとは「いかなる文字列 および 2 以…

CS Academy 069 DIV2 C - Build Correct Brackets (最短経路数も一緒に求める最短路!)

まさにこれだったん。 CSA 069 DIV2 C Build Correct Brackets ()()))(())() のようなカッコ列が与えられる。 最小回数flipして正しいカッコ列にせよ。 また最小回数flipで正しいカッコ列にする方法の数を数え上げよ。 ・1 <= 文字列長 <= 2500 まさに最短路…

最短経路の個数も一緒に数え上げる最短経路アルゴリズム

ARC 090 E - Avoiding Collision で話題になったこともあり、簡単にメモします。 最短経路を求める DP 的処理をするとき、DAG上のDP だろうと、BFS だろうと、Dijkstra だろうと、以下のような緩和処理をやっています // Edge e の緩和 int dp[MAX_V]; // dp…