CODE THANKS FESTIVAL 2018 G - Sum of Cards (500)

• 問題

解法

最初maxの方を選択していって差分が小さい順に種類を増やしていくgreedyが思いつく
-> なんかgreedyはやばそうなのでDPかな?
(やばそうと言いつつも反例は思いつかなかった,教えて欲しい)
-> key: i 番目まで見た, j 種類出た として1枚ずつ表裏を決めていくDPが思いつく
-> が, あるカードを決める時, それが既出の数字かもしれない
-> {a}, {b} に数字 x は合計で高々2回しか出ないので依存関係は2個まで. この順番にDPしたい
-> 依存関係( a_i - b_i )に辺を貼る(典型)
-> 全て次数2なので自己辺を含むサイクルの集合になる(要出典)
-> 各辺について向きをつけていくと #(出現する数字) = #(入次数>0である頂点) となる.

よってサイクル上でDPしていきたい.
適当に視点を x_0 として x_0 -- x_1 -- .. -- x{n-1} -- x_n = x_0 の順番でDPすることを考える.
x_i -- x{i+1} の向きを決める時, 出現した数字の種類は次の

• x_{i-1} -- x_i の向きはどちらか
• x_{i+1} は終点か(i+1=nか)どうか,またi+1=nの時は x_0 -- x_1はどちらの向きか

公式の解説のDPの意味はこういう意味.
ただ x_0--x_1 の向きを決めた後,各々のDPは独立に更新できるので,
DPのキーは前に決めた辺の向きはどちらだったかを持っておけば良い.
tdp[ i ][ j ][ k ] :=
( 合計のmax s.t. (i+1) 番目の辺( x_i -- x{i+1} )の向きを決めて, j 種類の数字が出て, kはx{i+1}の入次数 )
と置いて,各連結成分ごとにDPしていく.

tdpの結果から各連結成分で ary[ j ] := (j種類出現するときの合計のmax) を求め,
dp[ i ][ j ] := ( i 番目の連結成分をみて全体で j 種類出現するときの合計max) として
dp[ i+1 ][ j ] = max_{ 0 <= k <= j } ( dp[ i ][ j - k ] + ary[ k ] ) を更新していく.

計算量は それまでみた頂点の合計 a, 新しく見るサイクルの頂点数 b とすると,
f(a+b) = f(a) + O(b²) + O((a+b)b) で,
f(x) = x² とすると f(a+b) - f(a) = 2ab + b² = O(ab) + O(b²) から f(N) = N² が確かめられる.
(厳密な証明はわからない)

メモ

いくつか知ったこと

• 順列でグラフを貼るとサイクルの集合になる
• vector<vector<vector>> hoge; みたいなのめっちゃ遅い(これだけでTLE&MLEした)
• サイクル上のDPは最初の点,それまで見た点の状態をもつ

コード