AtCoder ARC 100 E - Or Plus Max (黄色, 700 点)

高速ゼータ変換各kに対して条件の言い換え O(3^N) bitDP DP高速化テク:K以上からK+1以上を引く ARC-E AtCoder AtCoder700点制約条件:総和<=K 数列黄色diff 解空間:O(N^2)個のペア解空間:O(N^2)通りの選択肢最大スコア最適化問題

高速ゼータ変換の練習第二弾！問題へのリンク問題概要長さの整数列があります。を満たすすべての整数について、以下の問題を解け: を < , を満たす整数とするとき、の最大値を求めよ。制約考えたこと個の要素を一斉に変換する何かをさせている感…

2018-06-24

AtCoder ARC 099 E - Independence (黄色, 700 点)

グラフ二部グラフ DFS BFS DP ナップサックDP ARC-E AtCoder AtCoder700点補グラフを考える補集合を考える黄色diff 均等に分けるそのまま覚えたいシンプル設定の中堅以上の典型問題中堅以上の典型要素を詰め合わせた教育的問題

いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たい。類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷似) POJ 3692 Kindergarten (補グラフとって二部グ…

2018-06-14

AtCoder ARC 067 E - Grouping (黄色, 600 点)

DP 数え上げ問題二項係数調和級数 ARC-E AtCoder AtCoder600点グルーピングの数え上げ問題黄色diff グルーピング(算数) 制約条件:総和=K 均等に分ける箱とボール

slack 勉強会で 600 点の DP として話題になってやってみたん。 DP 自体は素朴だけど、計算量解析含めると 700 点でもいい気はする。 Grouping 問題へのリンク問題概要 (ARC 067 E) 人をグループ分けしたい。人は互いに区別される。どのグループの人数も …

2018-06-07

AtCoder ARC 097 E - Sorted and Sorted (黄色, 600 点)

DP 前処理累積和操作:swap 最小回数・最小個数を求める操作 AtCoder AtCoder600点 ARC-E 操作:隣接swap ソートすることが目的の操作の問題最小コスト黄色diff DP状態:吸い出しと吸い込み要素の並び替えを管理するDP そのまま覚えたいシンプル設定の中堅以上の典型問題最適化問題

600 にしちゃムズイ。 ARC 097 E Sorted and Sorted 問題概要 (白, 1), (白, 2), ..., (白, N), (黒, 1), (黒, 2), ..., (黒, N) の 2N 個の要素の順列が与えられる。「隣同士を swap する」を最小回数行うことで、「白」についても「黒」についてもソートさ…