🪷

競プロ典型90問 045 Simple Grouping（★6）

2024/10/23に公開

 問題概要XY平面上に点がいくつか与えられる。これらをいくつかのグループに分類する。グループの数は指定される。

各グループの中で最も遠い2点の距離を出す。「すべてのグループの中で最高の値」を出来るだけ低くする。

 DPの作り方dp[i][j] = 対象の点(j)をi個のグループに分けたときの最低コスト
i:いくつのグループに分けるか
j:対象の点
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のビット積を取ることで求めたいもののひとつ下のものが求まる

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

 結論
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の立っているビット数1dp[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の立っているビット数1dp[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の立っているビット数1dp[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の立っているビット数2dp[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

可能なところは実際の値