[AtCoder] ABC088 C – Takahashi’s Information

Takahashi’s Information

https://beta.atcoder.jp/contests/abc088/tasks/abc088_c

問題を読んで思い浮かぶ解法は、連立方1次方程式が解を持つかどうかでした。Javaで行列の演算を記述するのは辛いので、Pythonのnumpyを使いましょう。

考え方

連立方程式

問題を元に連立方程式を立てます。

\[
A = \begin{bmatrix}
1 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 1
\end{bmatrix}
,\ x = \begin{bmatrix}
a_1\\
a_2\\
a_3\\
b_1\\
b_2\\
b_3
\end{bmatrix}
,\ b = \begin{bmatrix}
c_{0, 0}\\
c_{0, 1}\\
c_{0, 3}\\
c_{1, 0}\\
c_{1, 1}\\
c_{1, 2}\\
c_{2, 0}\\
c_{2, 1}\\
c_{2, 2}
\end{bmatrix}
\]

与えられる連立方程式は、

\[ Ax = b\]

となります。この連立方程式が解を持つための条件は、係数行列 \( A \) と拡大係数行列 \( (A|b) \) のランクが一致することです。この内容は線形代数の連立方程式の部分で習うと思います。

ソースコード

感想

久しぶりに線形代数のことについて調べました。行列などの演算はPythonが充実しているので、積極的に使っていこうと思います。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする