AtCoder625点
AtCoder
AtCoder625点
ABC-G
橙色diff
最小カット
フロー
【問題集】フローのステップアップ
マトロイドと劣モジュラ関数
グラフ
スイッチ
最小カット:K値変数をK-1個の0-1変数で表す
最小カット:PSP(燃やす埋める)
最小コスト
最小カット:すべてがTrueまたはFalseのときの利得を表す
最適化問題
2 変数劣モジュラ関数の和の最小化を最小カットにするやつ！ 問題へのリンク 問題概要 種類のスキルがある。それぞれ初期状態のスキルレベルは 1 であるが、最大で 5 まで上げられる。スキル のスキルレベルを 1 上げるのに必要なコストは 円である。 種類の…
AtCoder
ABC-Ex
計算幾何
円
線分の交差判定や距離計算
三分探索
高度典型
連続最適化
連続量問題
最小コスト
凸関数
山登り法
二次元平面上のN点の問題
AtCoder625点
赤色diff
最適化問題
浮動小数点型を扱う問題
本当に三分探索で通るのね！ これらの問題を思い出した drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 本の線分がある。この平面上の円盤 (円周と内部を含む) のうち、 本の線分すべてと共有点をもつようなも…
AtCoder
ABC-G
橙色diff
floor_sum
操作
操作:定数を足したり引いたりする
操作:区間に等差数列を足す
操作:区間
数列
数え上げ問題
操作後の結果の数え上げ
操作を好きな回数だけ行える
標準形を考える
AtCoder625点
floor sum！！！ コンテスト中に思いつけてよかった！ 問題へのリンク 問題概要 皿 があって、皿 には 個の石が乗っている。また、空の袋がある。 あなたは以下の 2 種類の操作を好きな順番で 0 回以上何度でも行うことができる。 石が 1 個以上載っている皿…
AtCoder
ABC-Ex
橙色diff
Union-Find
木
差分更新
undoつきUnion-Find
データ構造
クエリ処理問題
クエリ:削除
二値パラメータ問題
種類数
高度典型
木の問題に対してパスの場合から考える
DFS
値A[i]を頂点に持たせたグラフを考える
各kに対して
解空間:O(2^N)通りの選択肢
最大スコア
AtCoder625点
最適化問題
undo 付き Union-Find！ 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数…
