F - Heights and Pairs 考えたこと 「どのペアも高さが同じでない」の余事象は「どれかのペアで高さが同じ」 それは「1つのペアで…」「2つのペアで…」の組み合わせ 包除原理 まず高さの頻度表を作るんだろうな ペアの取り方は対象であるので状態を圧縮できる 2人、3人、4人、とペアがあった時に「ペアが1個ある組み合わせ」はいくつなのか？ これは式変形ではなくDPで求めるのかもな？ ペアの取り方に順序は関係ないので、こちらで順序を導入して良い 与えられた頻度表Xの先頭i個でjペア作る場合の数でDPかな 4人以上いると、一度に2ペアできる可能性がある 4C2×2C2÷2! Nが10万近くなるのか… 公式解説なし 解説 https://betrue12.hateblo.jp/entry/2020/09/27/043205 https://tiramistercp.hatenablog.com/entry/abl-f 「包除原理だ」OK 「頻度表を作る」OK 「サイズ4以上の集合からkペア取る場合の数」OK 「DPかな？」いいえ、畳み込みです 繰り返し畳み込みをする時は順序を工夫する必要がある 短い方からくっつける
