2020-09-19から1日間の記事一覧
AOJ
ACPC
DP
in-place DP
数え上げ問題
操作列を数え上げる問題
操作
数列
座標圧縮
ナップサックDP
制約:複数系列の長さの合計が10^5以下
データ構造
BIT
DP高速化
DP高速化:セグメント木
in-place な DP にもっと慣れていきたい 問題へのリンク 問題概要 個の数列がある。 個目の数列は 個の要素からなる。 個目の数列の 番目の要素は と表す。 個目の数列から 1 個以下の要素を選び、選んだ要素を元の数列の順番通りに並べた数列を とする。 数…
AOJ
HUPC
FFT
期待値
期待値の線形性
確率
部分和
DP
DP高速化:FFT
Greedy:各要素について独立に考えてよい
マージテク
ナップサックDP
前処理
累積和
制約:数値が10^6以下
一直線上のN点の問題
Greedy
priority_queue
データ構造
ハフマン符号
二分木のような計算順序
点が移動していく問題
分割統治法
鍵やアイテムを題材とした問題
確かに、えでゅふぉのラス問にありそう! 問題へのリンク 問題概要 人の選手が距離 のレースを走る。 人目はデフォルトでは距離 1 走るのに 秒かかる。 スタートから距離が のところにアイテムがある。各アイテムは各選手に対して独立に、確率 で減速 (距離 …