2019-04-17から1日間の記事一覧
AtCoder
旧ABC
順列を題材とした問題
操作
最小回数・最小個数を求める
操作:circular_shift
操作:挿入
DP
LIS
ソートすることが目的の操作の問題
最小コスト
青色diff
DP状態:吸い出しと吸い込み
要素の並び替えを管理するDP
そのまま覚えたい典型問題
最適化問題
順列において、要素をどこかに挿入する系の操作をする問題は典型ではある。こういうのをしっかり押さえたい。 問題へのリンク 問題概要 の順列が与えられる。 以下の操作を繰り返してソートされた状態にしたい。最小回数を求めよ。 要素を 1 つ選んで、任意…
こういうのを得意になるぞー!!! でも AtCoder でこういうデータ構造をしっかり準備する必要がある系は珍しい気がする。 問題へのリンク 問題概要 個のマス () があって、マス上に 個の区間がある。 各 に対して、 と移動したときに何個の区間を踏むかを答…
Codeforces
調和級数
数学(整数問題)
バケット
ある量を固定して考える
ある量を決めるとGreedy
最適化テク:緩和しても良い
最大公約数
Greedy
復元
構築
数列
制約:数値が10^6以下
最大公約数の値を固定して考える
CodeforcesDIV3
CodeforcesR2400
最大値の最大化
最適化テク:「最大値の最大化」に基づく緩和
天才か!!! 問題へのリンク 問題概要 個の整数 が与えられる。 < となる であって、LCM() が最小となるものを求めよ。 制約 考えたこと という制約がいかにも怪しい。この制約が意味するのは 配列 a をバケットで表せる。すなわち a = (2, 3, 5) みたいな…
Codeforces
データ構造
各kに対して
クエリ処理問題
順列を題材とした問題
順列テク:逆順列を考える
setの上手な使い方
CodeforcesDIV3
CodeforcesR1800
「次の要素」へのポインタを求める
操作後の結果を求める問題
超苦手タイプ 問題へのリンク 問題概要 要素からなる順列があたえられる。先手と後手が交互に 残っている中から最大要素を選び、その左右 要素を合わせて 要素を、自分のところに抜き取ってくる (左右に 要素残っていない場合はある分だけ抜き取ってくる) と…