2023-06-06から1日間の記事一覧
AtCoder
緑色diff
ABC-E
典型要素を詰め合わせた教育的問題
グラフ
クエリ処理問題
クエリ(グラフ上)
連結成分
グラフのconnectivity
グラフ上にチェックポイントのある問題
差分更新
Yes/No判定問題
Union-Find
前処理
条件の言い換え
連結成分ごとに分解して考える
N個のものうち1個を変更・削除したものを解く
AtCoder475点
Union-Find 慣れしていれば解きやすい！ 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフ が与えられる。 組の頂点対 について、どの頂点対間のもパスがないグラフを良いグラフと呼ぶことにする。 与えられるグラフ は良いグラフである。 このグラ…
AtCoder
AtCoder400点
そのまま覚えたい典型問題
緑色diff
ABC-D
座標圧縮
区間
二分探索:lower_bound
二分探索
【問題集】二分探索の入門
Greedy:各要素について独立に考えてよい
二次元平面上のN点の問題
【問題集】set・map
sparseな問題
最大値と最小値を求める
x軸とy軸について独立に考えてよい
「点がどの区間に属するか」は極めて典型的な問題で、それを二次元にしたバージョン！ 問題へのリンク 問題概要 二次元平面上で、左下の頂点が 、右上の頂点が であるような長方形状のケーキがあります。 このケーキ上には 個のいちごが乗っていて、 番目の…
AtCoder
AtCoder300点
ABC-C
灰色diff
そのまま覚えたい典型問題
二次元平面上のN点の問題
【問題集】グラフの入門
連結成分
連結成分ごとに分解して考える
密グラフ
DFS
BFS
計算幾何
Union-Find
各kに対して
伝播していく様子をテーマにした問題
単純な DFS / BFS 系はいよいよ灰色 diff になったのですね。 問題へのリンク 問題概要 二次元平面上に 人がいます。 番目の人は座標 にいます。 今、 番目の人がウィルスに感染しました。ウイルスに感染した人から距離が 以内にいる人にウイルスは次々とう…
AtCoder
AtCoder600点
黄色diff
ABC-F
計算幾何
しゃくとり法
多角形
差分更新
解空間:O(N^2)通りの選択肢
中堅以上の典型要素を詰め合わせた教育的問題
テク:循環するものを二週させる
面積
誤差
くしらっちょ君と一緒に解いた！ 実装が辛い。 問題へのリンク 問題概要 頂点数が である凸多角形が与えられる。この凸多角形の面積を とする。 今、凸多角形の隣接しない 2 頂点を結ぶ直線によって凸多角形を 2 つの多角形に分ける。そして、2 つの多角形う…
