AOJ-ICPC700点
AOJ
AOJ-ICPC
JAG冬合宿
AOJ-ICPC700点
連続最適化
最大スコア
計算幾何
数学(幾何)
連続量問題
全探索
next_permutaion
解空間:O(N!)通りの選択肢
解空間:O(2^N)通りの選択肢
凸包
最適化テク:緩和しても良い
KKT条件・Lagrangeの未定乗数法
面積
二分探索
方程式
二分探索:方程式の解を1つ求める
そのまま覚えたいシンプル設定の中堅以上の典型問題
最適化問題
浮動小数点型を扱う問題
面白い最適化問題! 問題へのリンク 問題概要 二次元平面上で、原点からの距離が であるような 点の凸包の面積として考えられる最大値を求めよ。 制約 考えたこと 凸包というところが面倒だが、要は 本のうちの何本かを選んで それを適切な順序に並び替えた…
AOJ
AtCoder
JAG
AOJ-ICPC
AOJ-ICPC700点
JAG夏合宿
二分探索
二分探索:lower_bound
文字列
セグメント木
SparseTable
SuffixArray
文字列検索問題
クエリ処理問題
制約:複数系列の長さの合計が10^5以下
連続部分列を扱う問題
区間
区間の長さの最大値または最小値を求める
解空間:O(N^2)個の区間
解空間:O(N^2)通りの選択肢
そのまま覚えたいシンプル設定の中堅以上の典型問題
Suffix Array の練習問題 問題へのリンク editorials へのリンク 問題概要 英小文字からなる文字列 と、 個のクエリが与えられる。 各クエリでは 2 つの文字列 が与えられる。 文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の…
AOJ
JAG
AOJ-ICPC700点
ConvexCut
多角形
面積
ボロノイ図
期待値
積分
分けて解いてまとめる
計算幾何
AOJ-ICPC
JAG春冬コン
図形的量の期待値
競技数学色強め
三角形
浮動小数点型を扱う問題
ボロノイ図の応用問題! 問題へのリンク editorials 問題概要 頂点数 の凸多角形があって、その内部に 個の点が与えられる。凸多角形の内部に一様ランダムに点を打つとき、以下の値の期待値を求めよ。 「その点 から 個の点までの距離の最小値」を二乗した値…
グラフ
Euler路
連立一次方程式
乱択
補グラフを考える
パリティ
AOJ
ICPCアジア
補集合を考える
AOJ-ICPC700点
AOJ-ICPC
全域木を考える
思わず解きたくなる興味深い良問
面白い!!!!!!! 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる (連結とは限らない)。 このグラフに何本かの辺を付け加えることで「連結なオイラーグラフ」にすることができるかどうかを判定し、できるならば一例を示せ。ただし多重辺…