値A[i]を頂点に持たせたグラフを考える
まず、これをグラフの問題として捉えるところに、一つ山がある印象だけど、みんなあっさり超えていてすごい! 問題へのリンク 問題概要 以下の正整数からなる長さ の数列 、 が与えられる。これらの数列の組が次の条件を満たすかどうかを判定せよ。 0 と 1 …
下手を打つと密なグラフになって TLE してしまう!! スーパーノードを作ることでグラフを sparse にするテク! 問題へのリンク 問題概要 以上 以下の整数値からなる 個の有限集合 が与えられる。 以下の操作を最小回数繰り返すことによって、「 と をともに…
undo 付き Union-Find! 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数…
めっちゃ面白い問題! 問題へのリンク editorials 問題概要 個の直方体がある。 番目の直方体は の形をしている。 今、これらの直方体からいくつかを選んで積み木を作る。このとき、奥行き方法は必ず長さが になるようにする。 縦または横方向については、 …
最小費用の最大流を流すネットワークフロー問題! 問題へのリンク editorial 問題概要 個の駅があり、 と番号づけられている。 駅 と駅 の間には 種類の電車が走っていて、 番目の電車は 駅 を時刻 に出発して、 駅 に時刻 に到着し、 料金は である。 今、 …
これがこのセットで一番難しかった。 こういうのをグラフで考えるのは典型と言えば典型か。 問題へのリンク 問題概要 組の整数組 がある。それぞれの組から整数を選んだ 種類の整数に含まれる整数の種類数の最大値を求めよ。 制約 考えたこと 数値をノードに…