Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Code Thanks Festival 2018 G - Sum of Cards】円周上のDP

解説を読んでDPだと言われても全くわからず、DP力が足りないから分からないのだと思って教育DPの全解きをし、戻ってきたら理解出来たという話。

G - Sum of Cards

問題

N枚のカードの表にAi、裏にBiが書いてある。Ai,Biともに1..Nの順列。

見えてるカードの和を最大化したいが、数字がK種類あるようにしたい。

和の最大値を求めよ。

方針

考え方だけ示します。

f:id:akiradeveloper529:20191008135233j:plain

まず、裏表関係を繋いでいくと各ノードの次数が2なので(xから出ていくやつもいれば必ず入ってくるやつもいるから)、円がいくつか出来ることになります。

もし、各円で、k種類を作る時の最大値が求まれば、あとはナップザック問題の要領で、大域解が求まります。

従って、1つの円についてk種類作る時の最大値はいくつか?が求めます。

裏表のどちらかを選ぶというのは、辺に方向をつけるという操作と同じであり、次数が0でないノードは種類としてカウントされるということになります。

円の中で各辺に方向をつけていきます。ナイーブだと2Nかかりますが、状態を

  1. どこまで見たか (N)
  2. 今までに何種類あったか (N)
  3. 今見てる辺の前の辺の向き(2)
  4. 1つ目の辺の向き (2)

とするとO(N2)でDP出来ます。(しらんけど)

考察

表と裏のどちらかをとるという問題で、表と裏に辺を作って、向きが選ぶということとして、グラフ問題に帰着させる考え方はこの問題でも使われています。よくある手筋なのでしょう。

K - 種類数 β