競プロ典型90問 045
Simple Grouping（★6）
問題概要
XY平面上に点がいくつか与えられる。これらをいくつかのグループに分類する。グループの数は指定される。
各グループの中で最も遠い2点の距離を出す。「すべてのグループの中で最高の値」を出来るだけ低くする。
DPの作り方
dp[i][j]
i:いくつのグループに分けるか
j:対象の点対象の点(j)をi個のグループに分けたときの最低コストを記録する。jの表し方は「点がビットに対応する表し方」を用いる。点が4個なら4ビット利用する。
ある dp[i][j] の値を決めるときはjを
- ひとつのグループ
- i — 1個のグループ
に分ける。
例えば、1,2,4,6,8,13,15で4つのグループにするときは
- 1,4,13でひとつのグループ
- 2,6,8,15で3つのグループ
とする。
グループ数が小さいほうからdpを作成していくので、4つグループのデータを書くときには3つグループのデータが出来ている。
ビット操作テクニック
このプログラムでは1,2,4,6,8,13,15から1,2や6,8,13を取り出すことをする。
つまり1から15から選択された1,2,4,6,8,13,15から、その中の組み合わせを取得したい。
テクニックは次のようにする。
k = (k - 1) & jjがもともとの1,2,4,6,8,13,15を表しているもの
kが6,8,13にあたるもの
この式の意味は、
- kから1を引くことでkの最低ビットが消えて、それより下のビットが全部立つ
- これとjのビット積を取ることで求めたいもののひとつ下のものが求まる
想定解法のDP
C++で書かれた想定解法はすこし難しいので書く。
結論
dp[0][*]はdp[0][0]=0、ほかは1<<62dp[1][*]はdp[1][0]=1<<62、ほかは実際の値dp[2以上][*]はdp[2以上][0]=1<<62、ほかは分割が可能なら実際の値、不可能(例 : 3点を4つに分解)なら1<<62
では細かく見ていく。
準備
cost[i] はiをひとつのグループにしたときのコスト
ただし、 cost[0]=0
dp[i][j] はjをi個のグループにしたときのコスト。デフォルト値 1<<62
ただし、 dp[0][0]=0
よって初期(dpのfor文を走らせる前)の状態で dp は
dp[0][0]=0
dp[0][0以外]=1<<62
dp[0以外][すべて]=1<<62
i = 1、jの立っているビット数1
dp[1][j] は
dp[0][0]=0とcost[j]=0のmax(k==j)
のminより0
i = 1、jの立っているビット数複数
dp[1][j] は
dp[0][0]=0とcost[j]=Xのmax(k==j)- その他の
dp[0][j-k]=1<<62とcost[k]=Yのmax(k!=j, k!=0)
のminよりX
i = 1の段まとめ
dp[1][0]=1<<62 (初期値から更新作業なし)
dp[1][0以外]=実際の値
i = 2、jの立っているビット数1
dp[2][j] は
dp[1][0]=1<<62とcost[j]=Xのmax(k==j)
より
dp[2][j]=1<<62
ビット数1なので2分割出来ないが、そういうところは 1<<62 になるようである。
i = 2、jの立っているビット数複数
dp[2][j] は
dp[1][0]=1<<62とcost[j]=Xのmax(k==j)dp[1][j-k]=Yとcost[k]=Zのmax(k!=j, k!=0)(複数ある)
のmin。
dp[2][j] は出てきた複数のYとZの最小値。
i = 2の段まとめ
dp[2][0]=1<<62 (初期値から更新作業なし)
ほかは
不可能なところ 1<<62
可能なところは実際の値
i = 3、jの立っているビット数1
dp[3][j] は
dp[2][0]=1<<62とcost[j]=Xのmax(k==j)
より
dp[3][j]=1<<62
ビット数1なので3分割出来ない。そういうところは 1<<62
i = 3、jの立っているビット数2
dp[3][j] は
dp[2][0]=1<<62とcost[j]=Xのmax(k==j)dp[2][j-k]=1<<62とcost[k]=Yのmax(k!=j, k!=0)
のmin。dp[2][j-k] は j-k が立っているビット数が1なので 1<<62 となる。
よって
dp[3][j]=1<<62
ビット数2なので3分割出来ない。そういうところは 1<<62
i = 3、jの立っているビット数3以上
dp[3][j] は
dp[2][0]=1<<62とcost[j]=Xのmax(k==j)
と、 k!=j, k!=0 で
dp[2][j-k]=Yとcost[k]=Zのmax([2][j-k]が可能)(複数あり)dp[2][j-k]=1<<62とcost[k]=Zのmax([2][j-k]が不可能)(複数あり)
よって
dp[3][j] は複数出てきたYとZの中の最小値
i = 3の段まとめ
dp[3][0]=1<<62 (初期値から更新作業なし)
ほかは
不可能なところ 1<<62
可能なところは実際の値
