なんとな~くしあわせ?の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

AOJ - ITP1_7_D (行列の積) を解いてみた

ITP1_7_Dは、今自分の中でブームの行列の積の問題です。生で計算しないにしても、機械学習にも大いに関係があります。

AOJ - ITP1_7_D

Matrix Multiplication | Aizu Online Judge
自分の回答

行列の積をプログラムに起こすと?

もし自分がJavaで行列計算をするのであれば、JAMA: Java Matrix Package を使う気がします。JAMAは見た感じちゃんとオブジェクト指向的な気がします。ちなみにJavaの行列計算は全体的にパフォーマンス悪めっぽいので実際の大規模データには向かないかもしれません。

しかし、今回は競技プログラミング的なWEBテストなのでライブラリは使えません、なので生の二次元配列を使います。

問題の内容

問題自体は2つの行列を単純に掛け算するのみです。インプットの例は以下、

1:数値n, m, lが与えられる

3 2 3

2:行列 A[n][m] が与えられる、縦の数がn, 横の数がm

1 2
0 3
4 5

3:行列 b[m][l] が与えられる、縦の数がm, 横の数がl

1 2 1
0 3 2

問題の解法

手計算だとわかるのですが、これをプログラム化するのに結構苦戦しました。

行列計算の参考リンク


行列同士を掛け算すると、外側の要素が答えの要素になります。

[行列の積]
●[m×n型][n×p型]=[m×p型]
積が定義されるためには,左の列数と右の行数が等しくなければなりません。

結果は,[m×p型]となります。

なので、解答を保持する行列C = A*bとおくと、

4:行列 C[n][l] を0で初期化する

0 0 0
0 0 0
0 0 0

5:行列 C[n][l]変数i,j,kを使って埋めます。

変数は以下の範囲で動きます、が最初は行列Cの出来上がりの構造を考えたほうがいいでしょう。

  • 0 <= i < n
  • 0 <= j < m
  • 0 <= k < l