2020-09-17から1日間の記事一覧
AOJ
HUPC
クエリ処理問題
DP
前処理
条件の言い換え
クエリ先読み
bitDP
高速ゼータ変換
累積和
累積max
個人的要復習
中堅以上の典型要素を詰め合わせた教育的問題
上位互換という概念
操作列が文字列で与えられる
累積和テク:条件を満たすものの個数を累積和で表す
比較的簡単枠だとは思っていたけど、B よりも解かれたのはびっくり! 問題へのリンク 問題概要 北海道高校には 個の科目があり、それぞれ 1, 2, 3 の 3 段階で成績がつけられる。 各生徒の成績は長さ の文字列で表される 生徒 が生徒 の「上位互換」であると…
AOJ
HUPC
数え上げ問題
操作によって作れるものの集合を考える(判定関数を考える)
操作
操作後の結果の数え上げ
区間
区間ソート
Greedy
DP
テク:移動可能区間を遷移していく
ナップサックDP
座標圧縮
最適化テク:探索候補を絞る
最適化テク:端点のみを考える
DP状態空間を絞る
比較的素直な考察で解ける問題 問題へのリンク 問題概要 umgくんは 1 次元上の座標 0 にいます。今は時刻 0 です。時刻が 1 進むごとに、今いる座標より 1 大きい座標に移動するか、 1 小さい座標に移動するか、その座標にとどまるかという行動ができます。 …