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

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

値A[i]を頂点に持たせたグラフを考える

AtCoder ABC 327 D - Good Tuple Problem (茶色, 400 点)

まず、これをグラフの問題として捉えるところに、一つ山がある印象だけど、みんなあっさり超えていてすごい! 問題へのリンク 問題概要 以下の正整数からなる長さ の数列 、 が与えられる。これらの数列の組が次の条件を満たすかどうかを判定せよ。 0 と 1 …

AtCoder ABC 302 F - Merge Set (水色, 500 点)

下手を打つと密なグラフになって TLE してしまう!! スーパーノードを作ることでグラフを sparse にするテク! 問題へのリンク 問題概要 以上 以下の整数値からなる 個の有限集合 が与えられる。 以下の操作を最小回数繰り返すことによって、「 と をともに…

AtCoder ABC 302 Ex - Ball Collector (橙色, 625 点)

undo 付き Union-Find! 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数…

AOJ 2293 Dangerous Tower (JAG 夏合宿 2011 day2-D) (600 点)

めっちゃ面白い問題! 問題へのリンク editorials 問題概要 個の直方体がある。 番目の直方体は の形をしている。 今、これらの直方体からいくつかを選んで積み木を作る。このとき、奥行き方法は必ず長さが になるようにする。 縦または横方向については、 …

AOJ 1088 School Excursion

最小費用の最大流を流すネットワークフロー問題! 問題へのリンク editorial 問題概要 個の駅があり、 と番号づけられている。 駅 と駅 の間には 種類の電車が走っていて、 番目の電車は 駅 を時刻 に出発して、 駅 に時刻 に到着し、 料金は である。 今、 …

Chokudai SpeedRun 002 K - 種類数 β (600 点)

これがこのセットで一番難しかった。 こういうのをグラフで考えるのは典型と言えば典型か。 問題へのリンク 問題概要 組の整数組 がある。それぞれの組から整数を選んだ 種類の整数に含まれる整数の種類数の最大値を求めよ。 制約 考えたこと 数値をノードに…