ABC085 C - Otoshidama O(1)解法
この問題は、制約がゆるいので解法で十分通るのですが、解説によればでも通せるみたいです。
計算したら 解法ができたので書きます。
問題
この問題をまとめると次のようになります。
- 入力:
- ただし はの倍数
- 出力:次を満たすの組のうち一つ。存在しない場合は
-1 -1 -1
を出力。
解法
考え方的には高校数学です。
まず変数消去すると
\begin{aligned} 9000x + 4000y = Y - 1000N \end{aligned}
となります(今回はを消去しました)。
制約よりはの倍数なのでとおくととなり、
\begin{aligned} 9x + 4y = t \end{aligned}
となります。 これは二元一次不定方程式なので次のような方法で自由度1で解けます。証明はここなどを見てください。
まず、よりはの倍数なので整数解が存在します。
解くと \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} となります。、とおくと
\begin{aligned} \begin{cases} x &= 4k +a \\ y &= -9k + b \end{cases}\\ k \in \mathbb{Z} \end{aligned}
です。ちなみには必ず整数になります。
あとは問題の条件をみたすようなの条件を考えるだけです。
まだ使ってない条件はで、上の関係式などを使うと
\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}
となります。 つまり
とおくと(、はそれぞれ天井関数、床関数)、となり、次のような結論になります。
(i) のとき
問題の条件すべてを満たすようなの組が存在し、そのうちの組の一つは
となる。
(ii) のとき
問題の条件すべてを満たすようなの組は存在しない。
ソースコード
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"); } }
無事でACがとれました。