ABC347 C - Ideal Holidays

休日開始曜日で全探索。（実際には、予定のある曜日だけを休日開始曜日とすればよい）

または、予定を覆うような曜日区間の区間長がa以下のものがあるか、と考える。

    fn solve2(&self) -> Answer {
        // ソートによる解法
        let a = self.a;
        let b = self.b;
        let n = self.n;
        let ds = &self.ds;
        // 各予定の曜日(今日を0とする)のリスト
        let ds_mod = ds.iter().copied().map(|x| x % (a + b)).collect_vec();
        let ds_mod_plus_apb = ds_mod.iter().copied().map(|x| x + (a + b)).collect_vec();
        let ds_mod_loop = chain!(ds_mod, ds_mod_plus_apb).sorted().collect_vec();
        let ans = (0..n)
            // iから始まるn個の予定の曜日を含む曜日区間の長さの最小値
            .map(|i| ds_mod_loop[n + i - 1] - ds_mod_loop[i] + 1) // i..i+n での区間の最大-最小 + 1
            .any(|x| x <= a);
        Answer { ans }
    }

学び

• ループは倍化すると扱いやすい
  • 倍化しなくても mod を取る方法もある
• （この問題から学びを得るの難しい）

抽象化

円環上の集合をある種の区間で覆うときの最小区間長を求める

• 問題

  • $x, y \in \mathbb{Z}/N\mathbb{Z}$ に対して、$[x,y] = \{x, x+1, …, y\}$ と定義します。
    • 例えば
      • $N=7, x=[2], y=[4]$ の場合、$[x,y] = \{[2], [3], [4]\}$
      • $N=7, x=[5], y=[1]$ の場合、$[x,y] = \{[5], [6], [0], [1]\}$
  • $\mathbb{Z}/N\mathbb{Z}$ の空でない部分集合 $A$ が与えられます。
  • $\min \{\#[x,y] \mid x, y \in \mathbb{Z}/N\mathbb{Z}, A \subseteq [x,y]\}$ を求めてください。

• 制約

  • $2 \leq N \leq 10^{9}$
  • $1 \leq \#A \leq 2\times 10^{5}$

• 例

  • $N = 7, A = \{[0], [2], [6]\}$ の場合

    • $[[6], [2]] = \{[6], [0], [1], [2]\}$ の要素数 $4$ が答え

      

• 方針

  • $[x,y] \subseteq A$ とする。$\#[x,y]$ が求めたい最小値であれば、$x, y \in A$ を満たす。
    • 貪欲法のノリで背理法をする
  • 各 $x \in A$ に対して、$\min \{\#[x,y] \mid y \in \mathbb{Z}/N\mathbb{Z}, A \subseteq [x,y]\}$ を求めればよい。
    • 一変数固定するのは典型

• 解法

  • $A$ の各元の代表元を $0$ から $N-1$ で取っておいて、ソートする。ソートしたものを $(b_0, \ldots, b_{k-1})$ とする。(重複排除が必要)
  • $\min \{ (b_{(i - 1)\%k} - b_i) \% N + 1 \mid i=0,1,\ldots,k-1\}$ が答え
    • $[[b_i], [b_{(i-1)\%k}]]$ という区間を考える

  let xs_rep_sorted = xs
      .iter()
      .copied()
      .map(|x| x % n)
      .sorted()
      .dedup()
      .collect_vec();
  
  let ans = xs_rep_sorted
      .iter()
      .copied()
      .circular_tuple_windows()
      .map(|(end_inclusive, begin)| (end_inclusive - begin).rem_euclid(n) + 1)
      .min()
      .unwrap();