Learning Algorithms

アルゴリズムの勉強メモ

AOJ Graph Automata Player

AOJ Graph Automata Player

Graph Automata Player | Aizu Online Judge

感想

ICPCのチーム練習で解いた。好きな感じの問題なので、じーーっと考察していると解法がわかった。

解法

ある頂点に注目して考える。ある状態から次の状態に遷移するとき、その頂点から移動可能な点に書かれた数の総和が奇数であるとき、その頂点は$\ 1\ $になる、という風に読み替えるとわかりやすい。よく考えると、この頂点から(自分を含む)(他の各頂点に対して接続しているかどうか)の情報列と、(各頂点の値)の情報列の内積のようなもの(?)をとれば、その総和が計算できる。このことから、隣接行列を$\ G\ $、時刻$\ t\ $での状態を$\ S_{t}\ $、時刻$\ t - 1\ $での状態を$\ S_{t - 1}\ $とすると、$\ S_{t} = G * S_{t - 1}\ $と表すことができる。

よって、$\ G\ $の逆行列が存在するならば、明らかに$\ S_{-T} = (G^{-1})^T * S_{0}\ $が成り立つので、これを計算するだけでよい。

存在しない場合は、解の存在性を見ればよい。すなわち、$\ G^T * S_{-T} = S_{0}\ $という方程式を満たす解$\ S_{-T}\ $が存在するかどうかを判定できればよい。線形代数の教科書を取り出して復習してみると、$\ Ax = b\ $の解が存在するための必要十分条件が$\ rank([A : b]) = rank(A)\ $が成り立つことであるとわかるため、そのように判定する。解が存在すればambiguous、存在しないならばnoneである。

ただし、行列の中身は常に$\ mod\ 2\ $で見ておき、小数が現れないようにすることができる。

実装
#include "bits/stdc++.h"
using namespace std;

typedef int Type;
typedef vector<vector<Type>> Matrix;

int GetRank(Matrix a) {
        int h = a.size(), w = a[0].size();
        int res = 0, now = 0;
        for (int i = 0; i < h; i ++) {
                Type ma = 0.0;
                int pivot;
                for (int j = i; j < h; j ++) {
                        if (a[j][now] > ma) {
                                ma = a[j][now];
                                pivot = j;
                        }
                }
                if (ma == 0.0) {
                        now ++;
                        if (now == w) break;
                        i --;
                        continue;
                }
                if (pivot != i) {
                        for (int j = 0; j < w; j ++) { 
                                swap(a[i][j], a[pivot][j]);
                        }

                }
                Type tmp = 1.0 / a[i][now];
                for (int j = 0; j < w; j ++) a[i][j] *= tmp;
                for (int j = 0; j < h; j ++) {
                        if (i != j) {
                                Type tmp2 = a[j][now];
                                for (int k = 0; k < w; k ++) {
                                        a[j][k] = ((a[j][k] - a[i][k] * tmp2) + 2) % 2;
                                }
                        } }
                res ++;
        }
        return res;
}
bool Inv(Matrix a, Matrix &inv) { //square
        int n = a.size();
        for (int i = 0; i < n; i ++) {
                for (int j = 0; j < n; j ++) {
                        inv[i][j] = (i == j ? 1.0 : 0.0);
                }
        }
        for (int i = 0; i < n; i ++) {
                Type ma = 0.0;
                int pivot;
                for (int j = i; j < n; j ++) { 
                        if (a[j][i] > ma) {
                                ma = a[j][i];
                                pivot = j;
                        }
                }
                if (ma == 0.0) return false; //no inverse matrix
                if (pivot != i) {
                        for (int j = 0; j < n; j ++) { 
                                swap(a[i][j], a[pivot][j]);
                                swap(inv[i][j], inv[pivot][j]);
                        }

                }
                Type tmp = 1.0 / a[i][i];
                for (int j = 0; j < n; j ++) {
                        a[i][j] *= tmp;
                        inv[i][j] *= tmp;
                }
                for (int j = 0; j < n; j ++) {
                        if (i != j) {
                                Type tmp2 = a[j][i];
                                for (int k = 0; k < n; k ++) {
                                        a[j][k] = ((a[j][k] - a[i][k] * tmp2) + 2 ) % 2;
                                        inv[j][k] = ((inv[j][k] - inv[i][k] * tmp2) + 2) % 2;
                                }
                        }
                }
        }
        return true;
}

Matrix Mul(const Matrix &a, const Matrix &b) {
        Matrix c(a.size(), vector<Type> (b[0].size()));
        for (int i = 0; i < a.size(); i ++) {
                for (int k = 0; k < b.size(); k ++) {
                        for (int j = 0; j < b[0].size(); j ++) {
                                c[i][j] = ((c[i][j] + a[i][k] * b[k][j])) % 2;
                        }
                }
        }
        return c;
}
Matrix Pow(Matrix a, long long n) { //a^n, square
        Matrix b(a.size(), vector<Type> (a.size()));
        for (int i = 0; i < a.size(); i ++) {
                b[i][i] = 1;
        }
        while (n > 0) {
                if (n & 1) b = Mul(b, a);
                a = Mul(a, a);
                n >>= 1;
        }
        return b;
}
void PrintMatrix(const Matrix &a) {
        int h = a.size(), w = a[0].size();
        for (int i = 0; i < h; i ++) {
                for (int j = 0; j < w; j ++) {
                        cout << a[i][j] << ' ';
                }
                cout << endl;
        }
}
int main() {
        int n;
        scanf("%d", &n);
        Matrix g(n, vector<int> (n));
        for (int i = 0; i < n; i ++) {
                for (int j = 0; j < n; j ++) {
                        scanf("%d", &g[i][j]);
                }
        }
        Matrix v(n, vector<int> (1));
        for (int i = 0; i < n; i ++) scanf("%d", &v[i][0]);
        long long t;
        scanf("%lld", &t);
        Matrix inv(n, vector<int> (n));
        if (Inv(g, inv)) {
                inv = Pow(inv, t);
                auto ans = Mul(inv, v);
                for (int i = 0; i < n; i ++) cout << ans[i][0] << (i == n - 1 ? '\n' : ' ');
        } else {
                auto g_t = Pow(g, t);
                Matrix g_tv(n, vector<int> (n + 1));
                for (int i = 0; i < n; i ++) {
                        for (int j = 0; j < n; j ++) {
                                g_tv[i][j] = g_t[i][j];
                        }
                }
                for (int i = 0; i < n; i ++) g_tv[i][n] = v[i][0];
                if (GetRank(g_tv) == GetRank(g_t)) {
                        cout << "ambiguous" << endl;
                } else {
                        cout << "none" << endl;
                }
        }
        return 0;
}