124. 連立一次方程式
【問題概要】
連立一次方程式を解くプログラムを作成せよ。ただし、行列の数値や変数の数は不定とし、行列は配列で表現するものとする。
【解説】
連立一次方程式は、行列やベクトルの演算で表現されることがあります。一般に、係数行列を A、未知数のベクトルを x、定数項のベクトルを b とすると、次のように表されます。
Ax = b
この方程式は、逆行列を用いて x = A^-1b という形で解くことができます。ただし、A が正則行列である場合に限り、逆行列が存在するために解が一意的に存在します。A が正則行列でない場合、解が存在しないか、複数存在する場合があります。
そこで、この問題では、まず行列 A が正則行列であるかどうかを判定する必要があります。行列 A が正則行列であるためには、行列式 det(A) が 0 でなければなりません。行列式は、各要素の積と和の組み合わせで表されるため、再帰的な計算が必要です。
行列式が 0 でなければ、逆行列を求めることができます。逆行列を用いて、未知数のベクトル x を求めることができます。
ただし、この問題では、行列やベクトルの数値や変数の数が不定であるため、行列の演算を直接行うことはできません。そのため、行列やベクトルを配列で表現し、演算を配列の操作で行う必要があります。
【関連する問題】
Atcoderの「Matrix Power」問題が、本問題と関連があります。以下は、その問題の情報です。
「Matrix Power」
レーティング難易度(★): 2200
ACした回答者に絞った場合のレーティング帯の範囲(数値): 1689 - 2471
レーティング難易度(%): 50.8%
レーティング(数値): 2129
AC率(%): 6.5%
ACしたスコアの高い回答者: https://atcoder.jp/users/TaninA
解説ブログ: https://atcoder.jp/contests/abc206/editorial/2228
Discussion