今日解いた競プロの問題。
ABC232-F: とりあえずAのどの要素をBのどの要素に割り当てるかが決まれば差の絶対値の総和採るだけだなということが分かる。しかし順列18!通りを全探索をするのは現実的ではない。こういうときは順列全探索をbitDPにできないか考える。2^18や2^18*18なら余裕で間に合う。
Sを自然数[1,N]の部分集合とし、$DP[S]:=(A_i\ (i\in S)をB_j\ (j\in [1, |S|])に対応させた場合の最小コスト)$と定義する。適宜遷移すれば$O(2^N N)$で解ける。入れ替えによるコストの計算方法に注意。
例えば$N=6, S=\{1, 3, 6\}$で、新たに$A_5$を採用して$S=\{1,3,5,6\}$に遷移するという場合。すでに3つ採用しているので$A_5$に対応させるのは$B_4$。ここでA,Bのまだ採用されずに残っている要素を見てみると、Aが$\{A_2,A_4,A_5\}$、Bが$\{B_4,B_5,B_6\}$である。$A_5$,$B_4$はそれぞれ左から3番目の要素と1番目の要素なので、3-1=2回の入れ替えが必要になる。このように採用されずに残っている要素の中での位置を計算する必要がある。これを計算するには、これから採用する要素の左に既に採用された要素がいくつあるかを数えればよい。
OpenXRをいじっている。いまだにちゃんと動くサンプルコードとちゃんと動かない自分のコードの違いが分からない。サンプルコードのVulkan部分を全部Vulkan-Hppに置換したのだが、いまだに正常に動く。深度バッファも実装したし、フレームバッファやイメージビューの生成タイミングも揃えてみたがやはり挙動が違う。何？
今日も散歩した。あまり時間がとれなかったが、一応歩いたことのなかった道を開拓した。
体力を回復させていきたい所存。
Categories: 未分類