Yukicoder No.519 アイドルユニット
n (2の倍数, 24以下) 人のアイドルでn/2組のペアを作る。それぞれのペアの相性がn*n行列で与えられるとき、ペアの相性の和の最大値を求めよ。
nが小さいのでペア成立済みのアイドルを状態にしたbitDPでメモリとしては十分。問題は計算量である。制限時間が1秒と短いので、漸化式の遷移をよく考える必要がある。m組のペアができている状況で、n - 2m人の中からペアを作る組み合わせは(n-2m)C2とおりであるが、これをすべて試していたら定数倍が大きくTLEする可能性が高い。
そこでよく考えると、現在の状態が例えば 00011110101 (1は既にペア成立済みのアイドル)の時、一人目は2番目のbitであると決め打ちしてしまってもよい。(bitDPの遷移順としては、bitが小さい方から配っていく感じのdpになる) つまり00011110111 からもう一人選ぶ見合わせだけ選べば良い。これで(n-2m-1)通りだけ調べれば良くなる。
また、状態として立っているbitの数が偶数個のときだけ遷移が発生する。これは次のように考える。まずdp[0]は0とし、それ以外は負の数を入れておく。そしてこっからbitを2個立てた時の配るdpを行うと、遷移先のは0以上の整数になっており、遷移先は必ず偶数個のbitが立っている。その為、dp[state]が負の時はスキップしてしまえばよい。
(ここで素直にbitcountすると定数倍でTLEする可能性が高い) 計算量は O(2^n) であるが、nが24まであるので、約1600万回のループになりC++以外の言語では定数倍をガチガチに最適化する必要がある。
