💡

TOYPRO解説記事 - 連立方程式(300点)

2021/04/21に公開

トイプロ解説

tech

1.概要

競技プログラミングのサイト「TOYPRO」の300点問題、連立方程式の解説をします！
問題はコチラ！(https://app.toy-pro.net/user/questions/190)

2.問題

連立方程式

\begin{cases} ax + by = c\\ a'x + b'y = c' \end{cases}

があります。
$a, b, c, a', b', c'$ がnumsとして与えられるので、 $(x, y)$ を出力してください。
なお、 $(x, y)$ は1以上の整数であり、 $a, b, c, a', b', c'$ も1以上の整数であるものとします。
※ numsは $(x,y)$ がもとまる値だけを考えるものとします。

制約

$1 ≦ x, y ≦ 10^{13}$

入力例

nums = [1, 2, 5, 6, 7, 20]

出力例

(1,2)

3.解説

3-1.素朴な解法

まず、素朴な解法としてあり得る $(x, y)$ の組を全探索することが考えられます。
この解法を実装すると次のようなコードになります。

nums = [1, 2, 5, 6, 7, 20]

for x in range(1, 10 ** 13 + 1):
    for y in range(1, 10 ** 13 + 1):
        if nums[0] * x + nums[1] * y == nums[2] and nums[3] * x + nums[4] * y == nums[5]:
            print(x, y)
            exit()

これを提出してみましょう、意外と簡単でしたね

ぐるぐる...

ぐるぐる...

ぐるぐる.........

と、いうことで、俗に言うTLE(時間切れ)になってしまいました。
これは、コンピューターが可能な計算の量を超えてしまったからです。
みなさんも、例えば1から1000までを足してください、と言われたら、どんなに早い人でも10分くらいはかかってしまうと思います。^[1]
それと同じように、コンピューターも計算の回数などに制限があるんです！
え、コンピューターならなんでもすぐ計算できるんじゃないの?と思われる方もいらっしゃるかもしれませんが、実は今のコンピューターでは2秒間に $10 ^ 8$ 回程度しか計算できません。
したがって、ToyProでもだいたい $10 ^ 8$ 程度の計算量^[2]のプログラムを提出する必要があります。
(少し難しいですが、興味のある方はけんちょんさんの記事を読むと一層理解が深まると思います。)

3-2.それならば

せっかく方程式なのだから、変形したくなりますよね!(え、なりませんか?)
と、いうことで頑張って変形してみます。

\begin{cases} ax + by = c　　・・・①\\ a'x + b'y = c'　　・・・② \end{cases}

$①$ の方程式を変形します　(∩^o^)⊃━☆゜.*

ax + by = c

$by$ を移項して...

ax = c - by

両辺を $a$ で割って...

x = \frac{c - by}{a}

みなさん、もう気がづきましたか?
実はこれ、 $y$ が求まれば $x$ も自然に決まるんです!
考えてみれば当たり前の話で、人間が連立方程式を解くときも $x$ か $y$ のどちらかを求めてから、片方の式に代入して解きますよね?
それでは、 $y$ を決めれば、 $x$ も決まる、ということは...?

そう、ループを回して決めるのは $y$ だけで良いんです!
で、上の式に $y$ を代入して、 $x$ を求める、と。

得られた $(x, y)$ の組が $②$ の方程式でも成立するかどうかを確認して、成立するなら、これがこの連立方程式の解、だーーーー！！！

と、なる気持ちはわかります。しかし、制約をよく見てみましょう。

ん?

あっ...

3-3.ｳｿﾞﾀﾞﾄﾞﾝﾄﾞｺﾄﾞｰﾝ!

聡明な読者諸君は既にお気づきでしょう。
$y$ だけをループで決定しても、結局 $10^{13}$ 回計算することになり、先程くどくど話した計算量^[2:1]の限界である $10^8$ を優に超えてしまうのです。
悲しいなあ、やっぱりこの問題、解けないんじゃないの?
うーん、これ以上ループ回数を減らす方法は簡単には思いつけなさそうだ...。
これ以上方程式をこねくり回すのも難しそうだしなあ...

あれ、待てよ?

3-4.ブレイクスルー

また数式をこねくりまわす時間だー！

\begin{cases} ax + by = c　　・・・①\\ a'x + b'y = c'　　・・・② \end{cases}

の $①$ の式は、

x = \frac{c - by}{a}

と変形できることは前に確認済みです。
ここから何か発展できないでしょうか?

そのとおり！ $②$ の式への代入です。

x = \frac{c - by}{a}　　・・・③

この式を③ と名付けることにしました。

$③$ を $②$ に代入して、

a'\Big(\frac{c - by}{a}\Big) + b'y = c'

展開して、

\Big(\frac{a'c}{a}\Big) - \Big(\frac{a'by}{a}\Big) + b'y = c'

$\Big(\frac{a'c}{a}\Big)$ を右辺に移項して、

- {\frac{a'by}{a}} + b'y = c' - {\frac{a'c}{a}}

$y$ で括りだして、

y\Big(b' - \frac{a'b}{a}\Big) = c' - \frac{a'c}{a}

$\Big(b' - \frac{a'b}{a}\Big)$ で両辺を割って

\LARGE{y = \frac{c' - \frac{a'c}{a}}{b' - \frac{a'b}{a}}}

Oh, My Gosh!!!
$y$ を $(a, b, c, a', b', c')$ だけを使って求める式が完成しちゃいました!
$y$ が求まったらもう煮るなり焼くなり $③$ に代入するなりして、 $x$ を求めればいいですね。
これをプログラムにすると、こうなります

nums = [1, 2, 5, 6, 7, 20]

# それぞれ
# a:nums[0]
# b:nums[1]
# c:nums[2]
# a':nums[3]
# b':nums[4]
# c':nums[5] を表す。

y = int((nums[5] - (nums[3] * nums[2]) / nums[0]) / (nums[4] - (nums[3] * nums[1] / nums[0])))
x = int((nums[2] - nums[1] * y) / nums[0])

print(f"({str(x)},{str(y)})")

4-1.FOOOOOO!! It's Amazing!

結局、2回の計算、つまり計算量^[2:2]O(1)で実装することができました！
いやあ、長かった（涙）
今回の問題は、ToyProではかなり難しい部類の問題です。（難易度☆3では少し低すぎるかな、とも思ったりしているくらいです）
ですが、こういうコンピューターの処理能力に頼りすぎないプログラムを書くことは、将来、絶対に役に立ってきます。
ToyProの問題を埋めてゆく時や、もちろん普段のプログラミングでも、そういうことを意識しながら書くと、より一層のスキルアップにつながるのではないでしょうか。

4-2.+αで知っておく

4-2-1.計算量の表し方

この記事では、計算量を「だいたい $x$ 」や「だいたい $10^{13}$ 」などと書いていますが、この「だいたいこのくらい」という計算量の表し方として、「オーダー記法」というものがあります。
厳密な定義は置いておいて、 $O(x)$ などと書き、xに比例した計算量がかかることを意味しています。
Pythonでは一秒間にだいたい10^8回くらいの計算ができると思っておけば良いと思います。
くわしくはけんちょんさんの記事へGO！

4-2-2.等差数列の和の公式

みなさんも、例えば1から1000までを足してください、と言われたら、どんなに早い人でも10分くらいはかかってしまうと思います。

と言いましたが、これは嘘です（すいません）。
自分は計算が遅い方なのですが、そんな僕でもこの問題をすぐに解く方法があります。
それは、等差数列の和の公式を使う方法です。

等差数列の和の公式
$1$ から $n$ までの整数の総和は、

\LARGE\frac{n(1 + n)}{2}

である。

...詳しく見ていきましょうか。
まず、最初に「 $1$ から $n$ までの整数の総和」がどんなものかを考えます。
これはすぐにわかると思います。 $n = 10$ のときなら、
$1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10$ です。
一般的に表すと、
$1 + 2 + 3 + 4 + 5 + 6 + 7 + \cdots + (n - 2) + (n - 1) + n$ となります。
さて、これをもう少し計算しやすくしてみましょう。

S = 1 + 2 + 3 + 4 + 5 + 6 + 7 + \cdots + (n - 2) + (n - 1) + n

と定義します。

ここで、 $2S$ は、

\begin{array}{rcccccc} S &= &1+ &2 + &\cdots + &n\\ S &=&n+ &(n - 1) + &\cdots + &1\\ \hline 2S &= &(n + 1) + &(n + 1) + &\cdots &+ &(n + 1)\\ \end{array}

より、 $2S = n(n + 1)$ となります。
よって、

2S = n(n + 1) S = \frac{n(n + 1)}{2}

となり、最初に言った、

等差数列の和の公式
$1$ から $n$ までの整数の総和は、

$\LARGE\frac{n(1 + n)}{2}$
である。

が導かれます。
さて、ここからが大事です。
1から $n$ までの和が求められるということは、任意の整数 $a$ から任意の整数 $b$ までの和も求めることができます。
どういうことかというと、 $1$ から $a$ までの和を $s_a$ 、 $1$ から $b$ までの和を $s_b$ とすると、 $a$ から $b$ までの和は、 $s_b - s_a$ で求められるからです。これは図を書いてみるとわかりやすいと思います。

\underbrace{\overbrace{1, 2, 3, 4, \cdots, a}^{\it s_a}, \overbrace{a + 1, a + 2, a + 3, a + 4, \cdots, b - 2, b - 1, b}^{\it {s_b - s_a}}}_{\it s_b}

また、差が1ではない等差数列の和を求めることもできるので、考えてみてください。

5.ということで

結構長くなってしまいましたが、ToyProの問題、「連立方程式」の解説でした！
他にも面白い問題がたくさんあるので、是非ご利用ください！！！
https://app.toy-pro.net/

6.連立一次方程式の解を求めるアルゴリズム(4/21/21:47追記)

っていうのが存在します。自分の中で一番有名(適当)なのは「Gauss-Jordanの消去法」です。
ここでは深く掘り下げませんが^[3]、興味がある方は調べてください。(丸投げ)
また、連立一次方程式の解を求める公式として、クラメルの公式というものもあります。
同様の理由^[3:1]で、深くは掘り下げません。

脚注

4-2-2.等差数列の和の公式を参照のこと ↩︎
4-2-1.計算量の表し方を参照のこと ↩︎ ↩︎ ↩︎
とか言ってますが自分が理解できてないだけです ↩︎ ↩︎