LIS and LDS のバリエーション。 問題へのリンク 問題概要 1〜N の各順列について LIS (最長増加部分列) の長さが A LDS (最長減少部分列) の長さが B とする。A + B を最小化し、A + B が最小となるような順列を具体的に 1 つ求めよ。 制約 1 <= N <= 105 …

これは楽しい 問題へのリンク 問題概要 個の整数 が与えられる。 今ある整数の中から 1 個 ( とする) を選んで、好きな整数 を選んで、 を と に分裂させる という操作を繰り返して、最終的に得られる整数の集合が、まったく同一の 2 つの集合に分けられるよ…

てんぷら君が解いていたのを見て... 問題へのリンク 問題概要 頂点のツリーが与えられる。 ツリーの各頂点に 'A' 〜 'Z' のラベルを割り当てたい。アルファベット順に rank が低くなっていくものとする ('A' が最高ランク)。 任意の 2 頂点 u, v について、u…

の Kruskal 法ではダメで、 な Prim 法なら OK という稀有なパターンの問題。Dijkstra 法でも priority_queue を使ったやつは 愚直なやつは と二種類の実装があって前者の方が速いと言及されるケースも多いけど、密グラフ ( なグラフ) では後者の方が速い。P…

本番はツリーDPな方向性に走って詰め切れなかった。ひょっとしたらツリーDPでも解けるのかもしれないが復元が大変そう... CSA 069 DIV2 D Cover the Tree N 頂点からなるツリーが与えられる。 ツリーのすべての辺を最小本数のパスで覆え。そのようなパスの集…

詰め切るの大変だった！ 問題へのリンク editorials 問題概要 '0'〜'9' からなる長さ の文字列 が与えられる。 これらの文字列をいくつかの連続する部分文字列に分ける。次の条件を満たす必要がある。 各部分文字列を数値とみなしたとき、strictly に単調増…