ABC008-C コイン next_permutationについて

はじめに

しばらく使ってないと使い方を忘れてしまいそうなnext_permutationですがABCのC埋めで埋まっていない問題ででてきました。

世間の解説記事にはnext_permutasionは順列に同じ数字が入っている場合でも正しく動作してくれるなどと記載されているものがあり，確かに全部の組み合わせを出力してくれるという意味では正しいのですが，本問のように重複も数えなければならない問題ではエラーになることがわかりました。

問題

C - コイン

考察

99点解法はnext_permutationで順列を全部試してやればいいと考えて実装しましたがWA。

next_permutationは同じ要素が入っていても大丈夫と思ってましたがうまくいきません。

WAしたコード（デバッグ用出力入れてます）

#include <bits/stdc++.h>
using namespace std;

int main(){
  //入力1
  int N;
  cin >> N;
  vector<int>c(N,0);
  
  //コインの並び配列　1表　-1裏
  int coins[N];
  for(int i=0;i<N;i++){
    coins[i]=1;
  }
  
  //入力2
  for(int i=0;i<N;i++){
    cin>>c[i];
  }
  //num=N!  
  int num=1;
  for(int i=1;i<=N;i++){
    num*=i;
  }
  double cnum=0;//表を向いているコインの枚数
  //next_permutation処理
  do{
    cout<<c[0]<<" "<<c[1]<<" "<<c[2]<<" "<<c[3]<<endl;
    //コインを全部表に
    for(int i=0;i<N;i++){
      coins[i]=1;
    } 
    
    for(int i=0;i<N;i++){
      for(int j=i+1;j<N;j++){
        if(c[j]%c[i]==0){
          coins[j]*=-1;
        }
      }
    }
    for(int i=0;i<N;i++){
      if(coins[i]==1){
        cnum++;
      }
    }  
  }
  while(next_permutation(c.begin(),c.end()));
  
  //cout<<cnum<<" "<<num<<endl;
  cout<<setprecision(18)<<(double)cnum/num<<endl;

  return 0;
}

テスト入力

4
5 5 5 5

出力

5 5 5 5
0.0833333333333333287

正しくは5555を24回出力するはずですが1回しか出力してくれません。

ACしたコード

組み合わせの回数分（N!）ループで回してやるとACしました。

#include <bits/stdc++.h>
using namespace std;

int main(){
  //入力1
  int N;
  cin >> N;
  int c[N];
  
  //コインの並び配列　1表　-1裏
  int coins[N];
  for(int i=0;i<N;i++){
    coins[i]=1;
  }
  
  //入力2
  for(int i=0;i<N;i++){
    cin>>c[i];
  }
  //num=N!  
  int num=1;
  for(int i=1;i<=N;i++){
    num*=i;
  }
  int cnum=0;//表を向いているコインの枚数
  //next_permutation処理
  for(int k=0;k<num;k++){
     //コインを全部表に
    for(int i=0;i<N;i++){
      coins[i]=1;
    } 
    
    for(int i=0;i<N;i++){
      for(int j=i+1;j<N;j++){
        if(c[j]%c[i]==0){
          coins[j]*=-1;
        }
      }
    }
    for(int i=0;i<N;i++){
      if(coins[i]==1){
        cnum++;
      }
    }  
    next_permutation(c,c+N);
  }
  //cout<<cnum<<" "<<num<<endl;
  cout<<setprecision(18)<<(double)cnum/num<<endl;

  return 0;
}

考察

next_permutationをdo whileで回すときには，順列の最後の組み合わせがでてきたところで止まってしまうため，同じ要素が入っていると全部回りきらず，本問のような問題ではWAになることがわかりました。重複を含めて全部回す場合は，for文で組み合わせ数のN!回分しっかり回してやるとよかったです。

更に考察

N<=8の制約のないケースの満点解法について解説みて理解しました。
天才かと思いましたが期待値の線形性については学んだことがあります。

自身以外の自身の約数の数が偶数の場合に２分の１、奇数の場合にS+2/2S+2となるのは手を動かして計算してみて理解できました。

実装も簡単でした。

  for(int i=0;i<N;i++){
    temp=0;
    //自身以外の要素に自身の約数がいくつあるか
    for(int j=0;j<N;j++){
      if(i==j)continue;
      if(c[i]%c[j]==0){
        temp++;
      }
    }
    if(temp%2==1){
      ans+=0.5;
    }
    else{
      ans+=(double)(temp+2)/(2*temp+2);
    }
  }