お寿司をできるだけたくさん食べるアルゴリズム

みなさんお寿司は好きですか？僕は好きです。というわけで、できるだけたくさんの種類のお寿司を食べるためのアルゴリズムについて書きます。

さて、早速たくさん食べる方法について考えていきます。まずお寿司には色々なネタがありますが、例えば脂っぽいものばかりを食べてしまうと気分が悪くなってしまうし、似たような味のものを食べていると飽きてしまいますよね。

ここで、スシローのメニューからいくつか例を挙げて、以下のような状況を考えてみます。

・机にはマグロ、中トロ、大トロ、サーモンちーず、オニオンサーモン、えびチーズの6種類のお寿司がある
・大トロは脂っぽすぎるので、マグロ、中トロ、サーモンちーずのいずれとも一緒には食べれない
・オニオンサーモンとサーモンちーずは、同じサーモン系なので一緒には食べれない
・サーモンちーずとえびチーズは、同じチーズ系なので一緒には食べれない

この状況でできるだけ多くの種類のお寿司を食べるにはどうすればよいでしょうか。

このままだと文章ばかりでよくわからないので、これらを頂点としてグラフを考えてみることにします。

それぞれのネタの頭文字をとって頂点にして書いてみると次のようになります。

f:id:KokiYamaguchi:20180113135833p:plain

さて、ここでまず、一緒に食べれないネタ同士に辺を張ってみると次のようになります。

f:id:KokiYamaguchi:20180113135852p:plain

このグラフ上でどのようなことを考えれば良いかというと、食べるお寿司をいくつか選び、そのいずれのお寿司の間にも辺が張られていない選び方の中で、その選んだ個数が最大になるようにすればよいです。その最大値が結局食べられるお寿司の最大個数になりますね。この問題を $MIS$（$Majide\ Issyoni\ Shinaide$ : マジで一緒にしないで）問題と呼ぶ人もいます*1。

この例では、マ、中、え、オ、すなわち、マグロ、中トロ、えびチーズ、オニオンサーモンの4種類を食べることができることがわかります。5種類以上食べることはできないので、これが最大個数になります。

この問題は、こちらの記事指数時間アルゴリズム入門を見ると解くことができます。

アルゴリズムとしては、基本的には各お寿司について、食べるか食べないかの2通りで全探索をします。しかしそれだと計算量が $O(お寿司の数 * 2^{お寿司の数})$ になってしまってお寿司の数が多めのときには対処できないので、以下の工夫を加えます。

・残っているお寿司の中で、葉か孤立点になっているお寿司は先に食べてしまう（次数1以下のお寿司は食べてしまう）
・あるお寿司を食べた後、そのお寿司と辺でつながっているお寿司はすべて友達に譲る

どちらも割と明らかにわかると思います。

この枝刈りによって、辺が多い場合は後者の条件によって、お寿司が多い場合は前者の条件によってかなり高速化されます。$お寿司の数 \leq 40 $くらいまでならいけるらしいです。

MISの実装

int MaximumIndependentSet(const int n, const vector<long long> &g) {
        int res = 0;
        function<void (long long, int)> dfs = [&](long long remain, int cnt) {
                for (bool update = true; update; ) {
                        update = false;
                        for (int i = 0; i < n; i ++) if (remain & (1LL << i)) {
                                int deg = __builtin_popcountll(remain & g[i]);
                                if (deg <= 1) {
                                        cnt ++;
                                        remain &= ~((1LL << i) | g[i]);
                                        update = true;
                                }
                        }
                }
                res = max(res, cnt);
                if (remain) {
                        int k = __builtin_ctzll(remain);
                        dfs(remain & ~(1LL << k), cnt);
                        dfs(remain & ~(g[k] | (1LL << k)), cnt + 1);
                }
        };
        dfs((1LL << n) - 1, 0);
        return res;
}

上記のコードは、climpetさんのコードを参考にさせて頂きました。ありがとうございます。

さて、次に上と同じ問題を考えるのですが、少し別の角度から問題を捉えてみます。今度は、一緒に食べることができるネタ同士に辺を張ったグラフを考えてみると、次のようになります。

f:id:KokiYamaguchi:20180113145653p:plain

このグラフ上で考えるべきことは、選ぶお寿司のいずれの間にも辺が張られているような選び方の中で、その選んだお寿司の最大個数です。この問題を$ MC $（$Mawoakezuni\ Cueru$：間を空けずに食える）問題と呼ぶ人もいます*2。

当たり前のことですが、上の $MIS$ と、この $MC$ のサイズは一致します。どちらもできるだけたくさんのお寿司を食べようとした結果なので当然ですね。

ところで上の $MIS$ のときに作ったグラフと、$MC$ のときに作ったグラフをよく見ると、互いに補グラフ（辺があるお寿司間の辺を無くし、辺がないお寿司間には辺を張ったグラフ）の関係になっています。よって、次が言えます。

あるグラフにおける $MIS$ のサイズは、その補グラフにおける $MC$ のサイズに等しい

このことから $MC$ を求めるアルゴリズムは以下のようにすればよいです。

MCの実装

int MaximumClique(const int n, const vector<long long> &g) {
        vector<long long> gg(n);
        for (int i = 0; i < n; i ++) gg[i] = ~g[i];
        return MaximumIndependentSet(n, gg);
}

さて、以上でお寿司をたくさん食べることができました。このお寿司のアルゴリズムを使うと以下の問題が解けます。

G - Mixture Drug

薬品がお寿司に見えれば $MIS$ を書いて終わりです。

int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        vector<long long> g(n);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a] |= 1LL << b;
                g[b] |= 1LL << a;
        }
        printf("%d\n", MaximumIndependentSet(n, g));
        return 0;
}

D - 派閥

国会議員がお寿司に見えれば $MC$ を書いて終わりです。

int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        vector<long long> g(n);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a] |= 1LL << b;
                g[b] |= 1LL << a;
        }
        printf("%d\n", MaximumClique(n, g));
        return 0;
}