AGC022 C - Remainder Game

問題 → C: Remainder Game - AtCoder Grand Contest 022 | AtCoder

解法概要

各 $(a_i, b_i)$ に対して条件を満たす集合を列挙
貪欲で条件を満たす集合を最小化

$a_i$ の最大値を $K(=50)$ とおくと、全体の計算量は $O(NK^3)$

解法

1. 各 $(a_i, b_i)$ に対して条件を満たす集合を列挙

$X = \{0, 1, \cdots, 50\}$ とおく。

$f(x, y) := \{A \in 2^X \mid \text{$A$に含まれる数を使って、操作によって$a_i$を$b_i$に変えられる}\}$

とすると $f: X\times X \rightarrow 2^{2^X}$ は

${\displaystyle f(x, y) = \begin{cases} \{\emptyset\}\, \text{ if } x=y\\ \displaystyle\bigcup_{i\in\{1, \cdots, x\}} \{ \{i\} \cup A \mid A\in f(x\%i, y) \}\, \text{ otherwise } \end{cases} }$

となり、コードに落とすと次のようになる。

long[] f(long x, long y) {
    if (x == y) return [0L];
    long[] res = [];
    foreach(i; 1..x+1) {
        res ~= f(x%i, y).map!(bits => bits|1L<<i).array;
    }
    return res;
}

雑に計算量を求めると $f(x, y)$ の計算に $O(x^2)$ かかる。各 $f(a_i, b_i)$ を求めると合わせて $O(NK^2)$ 。

2. 貪欲で条件を満たす集合を最小化

$\mathscr{A} := \{A\in 2^X \mid \text{$A$は問題の条件を満たす}\}$ とおく。

$\displaystyle \arg\min _{A\in\mathscr{A}} \sum_{i \in A} 2^i$ が最終的な答え。
なければ-1を出力。

$\displaystyle A\in \mathscr{A} \iff {}^\forall i\in\{1, \cdots, N\}, {}^\exists B\in f(a_i, b_i) \text{ s.t. } B\subset A$ が成り立つので、この判定は愚直に $O(NK^2)$ でできる。

$\displaystyle \arg\min _{A\in\mathscr{A}} \sum_{i \in A} 2^i$ の一つを $S$ とおく。 $\displaystyle \sum_{i=0}^n 2^i = 2^{n+1}-1 \le 2^{n+1}$ より ${}^\forall i\in X$ に対して次が成り立つ。

$i\notin S \iff \{j\in S \mid j\gt i\} \cup \{j\in X\mid j\lt i\} \in \mathscr{A}$

よって最高位ビットから順に貪欲すれば $S$ が求まる。

long ans = (1L<<K)-1;
foreach_reverse(i; 0..K) {
    long bits = ans>>(i+1)<<(i+1)|((1L<<i)-1);
    if (/* 集合bitsは\mathscr{A}に含まれるか？ */) {
        ans = bits;
    }
}