More than 3 years have passed since last update.

競技プログラミング用にC++で行列（2次元平面）ライブラリを作成する

Posted at 2020-06-28

はじめに

私がよく参加するAtCoderでは実装の重い平面問題はあまり出ていないと思うのですが、いつかABCでも出題される日に備えて、C++で競技プログラミング用の行列（2次元平面）用のライブラリを作成しました。
これから自分で構造体を使ってライブラリ作成したい方の参考にもなればと思います。
行列と2次元平面は概念としては別のものですが、実装としてはどちらも2次元配列で実現できるので、本記事では用語を区別せずに使用しています。

このライブラリでできるようにした機能は下記の通りです。

2次元配列の生成
行列の演算（加減乗除、代入）
2次元配列の回転
2次元配列の出力

作成したライブラリは以下の通りです。

行列（2次元平面）ライブラリ

#include <bits/stdc++.h>
#define drep(i,cc,n) for(int i=(cc);i<=(n);++i)
#define rep(i,n) drep(i,0,n-1)
#define sz(s) (int)(s.size())
using namespace std;

template<typename T>
struct mat {
    // 行列m
    vector<vector<T>> m;
    // コンストラクタ:第1引数⇒行数、第2引数⇒列数、第3引数⇒初期値
    mat():m(vector<vector<T>>()){}
    mat(int h,int w):m(vector<vector<T>>(h,vector<T>(w))){}
    mat(int h,int w, T d):m(vector<vector<T>>(h,vector<T>(w,d))){}
    // 添字演算子
    vector<T> operator[](const int i) const {return m[i];} //読み取り
    vector<T>& operator[](const int i){return m[i];} //書き込み
    // 行数・列数
    int nrow = sz(m);
    int ncol = sz(m[0]);
    // 行列同士の演算
    mat& operator=(const mat& a){return *a;}
    mat& operator+=(const mat& a){assert(ncol == a.ncol && nrow == a.nrow);rep(i,nrow)rep(j,ncol)m[i][j] += a[i][j]; return *this;}
    mat& operator-=(const mat& a){assert(ncol == a.ncol && nrow == a.nrow);rep(i,nrow)rep(j,ncol)m[i][j] -= a[i][j]; return *this;} 
    mat& operator*=(const mat& a){assert(ncol == a.nrow);mat<T> m2(nrow, a.ncol, 0);rep(i,nrow)rep(j,a.ncol)rep(k,ncol)m2[i][j] += m[i][k]*a[k][j];ncol = a.ncol;rep(i,nrow)m[i].resize(ncol);rep(i,nrow)rep(j,ncol)m[i][j] = m2[i][j]; return *this;}
    mat operator+(const mat& a) const { return mat(*this) += a;}
    mat operator-(const mat& a) const { return mat(*this) -= a;}
    mat operator*(const mat& a) const { return mat(*this) *= a;}
    bool operator==(const mat& a){assert(ncol == a.ncol && nrow == a.nrow);bool flg = true;rep(i,nrow)rep(j,ncol)if(m[i][j] != a[i][j])flg = false; return flg;}
    // 行列とスカラの演算
    mat& operator+=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] += a;return *this;}
    mat& operator-=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] -= a;return *this;}
    mat& operator*=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] *= a;return *this;}
    mat& operator/=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] /= a;return *this;}
    mat operator+(const T& a) const { return mat(*this) += a;}
    mat operator-(const T& a) const { return mat(*this) -= a;}
    mat operator*(const T& a) const { return mat(*this) *= a;}
    mat operator/(const T& a) const { return mat(*this) /= a;}
    // 回転（degの数だけ時計回りに90度回転）
    mat& rot(int deg){
        mat<T> m2(ncol, nrow);
        if(deg == 1 || deg == 3){
            if(deg == 1)rep(i,nrow)rep(j,ncol)m2[j][nrow -i -1] = m[i][j];
            if(deg == 3)rep(i,nrow)rep(j,ncol)m2[ncol -j -1][i] = m[i][j];
            swap(ncol,nrow); // 列数と行数を入れ替える
            m.resize(nrow);rep(i,nrow)m[i].resize(ncol); //リサイズ
        }
        if(deg == 2)rep(i,nrow)rep(j,ncol)m2[nrow -i -1][ncol -j -1] = m[i][j];
        rep(i,nrow)rep(j,ncol)m[i][j] = m2[i][j];
        return *this;
    }
    // 標準出力
    void show(){
        rep(i,nrow)rep(j,ncol){
            if(j != 0)cout << " ";
            cout << m[i][j];
            if(j==ncol-1)cout << endl;
        }
        return ;
    }
};

使い方

構造体matの使い方

int main(){

    mat<int> m(2,3,2),m2(3,2,1); // オブジェクトの作成
    m[0][0] = 1; // 一部の要素を書き換え
    m.show(); // 表示
    cout << endl;

    mat<int> m3 = m * m2; // 行列同士の掛け算
    m3.show();
    cout << endl;

    m.rot(1); //時計回りに90度回転
    m.show();

    return 0;
}

実行結果

作り方

構造体の基本構造

メンバ変数

    vector<vector<T>> m;
    int nrow = sz(m);
    int ncol = sz(m[0]);

構造体とは、いくつかの変数や関数が一体となった概念です。
この構造体matは2次元配列mと2次元配列の行数・列数を表すncol、 nrowといった変数と、2次元配列mを回転させるrot()、2次元配列を標準出力するshow()を持っています。
まず、matを作成するためのコンストラクタについて、matは2次元配列なので、縦と横の次元数（hとw）を渡すと作成することができるようにしています。
また、matを使った演算を定義する必要があります。
matは2次元配列なので、各要素にアクセスするための添字演算子や行列と行列の演算、行列とスカラ（1次元の変数）の演算等が定義されています。

テンプレート

template<typename T>

構造体を宣言する前にtemplate<typename T>としておくことで、特定の型に固定しない構造体の定義が可能となります。
例えばmat<int>とするとint型の2次元配列ができ、mat<char>とするとchar型の2次元配列ができます。

コンストラクタ

    mat():m(vector<vector<T>>()){}
    mat(int h,int w):m(vector<vector<T>>(h,vector<T>(w))){}
    mat(int h,int w, T d):m(vector<vector<T>>(h,vector<T>(w,d))){}

オブジェクトの作成の仕方を定義します。
mat<int> a;のように引数を持たずに呼び出された場合、1つ目のコンストラクタmat():m(vector<vector<T>>()){}によって空の2次元配列が生成されます。
mat<int> a(2,3);のように行数と列数を指定すると、2つ目のコンストラクタによって行数・列数が決められた2次元配列が生成されます。
mat<int> a(2,3,1);のように3つの引数を与えると、3つ目のコンストラクタが該当して行数・列数・初期値が決められた2次元配列が生成されます。

添字演算子

    vector<T> operator[](const int i) const {return m[i];} //読み取り
    vector<T>& operator[](const int i){return m[i];} //書き込み

matは2次元配列がベースになっていますが、mat[i][j]等としたときにi行j列を参照するように添字演算子を定義する必要があります。
operatorを使ってvector<T> operator[](const int i) const {return m[i];}のように添字演算子を定義することで、mat[i]としたときにvectorが返されるようになります。
mat[i]のj番目の要素（mat[i][j]）へのアクセスはvector型によって定義されているので、matによって定義する必要はありません。
上記の添字演算子は読み取り専用になっているため、書き込み用の添字演算子もvector<T>& operator[](const int i){return m[i];}と定義します。

加減乗除演算子

各種演算

   // 行列同士の演算
    mat& operator=(const mat& a){return *a;}
    mat& operator+=(const mat& a){assert(ncol == a.ncol && nrow == a.nrow);rep(i,nrow)rep(j,ncol)m[i][j] += a[i][j]; return *this;}
    mat& operator-=(const mat& a){assert(ncol == a.ncol && nrow == a.nrow);rep(i,nrow)rep(j,ncol)m[i][j] -= a[i][j]; return *this;} 
    mat& operator*=(const mat& a){assert(ncol == a.nrow);mat<T> m2(nrow, a.ncol, 0);rep(i,nrow)rep(j,a.ncol)rep(k,ncol)m2[i][j] += m[i][k]*a[k][j];ncol = a.ncol;rep(i,nrow)m[i].resize(ncol);rep(i,nrow)rep(j,ncol)m[i][j] = m2[i][j]; return *this;}
    mat operator+(const mat& a) const { return mat(*this) += a;}
    mat operator-(const mat& a) const { return mat(*this) -= a;}
    mat operator*(const mat& a) const { return mat(*this) *= a;}
    bool operator==(const mat& a){assert(ncol == a.ncol && nrow == a.nrow);bool flg = true;rep(i,nrow)rep(j,ncol)if(m[i][j] != a[i][j])flg = false; return flg;}
    // 行列とスカラの演算
    mat& operator+=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] += a;return *this;}
    mat& operator-=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] -= a;return *this;}
    mat& operator*=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] *= a;return *this;}
    mat& operator/=(const T& a){rep(i,nrow)rep(j,ncol)m[i][j] /= a;return *this;}
    mat operator+(const T& a) const { return mat(*this) += a;}
    mat operator-(const T& a) const { return mat(*this) -= a;}
    mat operator*(const T& a) const { return mat(*this) *= a;}
    mat operator/(const T& a) const { return mat(*this) /= a;}

matを用いた加減乗除等の演算を定義します。
例としてmat同士の足し算mat& operator+=(const mat& a){assert(ncol == a.ncol && nrow == a.nrow);rep(i,nrow)rep(j,ncol)m[i][j] += a[i][j]; return *this;}について説明します。
まず、行列同士の足し算においては2変数の行数・列数が一致している必要があるため、assert(ncol == a.ncol && nrow == a.nrow)しています。
あとは要素ごとに足し算をしています。
足し算によって行列の行数・列数が変化することはありませんが、行列同士の掛け算や後述の回転関数によって元の行列の行数・列数が変化する場合があります。
そのようなケースにはnrow、ncolを書き換えるとともに、行列mをresizeする操作をしています。

関数

回転（rot）

回転

    mat& rot(int deg){
        mat<T> m2(ncol, nrow);
        if(deg == 1 || deg == 3){
            if(deg == 1)rep(i,nrow)rep(j,ncol)m2[j][nrow -i -1] = m[i][j];
            if(deg == 3)rep(i,nrow)rep(j,ncol)m2[ncol -j -1][i] = m[i][j];
            swap(ncol,nrow); // 列数と行数を入れ替える
            m.resize(nrow);rep(i,nrow)m[i].resize(ncol); //リサイズ
        }
        if(deg == 2)rep(i,nrow)rep(j,ncol)m2[nrow -i -1][ncol -j -1] = m[i][j];
        rep(i,nrow)rep(j,ncol)m[i][j] = m2[i][j];
        return *this;
    }

線形代数でいうrotではなく、単純に行列を時計回りに90度回転させる関数です。
引数degの回数分、行列を回転させます。
行列mの行数・列数が異なる場合、90度回転（deg=1）と270度回転（deg=3）のときには行数・列数が入れ替わります。
そのため、そのような場合にはmをresizeして行数・列数を変えるとともにメンバ変数ncol、nrowの値を入れ替えます。

表示（show）

表示

    void show(){
        rep(i,nrow)rep(j,ncol){
            if(j != 0)cout << " ";
            cout << m[i][j];
            if(j==ncol-1)cout << endl;
        }
        return ;
    }

行列の各要素を確認するときに標準出力させるための関数です。
行が変わるたびに改行をしています。

おわりに

いずれAtCoderでこのライブラリを使って楽に解ける問題が出てきましたら掲載します。
実装においておかしい点や、こうしたらもっとスマートだよ！といった点がありましたらコメントでお教えいただけるとありがたいです。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up