atcoder.jp なんか同じ考え方の人が全然いないので書きます とすれば, 遷移は高々「被覆を開始する」「被覆を終了する」だけになるので, disjointに気をつけてDPして終わりです int main() { int N; cin >> N; int A[N]; rep(i, N) cin >> A[i]; mint DP[200…

まえがき このように、直感に頼った未証明のGreedyは危険です。 概要 状態に対してコストが定まるような状況を考える. コストが最小になるための状態の必要十分条件を とする. このとき, 以下のいずれかを仮定できるなら, 条件 を の必要条件に代るものとし…

1:09 4完 ちょっと参加が10分くらい遅くなってしまった。 Aを見る。ただでさえ問題文がわかりにくい上、変数が衝突していて読み解くのに時間がかかったが、適当に交互にすると問題の性質を満たすと分かったので提出。 (0:16 WA) ソートを忘れていたのでなお…

2:01全完←間に合ってない Aを眺めると数学 なので提出する (0:01 AC) Bの制約を眺めると優先度付きキューでシミュレーションしたら通りそうなので提出する (0:07 AC) Cを見て、なんか面倒そうなので先にDを見る Dを見ると、ただのエラトステネス+累積和なの…