ABC310-Dのフレンズさん解説で被らないってマジ？と思ったお仲間へ

どーも、Nafmoです。

ところで皆様はこの解説を見たときにこんなことを思いませんでしたか？

「これで被らず数え上げられるってマジ？」

アライグマ「D問題はDFSの練習問題なのだ！　1番目の選手から順に、何番目のチームにいれるかDFSで決めて、最後にチーム数をチェックすればいいのだ」 pic.twitter.com/JJKZqUXp3u
— 競技プログラミングをするフレンズ (@kyopro_friends) 2023年7月15日

そう、僕も思ってました。が、よくよく考えると、全然被らないのでそのお話を…………

と思ってました。が、僕が理解したなんとなくしかかけなかったのでチラシの裏です。参考程度にどうぞ………。厳密にはかけません。

小さい順に入れてるから、以上。

それじゃ元も子もないですよね。

(1,2,3),(1,3,2),(2,1,3)を同じと見ます！みたいなやつ

これなら全部ソートすれば(1,2,3)で1種類ですよね。

これと同じことをします。

今回はN個ある要素を部分集合 A,B,Cの3つに分けたとしましょう。共通部分はなく、AとBとCを合わせたものは分ける前と同じとします。

さっきの話で、A,B,Cそれぞれ、その構成要素をソートしておきます（(2,1,3)を(1,2,3)にのように）

次に、A,B,Cの先頭の要素を見てソートします（それぞれ違うはずなのでA,B,Cを並び替えることができます）

これをすると、小さい数字から順番に属する集合を決めるとき、すでにある集合に加えるか、新たな集合を作るかの2択になると思います。そして、これはソートされた状態を保ったまま要素を追加できます。

ソートされた状態のものだけを数えておけば、重複は避けられそうですね〜という感じで何となく理解しました。

お気持ちしかかけませんでした…殴らないで………

もっと良い説明があったら教えてね

ありがとうございました。