TOYPRO解説記事 - 連立方程式(300点)
1.概要
競技プログラミングのサイト「TOYPRO」の300点問題、連立方程式の解説をします!
問題はコチラ!(https://app.toy-pro.net/user/questions/190)
2.問題
連立方程式
があります。
なお、
※ numsは
制約
入力例
nums = [1, 2, 5, 6, 7, 20]
出力例
(1,2)
3.解説
3-1.素朴な解法
まず、素朴な解法としてあり得る
この解法を実装すると次のようなコードになります。
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秒間に
したがって、ToyProでもだいたい
(少し難しいですが、興味のある方はけんちょんさんの記事を読むと一層理解が深まると思います。)
3-2.それならば
せっかく方程式なのだから、変形したくなりますよね!(え、なりませんか?)
と、いうことで頑張って変形してみます。
両辺を
みなさん、もう気がづきましたか?
実はこれ、
考えてみれば当たり前の話で、人間が連立方程式を解くときも
それでは、
そう、ループを回して決めるのは
で、上の式に
(x, y) の組が② の方程式でも成立するかどうかを確認して、成立するなら、これがこの連立方程式の解、だーーーー!!!
得られたと、なる気持ちはわかります。しかし、制約をよく見てみましょう。
ん?
あっ...
3-3.ウゾダドンドコドーン!
聡明な読者諸君は既にお気づきでしょう。
悲しいなあ、やっぱりこの問題、解けないんじゃないの?
うーん、これ以上ループ回数を減らす方法は簡単には思いつけなさそうだ...。
これ以上方程式をこねくり回すのも難しそうだしなあ...
あれ、待てよ?
3-4.ブレイクスルー
また数式をこねくりまわす時間だー!
の
と変形できることは前に確認済みです。
ここから何か発展できないでしょうか?
そのとおり!
この式を③ と名付けることにしました。
展開して、
Oh, My Gosh!!!
これをプログラムにすると、こうなります
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.計算量の表し方
この記事では、計算量を「だいたい
厳密な定義は置いておいて、
Pythonでは一秒間にだいたい10^8回くらいの計算ができると思っておけば良いと思います。
くわしくはけんちょんさんの記事へGO!
4-2-2.等差数列の和の公式
みなさんも、例えば1から1000までを足してください、と言われたら、どんなに早い人でも10分くらいはかかってしまうと思います。
と言いましたが、これは嘘です(すいません)。
自分は計算が遅い方なのですが、そんな僕でもこの問題をすぐに解く方法があります。
それは、等差数列の和の公式を使う方法です。
等差数列の和の公式
である。
...詳しく見ていきましょうか。
まず、最初に「
これはすぐにわかると思います。
一般的に表すと、
さて、これをもう少し計算しやすくしてみましょう。
と定義します。
ここで、
より、
よって、
となり、最初に言った、
等差数列の和の公式
から 1 までの整数の総和は、 n
\LARGE\frac{n(1 + n)}{2}
である。
が導かれます。
さて、ここからが大事です。
1から
どういうことかというと、
また、差が1ではない等差数列の和を求めることもできるので、考えてみてください。
5.ということで
結構長くなってしまいましたが、ToyProの問題、「連立方程式」の解説でした!
他にも面白い問題がたくさんあるので、是非ご利用ください!!!
6.連立一次方程式の解を求めるアルゴリズム(4/21/21:47追記)
っていうのが存在します。自分の中で一番有名(適当)なのは「Gauss-Jordanの消去法」です。
ここでは深く掘り下げませんが[3]、興味がある方は調べてください。(丸投げ)
また、連立一次方程式の解を求める公式として、クラメルの公式というものもあります。
同様の理由[3:1]で、深くは掘り下げません。
Discussion