読者です 読者をやめる 読者になる 読者になる

足跡-sokuseki-

りかの日進月歩の記録

ABC 006 C スフィンクスのなぞなぞ

競技プログラミング AtCoder

数式が出てきたのでメモ。

C: スフィンクスのなぞなぞ - AtCoder Beginner Contest 006 | AtCoder

問題概要

大人、老人、赤ちゃんの足の数をそれぞれ2本、3本、4本とする。
街の人数Nと足の数Mが与えられるので大人、老人、赤ちゃんの人数の組み合わせを1つ答えよ。存在しない場合はすべて-1で答えよ。

制約
 1 \le N \le 10^5
 1 \le M \le 10^5

部分点あるけどここでは割愛

解法

連立方程式を解くだけ。

大人の人数をa、老人の人数をe、赤ちゃんの人数をbとする。
ただし、人数なのでそれぞれ非負整数である。

このとき、街の人口については

 a + e + b = N  …(1)

足の本数について

 2a + 3e + 4b = M  …(2)

という2つの方程式を立てることができる。

よって連立させて式を変形させることで、変数を1つに減らすことができる*1

まず(1)式をeについての式に変形する

 e = N - a - b  …(3)

そして(3)式を(2)式に代入して、aについて解く

 2a + 3( N - a - b ) + 4b = M

 3N - a + b = M

 a = b + 3N - M  …(4)

また、(4)式を(1)式に代入して、eについて解くと

 ( b + 3N - M ) + e + b = N

 2b + e + 2N - M = 0

 e = M - 2N - 2b  …(5)


以上のように、(1)(2)の連立方程式から(4)(5)の式が得られた。(4)(5)の2式は人口についてと足の本数についての制約を満たすので、あとは3つの変数a、e、bが非負整数であれば、答えとなる。

変数bが決まればaとeは確定するので、bがとりうる値(0からNまで)をループで回してやれば、全通り試せる。
よって、計算量は  O(N)


Submission #1152289 - AtCoder Beginner Contest 006 | AtCoder

感想

数学は楽しい(これは真理)。

実は私のソースコードだと  a = e = 0 の場合も答えとなってしまう(サンプル1だと「 0 3 0 」を出力する)けど、実際問題、街に大人と老人がいなくて赤ちゃんだけ存在するというのはおかしいなあ大丈夫かなあと思いながらsubmitしたらACしてしまったので拍子抜けした。

*1:連立方程式は連立した式の数だけ変数を減らすことができる。変数が3つで式が2つなので、変数は2つ減らせる