CODE THANKS FESTIVAL 2018-G:Sum of cards

詰め切るのが大変。本番で通した人たちすごい。

問題

解法

カード $i$ について， $A_i,B_i$ どちらか一方のスコアを獲得できるという状況だ。こういう状況は，グラフにしてみたくなる。 $1$ から $N$ の数字が頂点，辺を $A_i,B_i$ の間に結んだグラフを考えよう。このグラフは，どの頂点も次数が $2$ であり，円形のグラフの集まりになる。 $A_i,B_i$ のどちらを表にするかということを辺の向きで表現しよう。 $A_i,B_i$ のうち，辺が入る方を表にする，ということにする。するとこの問題は以下のように書ける。

$N$ 頂点の，円形のグラフが集まったグラフがある。各頂点には $1$ から $N$ の数字が書いてある。このグラフの各辺に向きをつけ，各辺について，その辺が入る頂点に書いてある数字だけスコアを得る。少なくとも1本は辺が入ってくる頂点が $K$ 個以上あるという条件のもとで，スコアの最大値を求めよ。

この問題を解いていこう。

円形のグラフが1つのとき

まずは円形のグラフが1つのときを考えよう。これをどう解くかで既に難しく思えるが，なんとここでdpをする(初見厳しくないか...)。どのような状態を持つべきかを考えよう。まず，便宜的に頂点番号を $0,1,n-1$ とする。 $n$ は円形を構成する頂点の数とする。今どの頂点をみているかということは当然必要だろう。また，辺が入ってくる頂点の数に制約があるので，これも状態としてもっておきたい。さらに，この「辺が入ってくる頂点の数」をカウントするために重要な情報がある。それは，頂点 $i-1$ 頂点 $i$ の間の辺の向きである。この頂点の向き次第で，頂点 $i-1$ から頂点 $i$ に移るときに，辺が入ってくる頂点の数が変わってくる。では

$dp[i][j][k]$ :頂点 $i$ までで辺が入る頂点の数が $j$ 個， $k$ は頂点 $i-1$ と頂点 $i$ 間の辺の向きを表す。 $k=0$ のときに頂点 $i$ から頂点 $i-1$ に辺が入る。 $k=1$ のときはその逆とする。

で十分だろうか？とりあえずこの場合の状態遷移について考えてみよう。便宜上， $i=1$ から始め， $i=n-1$ まで見た後， $i=0$ をみることにする。

$k=0$ のとき

$i-1$ で $k=0$ のときは以下の図のようになる。 $i-1$ には辺が入っていなかったが， $i$ から出る辺で入ってくるようになるので， $j$ の添え字が1増える。
f:id:sigma1113:20190130234314p:plain
また， $i-1$ で $k=1$ のときは以下の図のようになる。 $i-1$ にもともと辺が入っていたので， $j$ の添え字は増えない。
f:id:sigma1113:20190130234332p:plain

$k=1$ のとき

同様に考えればよい。
$i-1$ で $k=0$
f:id:sigma1113:20190130234637p:plain
$i-1$ で $k=1$
f:id:sigma1113:20190130234702p:plain

というわけで遷移が書けた。めでたしめでたし...と言いたいのだが，ここには罠がある。そう，いま考えているグラフは円形であったから，頂点 $0$ と頂点 $1$ の間から順に見ていって，最後に頂点 $n-1$ と頂点 $0$ の間を見ることになるが，このときに，上で述べた遷移にはならないパターンがある。以下の2つの図を見比べてみよう。
頂点 $0$ から頂点 $1$ に辺が出ているとき
f:id:sigma1113:20190131000413p:plain
頂点 $1$ から頂点 $0$ に辺が出ているとき
f:id:sigma1113:20190131000423p:plain
$i-1$ から $i$ に辺を伸ばすときは基本的に辺が入る頂点の数は増えるはずであったが，一周して戻ってくるときだけは，そうならないのである。よって，この3次元DPを素直にやるだけではうまくいかないのだ。ではどうするか？答えはシンプルで，「 $0$ から $1$ に辺が出ているか」それとも「 $1$ から $0$ に辺が出ているか」ということを状態としてもてばよい。そうすれば $n-1$ から $0$ の遷移の際にのみ気をつけることで，この問題を回避できる。つまり

$dp[i][j][k][l]$ :頂点 $i$ までで辺が入る頂点の数が $j$ 個， $k$ は頂点 $i-1$ と頂点 $i$ 間の辺の向きを表す。 $k=0$ のときに頂点 $i$ から頂点 $i-1$ に辺が入る。 $k=1$ のときはその逆とする。 $l$ は頂点 $0$ と頂点 $1$ の間の辺の向きを表す。 $l=0$ のときに頂点 $1$ から頂点 $0$ に辺が入る。 $l=1$ のときはその逆とする。

これで円形1つのときの問題を解くことができた。頂点が1つのみのときに注意。

円形のグラフが複数あるとき

さて，この問題でグラフを作ったときに， $N$ 個の頂点すべてが連結になるとは限らない。よって，上のようにして各円について問題を解くことはできるが，その結果をまとめてやる必要がある。しかしこれは難しくない。円が全部で $M$ 個あるとしよう。各円について，辺が入る頂点が $k$ 個あるときのスコアの最大値がわかっている。このとき， $floor(\frac{M+1}{2})\leq k \leq M$ であることに注意しよう。それならば

$dp2[i][j][k]$ : $i$ 個目の円の $j$ 番目のありえる辺が入る頂点の個数まで考えたときに，合計で辺の入る頂点の個数が $k$ のときのスコアの最大値

「 $j$ 番目のありえる辺が入る頂点の個数」というのは， $t=floor(\frac{M+1}{2})$ とすると， $t,t+1,\cdots,M$ に新たに $1,2,\cdots m$ という番号を振りなおしたと考えればよい。遷移はナップサック問題のような形になる。このうち， $k$ が $K$ より大きいものの最大値が答えとなる。

この解法全体の計算量は $O(NK)$ である。

実装

Submission #4129625 - CODE THANKS FESTIVAL 2018
これが参考になるかわからないが，上で述べたことを書くとこんな感じになる。各円の結果をまとめる部分で，前の円の大きさを保存しておかないといけなかったりなど，実装上面倒なことは多い。もう少し楽な実装方針があるかもしれない。

大変だが，勉強になる問題であった。ちなみにうまくやると最大費用流になるらしい。