algoNote

プログラミング関連

No.437 cwwゲーム

本番では解けずに解説を見て解きました。

初めてbitDPを使う問題に当たりました。

問題

No.437 cwwゲーム - yukicoder

考え方

使う桁の集合をビットで表すとNが最大で12桁なので12ビットで表すことができる。
(例えば、 12345 という数があって1桁目、3桁目、4桁目を使うときの集合は 01101 と表せる。)

DPテーブル

dp[使う桁の集合]:=その桁を使ったときのcww数の和の最大値

具体的な処理は以下 (S:使う桁の集合、a[i]:Nを文字列化したときのi番目の数、とする。)

  1. すべてのSについてcww数に使う桁i,j,kをすべて試す
  2. Sにi,j,kが含まれないときはSを決め直す
  3. cww数にならならないときはi,j,kを決め直す
  4. dp[S]=max(dp[S], dp[Sからi,j,kを除いた集合]+(a[i]*100+a[j]*10+a[k]); で更新

※Sを0から始めることで、Sからi,j,kを除いた集合は既に評価されているはずなのでうまく行きます。

更新の例

入力 : N=5133144

......

    (5133144)
  S={1100100}, i=0, j=1, k=4 のとき (a[i] a[j] a[k] = 511)

     (5133144)           (5133144)      (5133144)
  dp[{1100100}] = max(dp[{1100100}], dp[{0000000}] + (511))

......

    (5133144)
  S={1101111}, i=3, j=5, k=6 のとき (a[i] a[j] a[k] = 344)

     (5133144)           (5133144)      (5133144)
  dp[{1101111}] = max(dp[{1101111}], dp[{1100100}] + (344))

......

答えは 855 (dp[{1111011}])

コード(c++)

int dp[10000];
inline bool check(int bits,int index) {
    return (bits&(1<<index));
}
int main() {
    string str;
    cin>>str;
    vector<int> a;
    for(char x:str) a.push_back(x-'0');
    int N=str.size();

    int ans=0;
    for(int S=0; S<=(1<<N); S++) {
        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {
                for(int k=j+1; k<N; k++) {
                    if(!check(S,i) || !check(S,j) || !check(S,k)) continue;
                    if(a[i]==0 || a[j]!=a[k] || a[i]==a[j]) continue;
                    int t=S^(1<<i)^(1<<j)^(1<<k);
                    dp[S]=max(dp[S],dp[t]+a[i]*100+a[j]*10+a[k]);
                }
            }
        }
        ans=max(ans,dp[S]);
    }
    cout<<ans<<endl;
    return 0;
}