2019-04-26から1日間の記事一覧
AtCoder
AGC-D
最適化テク:固定する変数を入れ替えて考える
盤面を予め変更する
文字列
回文
DP
LCS
操作
AtCoder900点
操作後の結果の最適化問題
最大スコア
黄色diff
LCS型DP
操作をちょうどK回行う
最適化問題
面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …
AtCoder
AGC-D
AtCoder1000点
順列を題材とした問題
操作
条件の言い換え
操作:区間
操作:挿入
DP
フロー
グラフ
二部グラフ
最大安定集合・最小点被覆・最小辺被覆
LIS
可視化テク:二次元平面上に可視化する
ソートすることが目的の操作の問題
最小コスト
橙色diff
DP状態:吸い出しと吸い込み
要素の並び替えを管理するDP
操作:circular_shift
最適化問題
本番フローで無理矢理解いた!!! でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…
面白かった 問題へのリンク 問題概要 (やや意訳) 長さ の数列 を復元したい。この数列に対し、ある並び替え順列 があって 隣り合う 2 要素の min をとってできる長さ の数列を で並び替えると となり 隣り合う 2 要素の max をとってできる長さ の数列を で…