最近夢で見た問題

夢に出てくる競プロの問題、自明か既出か #P-complete がち

— えびちゃん (@rsk0315_h4x) 2021年11月23日

今回はわりと面白いやつ出たか？と思って考えてたんだけど、寝起きで頭がついてなかっただけで自明枠だったことが判明しつつある

— えびちゃん (@rsk0315_h4x) 2021年11月25日

あまり難しくなかったのですが、ABC-C から D くらいはある気がしたので、寒色の人の腕試しくらいになればいいかな〜くらいの気持ちで放流してみます。 暖色の人も、発展的なことを考えてくれるとうれしいかもです。

夢の内容（概要）

競プロ er がたくさんいる会社があります。各社員をレーティング順に並べたリストが公開されています。 さらに、各社員を出身校ごとに分けたときの順位も公開されています。出身校自体は非公開です。 次のような感じです。

名前	順位	出身校順位
A	1	1
B	2	1
C	3	2

このとき、同じ出身校である社員たちのグループ（同じグループ間の社員は出身校が同じ、そうでない社員はそうでない）は何通り作れるのか気になりました。 この例では、[[A, C], [B]] と [[A], [B, C]] の 2 通りです。

問題

もう解けている人もいるかもなんですが、より形式的に書きます。

問題文

まず、集合 \(T\) の分割を、集合の集合 \(\mathcal{S} = \{S_1, S_2, \dots, S_m\}\) であって、次の条件を満たすものと定めます。

• \(S_1 \cup S_2 \cup \dots \cup S_m = T\)
• 各 \(i\) (\(1\le i\le m\)) に対して \(S_i \ne \emptyset\)
• 各 \(i, j\) (\(1\le i\lt j\le m\)) に対して \(S_i \cap S_j = \emptyset\)

例（クリックで展開）

\(T=\{1, 2, 3, 4\}\) のときの分割の例：

• \(\{\{1, 3\}, \{2\}, \{4\}\}\)
• \(\{\{1, 2, 3, 4\}\}\)
• \(\{\{1\}, \{2\}, \{3\}, \{4\}\}\)

\(T=\{1, 2, 3, 4\}\) のときの分割でない例：

• \(\{\}\)
• \(\{\{\}\}\)
• \(\{\{1, 3\}, \{1, 4\}, \{2\}\}\)
• \(\{\{1, 3\}, \{2\}\}\)
• \(\{\{1, 2, 3, 4, 5\}\}\)

（クリックして展開部分おわり）

数列 \(A = (a_1, a_2, \dots, a_n)\) が与えられます。集合 \(\{1, 2, \dots, n\}\) の分割 \(\mathcal{S}\) であって、以下の条件を満たすものの個数を \(998244353\) で割ったあまりを求めてください。

• 各 \(S\in\mathcal{S}\) に対して、以下がすべて成り立つ
  • ある \(i\in S\) に対して \(a_i = 1\)
  • すべての \(i\in S\) (\(a_i \ne |S|\)) について、ある \(j\in S\) が存在して \(a_j = a_i + 1\)
  • すべての \(i, j\in S\) に対して \(i\lt j \implies a_i \lt a_j\)

制約

• \(1\le n\le 10^6\)
• \(1\le a_i\le n\) (\(1\le i\le n\))

例

input 1

3
1 1 2

output 1

2

上記の例です。

input 2

4
1 2 2 3

output 2

0

input 3

12
1 1 1 2 1 2 2 3 2 3 3 3

output 3

324

解答

クリックして展開

とりあえず、愚直に \(A\) を先頭から見ていって valid な分割を全通り作ることを考えます。 \(\mathcal{S} = \{\}\) で初期化しておきます。

\(a_i = 1\) であれば、\(S\in\mathcal{S}\) に追加することはできないので、\(\mathcal{S} \gets \mathcal{S}\cup\{\{i\}\}\) で更新します。

\(a_i \gt 1\) であれば、\(S\in\mathcal{S}\) のうち \(|S|+1 = a_i\) であるものを選んで、\(\mathcal{S} \gets (\mathcal{S}\setminus S)\cup(S\cup\{i\})\) で更新します。ただし、そうした \(S\) が存在しなければ valid な分割は作れません。

クリックしてさらに展開

上記の手順を見ると、\(a_i\) を見たときに行える操作の通り数は、その時点での \(\mathcal{S}\) にサイズ \(a_i-1\) の集合がいくつあるかに依っていることがわかります。 また、そこでどの \(S\) を選んで更新したとしても、各サイズの個数の変わり方は同じであることもわかります。

クリックしてさらに展開

なので、各サイズの個数を管理しながら答えを更新していけばよいです。\(O(n)\) 時間です。

use proconio::{input, marker::Usize1};

const MOD: u64 = 998244353;

fn main() {
    input! {
        n: usize,
        a: [Usize1; n],
    }
    let mut size_count = vec![0; n];
    let mut res = 1;
    for ai in a {
        if ai > 0 {
            if size_count[ai - 1] == 0 {
                println!("0");
                return;
            }
            res *= size_count[ai - 1];
            res %= MOD;
            size_count[ai - 1] -= 1;
        }
        size_count[ai] += 1;
    }
    println!("{}", res);
}

所感

区間クエリとかにできたりしないかなぁ。右を伸ばしたり縮めたりするのは簡単だけど、左をそうするのは難しそう。← Mo のことを考えています。

サイズが \(\sqrt{n}\) より大きい集合は高々 \(\sqrt{n}\) 個しか作れないこととかを使ってなんかできたりしないかなぁ。 変な数列だとすぐ invalid になることとかも使えないかなぁ。

類題

これ が似ている気がします。

宣伝

他にも夢由来の記事はあります。

rsk0315.hatenablog.com

rsk0315.hatenablog.com

おわり

お粗末さまでした。