Ark's Blog

数学とか競プロとかCTFとか参加記とか備忘録とか

ようこそ

AGC022 C - Remainder Game

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

解法概要

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

 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;
    }
}

提出コード

感想

コンテスト中、大体の考察はできてたけど時間に追われて焦って考察&コーディングをしたためWA連発。AC取れず。悲しい

問題自体は、コストが 2^kであったり制約が「 \leq 50」であったりと誘導(?)が強い問題だったと思う。考察重視のわりと好きなタイプの問題。