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

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

CodeforcesR2600

Codeforces Round #673 (Div. 1) D. Graph and Queries (R2600)

いろんな方法がありそう。Union-Find のマージ過程を表す木でやったけど、ほかにも Undo 付き Union-Find を使うなど 問題へのリンク 問題概要 頂点数 、辺数 のグラフが与えられる。初期状態では各頂点に という値がついている (すべて 1 以上で disjoint)…

Codeforces Round #683 (Div. 1) D2. Frequency Problem (R3000)

平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…

Codeforces Round #684 (Div. 1) B. Graph Subset Problem (R2600)

TLE が厳しくて話題になってた 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ [tex G] が与えられる。また、正の整数 が与えられる。 以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。 type 1: の…

Educational Codeforces Round 83 G. Autocompletion (R2600)

頑張って DFS だけで通した!!! 問題へのリンク 問題概要 頂点数 の Trie 木と、そのうちの 個の頂点集合 が与えられる。 の各頂点 について、トライ木の根から出発して、以下の操作によって到達するまでの最小コストを求めよ。 トライ木の辺を 1 本先に進…

Educational Codeforces Round 81 F. Good Contest (R2600)

座標圧縮をがんばる 問題へのリンク 問題概要 個の区間 が与えられる。それぞれの区間から一様ランダムに整数を選んでいく。 これが広義単調減少となる確率を求め、それを 998244353 で割ったあまりの形式で求めよ。 制約 考えたこと 区間の幅は大きいが、 …

Codeforces Round #584 (Div. 1 + Div. 2) F. Koala and Notebook (R2600)

勉強になった!!!!! 「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。 最短路として使われうる辺を列挙しておく (この考え方自体が典型) その辺をうまいこと活用しながら探索する という典型の流れになっている。 問題への…