ABC199 E 解答

E - Permutation（1814）

問題文

( 1, 2, 3, … , N )を並び替えてできる数列 a であって、以下の条件を満たすものの数を出力してください。
1 ≤ i ≤M を満たす全ての整数 i について、a1, a2, a3, … ,aXi の中に Yi 以下の数は Zi 個以下しか存在しない

制約

2 ≤ N ≤ 18
0 ≤ M ≤100
1 ≤ Xi <N
1 ≤ Yi <N
0 ≤ Zi <N
入力に含まれる値は全て整数である

考察

本問題はbitDPという手法を用いて解きます。了解！という方も、なんだそれ？という方もいるかと思います。できるだけ前提知識なく理解できるように順を追って説明します。bitDPに則って説明するというよりは問題を解説し終えた後に「これがbitDP(の一例)ですよ」となるイメージですかね。

本問題はM個の条件を満たす長さ N の順列の個数を求める問題です。全通りを試すとなるとその総数は N! です。制約がN≦18と小さいとはいえ、これは間に合いそうにありません。

ですのでちょっとばかり工夫をしましょう。

N 要素の順列をいきなり考えるのは、とっても難しいですね。まずは誰でもわかるものから少しずつ考えていきたいです。

ということで、まずは長さ 1 の順列を作ってあげましょう。この場合、その種類は1〜Nまでの数字のうちどれか一つを入れれば良いので、18通りしかありません（一旦制約は無視します）。これなら全部調べることができそうです。

またこの時にどの数字を入れたかをメモしておきましょう。入れた数字を1、6などとそのままメモする方法もありますが、今後のことも考えて

00000

こんな感じの0を並べたものを使ってみます(実際はN個並んでいます)。もし1を入れた場合には、右から1番めの0を1にしてあげます。

00001

別に左からでもいいんですが、右だとこのあとでちょっと楽できます。
同様に3を入れた場合は

00100

ですね。
こうすると何が嬉しいかと言いますと、もうちょっと解説が進んだ際に、1と4が入ってるという状態が

01001

という風にスッキリ表すことが可能となることです。

このように、使った数字の状態を0と1のビット列で表せるので、bitDPのうちのbitという名前がついています。入れた数字は実際に10進数として表すことも可能です。

2進数：00000 → 10進数：0
2進数：00001 → 10進数：1
2進数：00100 → 10進数：4
2進数：01001 → 10進数：9

一個の数字を入れた時の状態の数を書き出しまして、次に進みたいと思います。本当は N まであります。

00001 : 1 通り
00010 : 1 通り
00100 : 1 通り
01000 : 1 通り
10000 : 1 通り
...

これで、１個の場合はおしまいです。続きまして、もう１個増やしましょう。２個の場合の数は１個の場合の数を使うと簡単に求めることができます。

例）10010 (2と5)

この場合は、次の２通りからのみたどり着くことが可能です。

１）１個目に2、２個目に5を入れる。

00010 → 10010

２）１個目に5、２個目に２を入れる。

10010 → 10010

ですので、10010となるのは、

１）１個目が２のときの１通り
２）１個目が５のときの１通り

の合わせて、２通りが考えられるわけです。実際に並べて見ますと

２５と 5 2

の２通りあることがわかります。同様のことを３個以上の場合も行うことが可能です。これを N まで行えば最終的な状態は

11111

となっているはずです。このときの数が N  個の並べ方となります。

このように

前の情報からの遷移をうまく使って先の状態を求めて行く手法

を動的計画法（DP）といいます。厳密にはマルコフ過程だなど色々とありますが、こんな認識で大きくは外していないでしょう。

以上のようにbitを使って状態を管理する動的計画法ですので、bitDPと呼ばれるわけです。この手法を用いることでこの問題を解けます。が上記の説明では大切なことを無視しています。本問題は

1 ≤ i ≤M を満たす全ての整数 i について、a1, a2, a3, … ,aXi の中に Yi 以下の数は Zi 個以下しか存在しない

数を求める必要があります。条件がなければbitDPを使わなくとも、N !が答えになりますもんね。

さて、この条件をどんな感じで使うかです。

上記の説明では全ての状態が次の状態に遷移可能でした。ここの「遷移する」というところを「条件を満たしていたら遷移する」に変更してあげましょう。条件はどうやら最大で100個あるらしいです。ただ全ての遷移に対して100個見てあげる必要はありません。

まず注目すべきは Xi です。これは（順列の）左からXi 個の数字に関する条件です。そのため、Xi 未満しか並べてない場合にはそもそも判定ができず、 Xi 以上並べてる場合には数を追加してもその数は判定結果には寄与しません。ですので、並べる数の個数がちょうど Xi 個になった場合にだけ判定を行いましょう。

次は Yi ですね。Yi 以下の数が何個使われているかを確かめたいです。ここで、各状態は 01001 こんな感じの0と1で表されています。例として Yi = 3としましょう。とすると、右端から、右から数えて 3 番目の数字までの 1 の数がYi以下の個数に対応します。

01001
↑
ここより右

最後の条件ですね。 Yi 以下の数が何個使われているかを求めました。この数が Zi 以下なら無事条件達成で、次の状態に遷移することが可能となります。満たさなかった場合は残念ながら、遷移することができません。

Xi の時点で遷移ができるかどうか決まる、さながら進級テストみたいな感じですかね。数の世界も世知辛そうです。

以上の条件をbitDPの遷移に含めてあげれば無事ACとなります。

実装に移る前に、ビットシフト系のお話を簡単に。

00101とかを作るときにはビットシフトが便利です。

1<<2

こんな感じで書けば、1を2個分ずらすので

2進数：100 = 10進数：4

が簡単に作れます。これは右側にずらすこともできちゃいます。

2進数：10100 = 10進数：20
20 >> 2
2進数：101 = 10進数：5

ですね。はみ出した数字は無くなっちゃいますのでご注意を。こんな感じで、Yi 以下の数の場合には Yi までずらして、１の数を数える（ &1 とすると１かどうかわかる）と判定が可能です。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
   int n,m;
   cin >> n >> m;
   vector<int> X(m),Y(m),Z(m);
   rep(i,m) cin >> X[i] >> Y[i] >> Z[i];
   vector<ll> dp((1<<n)+5);
   //開始は00000だからそれを１通りとしておく
   dp[0] = 1;
   //n 個の数字を入れる
   rep(i,n)    
   {
       //...00000~...11111まで試す。
       rep(bit,1<<n)
       {
           //経っているbit数が桁と一致しなければ飛ばす
           int bit_num = 0;
           rep(k,n) if((bit>>k)&1)++bit_num;
           if(bit_num != i) continue;

           //追加する数
           rep(add,n)
           {
               //数を追加してもよいかの判定
               bool ok=true;
               if((bit>>add)&1) continue;
               //遷移先のbit（ | or演算子を用いる）
               int next_bit = bit | (1<<add);
               //next_bitへの遷移が可能かどうかMの条件を見ていく
               rep(mi,m)
               {
                   //追加したあとの数字の個数がXiじゃなければ判定しない
                   if(i+1 != X[mi]) continue;
                   //Yi以下でたってるビット数
                   int bit_num_y = 0;
                   rep(k,Y[mi]) if((next_bit>>k)&1)++bit_num_y;
                   //もしZi個より多いbitがたっていたら遷移できない
                   if(bit_num_y>Z[mi]) ok = false;
               }
               //遷移可能だったら遷移する。
               if(ok) dp[next_bit] += dp[bit];
           }
       }
   }
   //dp[...111111]に答えが入ってる
   cout << dp[(1<<n)-1] << endl;

   return 0;
}

あとがき

本問題では遷移が循環しないため、１次元のdpで解いていますが

dp[ i ][ s ]:
i 個目の数字まで見て
その時の使用した数字の集合（001010こんなやつ）が s
のときの場合の数

と２次元配列を用意してあげても全く同じように解けます。というか、i を用意するだけで、あとは全く同じになります。立っている１の数が数字の列の長さを管理してくれている、というとすんなり理解できる方がいるかもしれません。

bitDPやbit全探索など、bit系を使う際のポイントは何と言っても　N の小ささですね。今回は 18 でした。D 問題のように N=20でも3通り必要となる場合は少し違いますが、N が小さいときにはbitで表すことを一瞬考えてあげると、解法が浮かんでくるかもしれませんね。

最後にbitの類題が典型90問にありましたので紹介しておきます。
とっても難しいので、小課題１から解いてみると良いと思います。

023 - Avoid War（★7）