Ark's Blog

引っ越しました→ https://blog.arkark.dev/

ようこそ

ABC085 C - Otoshidama O(1)解法

この問題は、制約がゆるいので O(n^2)解法で十分通るのですが、解説によれば O(1)でも通せるみたいです。

計算したら  O(1) 解法ができたので書きます。

問題

この問題をまとめると次のようになります。

  • 入力: N, Y \in \mathbb{N}
    • ただし  Y 1000の倍数
  • 出力:次を満たす x, y, z\in \mathbb{N}の組のうち一つ。存在しない場合は-1 -1 -1を出力。
    •  10000x + 5000y + 1000z = Y
    •  x + y + z = N

解法

考え方的には高校数学です。

まず変数消去すると

\begin{aligned} 9000x + 4000y = Y - 1000N \end{aligned}

となります(今回は zを消去しました)。

制約より Y 1000の倍数なので t := \frac{Y-1000N}{1000}とおくと t\in \mathbb{Z}となり、

\begin{aligned} 9x + 4y = t \end{aligned}

となります。 これは二元一次不定方程式なので次のような方法で自由度1で解けます。証明はここなどを見てください。

まず、 \gcd(9, 4) = 1より t \gcd(9, 4)の倍数なので整数解 (x, y)が存在します。

解くと \begin{aligned} \begin{cases} x &= 4k + (t \bmod 4) \\ y &= -9k + \frac{t - 9(t \bmod 4)}{4} \end{cases}\\ k \in \mathbb{Z} \end{aligned} となります。 a:= (t \bmod 4) b :=  \frac{t - 9(t \bmod 4)}{4}とおくと

\begin{aligned} \begin{cases} x &= 4k +a \\ y &= -9k + b \end{cases}\\ k \in \mathbb{Z} \end{aligned}

です。ちなみに bは必ず整数になります。

あとは問題の条件をみたすような kの条件を考えるだけです。

まだ使ってない条件は x, y, z \geq 0で、上の関係式などを使うと

\begin{cases} 0\leq 4k + a \\ 0\leq -9k + b \\ (4k + a) + (-9k + b) \leq N \end{cases}

整理すると

\begin{aligned} \max\left\{ \frac{-a}{4} , \frac{a + b - N}{5} \right\} \leq k \leq \frac{b}{9} \end{aligned}

となります。 つまり

  •  k_{\min} := \max\left\{ \left\lceil \frac{-a}{4} \right\rceil , \left\lceil  \frac{a + b - N}{5} \right \rceil \right\}
  •  k_{\max} := \left\lfloor \frac{b}{9} \right\rfloor

とおくと( \lceil \cdot \rceil \lfloor \cdot \rfloorはそれぞれ天井関数、床関数)、 k_{\min} \leq k \leq k_{\max}となり、次のような結論になります。

(i)  k_{\min} \leq k_{\max}のとき

問題の条件すべてを満たすような x, y, zの組が存在し、そのうちの組の一つは

  •  x = 4k_{\min} + a
  •  y = -9k_{\min} + b
  •  z = N - x - y

となる。

(ii)  k_{\min} > k_{\max}のとき

問題の条件すべてを満たすような x, y, zの組は存在しない。

ソースコード

void main() {
    int N; long Y;
    scanln(N, Y);

    // 10000x + 5000y + 1000z = Y
    // x + y + z = N

    long t = (Y - 1000*N) / 1000;
    // 9x + 4y = t

    long a = t%4;
    long b = (t - 9*(t%4)) / 4;
    // x =  4k + a
    // y = -9k + b

    long minK = max(ceil(-a, 4), ceil(a + b - N, 5));
    long maxK = floor(b, 9);
    if (minK <= maxK) {
        long k = minK; // minK <= k <= maxK
        long x = 4*k + a;
        long y = -9*k + b;
        long z = N - x - y;
        writeln(x, " ", y, " ", z);
    } else {
        writeln("-1 -1 -1");
    }
}

無事 O(1)でACがとれました。