グラフの辺数削減テク:サイクル内の辺長の大小関係に基づく枝刈り
AOJ
JAG
グラフ
三角不等式
グラフの辺数を削減する
Union-Find
最適化テク:解に確実に含まれる要素を列挙する
DAG
DP
最長路問題
制約条件:距離K以下の2頂点
AOJ-ICPC500点
JAG夏合宿
AOJ-ICPC
個人的要復習
グラフの辺数削減テク:サイクル内の辺長の大小関係に基づく枝刈り
中堅以上の典型要素を詰め合わせた教育的問題
素直に考えるとグラフの辺数が のオーダーになってしまうので、いかに削減するかを考える問題だった 問題へのリンク editorials 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。各頂点 には値 が振られている。今、各頂点にスコア を割り振りたい。…
最小全域木
最適化テク:探索候補を絞る
グラフ
木
AtCoder
AtCoder500点
ABC-D
Kruskal法
グラフの辺数を削減する
ARC-D
青色diff
グラフの辺数削減テク:うまく並べて隣接する部分のみに辺を張る
グラフの辺数削減テク:サイクル内の辺長の大小関係に基づく枝刈り
マンハッタン距離
思わず解きたくなる興味深い良問
典型要素を詰め合わせた教育的問題
ゆかたゆさんと一緒に解いた。 今後まだ解いてない様々な 500 点問題について何がポイントになっているのかをブログ書きながら明らかにして行きたい。500 点問題の苦手意識を克服する！ 問題へのリンク 問題概要 二次元平面上に 個の点が与えられる。これら…
最小全域木
マトロイド
最適化テク:探索候補を絞る
分割統治法
木の重心分解
再帰的構造に着目する
Kruskal法
グラフ
AtCoder600点
AtCoder
最大値や最小値に着目する
グラフの辺数を削減する
橙色diff
ARC-like
ARC-E
高度典型
個人的要復習
グラフの辺数削減テク:サイクル内の辺長の大小関係に基づく枝刈り
めちゃいっぱい解法あってすごい！！！！！！！MST への理解が問われる。 いずれ復習をやり切ってちゃんとしたいが取り急ぎ、分割統治法 Kruskal と、想定解法のみ。 問題へのリンク 問題概要 頂点からなるパスグラフと整数 が与えられる。各頂点には重み が…
