AtCoder2000~点
AtCoder
AtCoder2000~点
AGC-F
順列を題材とした問題
操作:隣接swap
操作:swap
操作
順列テク:逆順列を考える
条件の言い換え
変数変換して扱いやすい同型な問題を見出す
分割統治法
辞書順
最適化テク:探索候補を絞る
グラフ
グラフの辺数を削減する
トポロジカルソート
priority_queue
Greedy
天才のGreedy
可視化テク:二次元平面上に可視化する
主客転倒
ソートすることが目的の操作の問題
操作後の結果の最適化問題
思わず解きたくなる興味深い良問
難しいGreedy
これも自力で解けたの、嬉しい!!!!! 問題へのリンク 問題概要 正の整数 が与えられる。 からなる順列 に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ かつ を満たす に対して、 と を swap する 制約 まずは逆…
パリティ
DP
二分探索
ゲーム
条件の言い換え
DP値を利用して状態復元
AtCoder
AGC-F
AtCoder2000~点
区間
区間分割型ナップサックDP
DP高速化
最大値の最小化
数列
操作
操作木を考える
銀色diff
DP高速化:直前との比較のみでよい
ふと考えてみた。区間 DP っぽく にはなるな...なんて思っていたけどそこから落とせなかった...いやこれ何を食べたらこんな二分探索思いつけるようになるの!?!?!?!??? なにかこういう場面で二分探索すると上手く行くよ、というパターン的なものが…