競プロ典型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) & j

jがもともとの1,2,4,6,8,13,15を表しているもの

kが6,8,13にあたるもの

この式の意味は、

• kから1を引くことでkの最低ビットが消えて、それより下のビットが全部立つ
• これとjのビット積を取ることで求めたいもののひとつ下のものが求まる

想定解法のDP

C++で書かれた想定解法はすこし難しいので書く。

結論

• dp[0][*] は dp[0][0]=0 、ほかは 1<<62
• dp[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

可能なところは実際の値