2019-10-20から1日間の記事一覧
AtCoder
AtCoder500点
Greedy
最適化テク:固定する変数を入れ替えて考える
Dijkstra法
DP値:ペア値
DP
Floyd-Warshall法
最短路問題
体力や燃料がある一定以上必要になる設定の問題
グラフ
密グラフ
Greedy:今が良いほど未来も良い
前処理
クエリ処理問題
青色diff
【問題集】最短路問題
最小回数・最小個数を求める
最適化問題
この Floyd--Warshall は天才すぎる! 問題へのリンク 問題概要 頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。 各頂点では燃料を補給できて、補給すると満タン (容量 の…
AtCoder
AtCoder400点
ABC-D
二分探索
二分探索:lower_bound
三角形の成立条件
三角形
半分全列挙
累積和
しゃくとり法
FFT
ある量を固定して考える
全探索
茶色diff
【問題集】累積和・二分探索法・しゃくとり法
【問題集】二分探索の入門
そのまま覚えたい典型問題
バケット
集計処理
制約:数値が10^6以下
累積和テク:条件を満たすものの個数を累積和で表す
累積和テク:区間の総和を累積和で高速に求める
教育的ないい問題!!!!! 問題へのリンク 問題概要 本の棒があって、それぞれ の長さをもっている。 このうちの 3 本を選ぶ方法であって、その 3 本で三角形が作れるものは何通あるか? 制約 解法の overview ものすごく色んな解法が考えられる問題だと思…
AtCoder
AtCoder600点
ABC-F
調和級数
二分探索
前処理
必要条件を列挙したら十分条件になる
主客転倒
累積和
バケット
各kに対して
クエリ処理問題
最大回数・最大個数を求める
操作
黄色diff
累積和の亜種
累積和テク:累積和や累積結果を前処理しておく
最適化問題
数列
かなり辛いことを頑張ったけど、本当はすごく明快な問題だった!! 問題へのリンク 問題概要 個の整数 がある。各 に対して、以下の答えを求めよ。 残っている整数から、どの 2 つも互いに異なる 個の整数を選んで抜き取ることを繰り返したい 抜き取れる回数…