AGC044F Name-Preserving Clubs を解いたのですが、かなり不思議な問題・解法だったので、解いたときの思考過程をメモしておきます（証明ではありません） atcoder.jp
問題概要
整数 $1, \ldots , N $ に対して、集合の多重集合 $S$ を構成したとき、以下を満たすものを良い構成とする - 任意の順列 $p$ について、$S$ 内の全ての要素を $i \rightarrow p(i)$ と変換した $S'$ が与えられた時に、 $p$ が特定できる
例えば、 $S = \{ \{1,2\}, \{2\} \}$ という構成に対して, $p = (2,1)$ とすると $S' = \{\{1,2\}, \{1\}\} $ となるが、$S'$ が与えられると $p$ が特定できる
これを満たすような $S$ の中で追加した集合の数が最小となる $S$ のパターンは何通りあるか。ただし、順列による変換を行って一致するような $S$ は同一視し、パターンが 1000 を超える場合は -1 を出力せよ。
実験
$N$ が大きい場合、パターン数は 1000 を超えそうなので、$N>=100$ なら $-1$ を返して、そうでないなら assert で落としてみる
そっか・・・
追加する集合の数の最小値 $K$ の計算
恐らく$2$ 冪が絡むだろうことは分かり、$\log_2(N)$ くらいは必要そうであることは分かる。順列がどうのこうのが良く分からないのでとりあえず実験・・・。
- 実験結果： 追加する集合の数を $K=1,2,\ldots$ としたときに構成可能な $N$ の最大値 $F(K)$ は、$2, 3, 6, 13, 29, \ldots$ となる
やはり $F(K) = 2^{K} - c(K)$ の形が最大値になりそう。
良くある話だが、$K$ 個の「区別がついている」集合がある場合、各集合に含まれているか否かで、$2^{K}$ 個の要素を分類可能である。 $i$ 番目の集合に含まれている場合 $i$ bit 目を立てることで、$0, \ldots, 2^{K}-1$ に対応する。
そこで逆に考えると、$0, \ldots, 2^{K}-1$ から何個かの数字を取り除いた場合に、$K$ bit が区別できれば、順列で変換されたとしても $2^{K} - $ (取り除いた個数)を区別することが出来る。
そのため、$c(K)$は $K$ 個のものを区別するために必要な最小の集合の個数と言い換えることができ、これは元の問題のより小さい問題になっている。よって、$c(K) =$（$F(x) \ge K$ となる最小の $x$） になる。
パターン数 $P(N)$の計算
まず、十分大きいところでは、$N = F(K)$ と表現されるような $N$ だけ考えればよいと雰囲気で分かる（$N = F(K)$ を達成する構成から集合を消していくことを考えると、候補は $N$ に比例して大きくなりそうで簡単に $1000$ を超えるように見える）。
$N = F(K)$ と表現される $N$ については、最小値の計算と同様の議論をすると、 $P(N) = P(K)$ となると考えられる ($N$ 個を $K$ 個の集合で区別する表現は、$K$ bit を $c(K)$ 個の整数で区別する表現に言い換えられるという議論はパターン数でも同じはず)。
以上より、$F(K)$ は大体 $2$ の指数乗になっているため、 $1 \le N \le 61$ までを前計算してテーブルで埋め込んで、$N \ge 62$ 以上は $N = F(K)$ を満たす場合のみ、 $P(N) = P(K)$ そうでない場合は、$1000$ を超えると判定すればよい。
コーナーケース
・・・で終わればよいのだが、これまでの議論には大きな落とし穴がある。
実は $N = 4, 7$ の場合、同じ集合を $2$ つ追加するような特殊な集合の構成が存在する（$N=4$ のサンプルがあって優しいね）。 $N$ が小さいため、情報量的に損していそうな同じ集合の追加でも区別が出来てしまう。
これまでしてきた、$N = F(K)$ での言い換えの議論では、「異なる集合」によって区別することを勝手に仮定してしまっていた。 そのため、同じ集合を $2$ つ追加するような特殊な構成に対しては、「$K$ bit を $c(K)$ 個の整数で区別する」 側の表現に言い換えることができない。 例えば、$N =124 = F(7)$ の場合がコーナーケースで、 $P(7) = 336$ であるが、$2$ 個同じ集合を $2$ つ追加する構成が存在するため、$P(124) = 334$ となる。この場合分けに気を付けると AC できた。
