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

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

トップ > 牛ゲー

牛ゲー

AtCoder ARC 105 C - Camels and Bridge (青色, 500 点)

AtCoder AtCoder500点 ARC-C 最短路問題 牛ゲー 双対性 最長路問題 順列 順列の最適化 next_permutaion DP 差分制約系 グラフ問題 前処理 指数探索系問題 ある量を固定して考える 青色diff 区間 制約条件:区間 必要条件を列挙したら十分条件になる 条件の言い換え 累積max 一直線上のN点の問題 スムーズにGreedyできない時に幅を持たせるDP 個人的要復習

難しかった 問題へのリンク 問題概要 体重が であるような 体のラクダがいる。ラクダを一列に並べる方法のうち、次の条件を満たすものについて、左端のラクダと右端のラクダの距離として考えられる最小値を求めよ。また、そのようにラクダを並べることが不可…

AOJ 2427 ほそながいところ (JAG 夏合宿 2012 day2-D) (800 点)

グラフ問題 探索問題 全探索 Union-Find 重みつきUnion-Find データ構造 コーナーケース IP定式化 AOJ 差分制約系 AOJ-ICPC AOJ-ICPC800点 JAG JAG夏合宿 牛ゲー

「全探索でもここまで難しいやつもある」という例としてよく挙げられる問題。 ここのページに僕なりの 全探索 重み付き Union-Find 木を使いながら判定 をした解法を記した。