AtCoder Regular Contest 054 C - 鯛焼き

問題

　タイヤと木がそれぞれ個あり、各タイヤと木の組について相性が良いか悪いかが決まっている。相性の良いタイヤと木のみを組み合わせて全てのタイヤと木を組み合わせる方法が何通りあるか、その偶奇を求めよ。

解法

　行列式を計算して2で割った余りを求める。詳細は解説なり各種ブログで。

反省

　3時間14分(11WA)でAC。久しぶりに地獄という感じだった。

　考察は1時間で諦めた。完全マッチングの組み合わせ数って数えられるのかなとググってNP困難とか書いてあるのを見つけたくらい。行列として見てどうにかするっていうのも一瞬考えたけど行列式求めるだけで良いっていうのはわからなかった。

　大変だったのは解説を読んでから。行列式が求められない。後でわかったことは、整数行列の行列式の値は整数にはなるが、自分の実装では途中で小数まで考えないといけないはずの計算が発生していたので整数型では答えが合わなくなるということだった。ACしたときは適当にxor取っている他の人の実装パクったら通ったという感じ。

　整数型で計算途中にmodも取らず通している提出もあるので実装の問題なんだろう。自分の提出をdoubleにしても誤差でめちゃくちゃになっているようなので、この計算方法はダメらしい。整数型でmod2における逆元を計算するか、なぜか誤差の出ない上の方法でやるしかないようだ。

　テストケースが非公開なのはやはり地獄。あと数回分くらいの我慢だ……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

//n×n行列の行列式を求める
ll determinant(vector<vector<ll>> M) {
    const ll n = M.size();
    ll result = 1;
    for (ll i = 0; i < n; i++) {
        if (M[i][i] == 0) {
            //対角成分が0だった場合はその列の値が0でない行と交換する
            for (ll ni = i + 1; ni < n; ni++) {
                if (M[ni][i] != 0) {
                    swap(M[i], M[ni]);
                    //result = -result;
                    break;
                }
            }
        }

        if (M[i][i] == 0) {
            return 0;
        }

        for (ll ni = i + 1; ni < n; ni++) {
            //ni行のi列目を全て0にする
            //ll r = M[ni][i] / M[i][i];

            for (ll j = i + 1; j < n; j++) {
                //M[ni][j] -= r * M[i][j];
                M[ni][j] ^= M[ni][i] * M[i][j];
            }
        }

        //行列式は対角成分の積
        result *= M[i][i];
    }
    return result;
}

int main() {
    ll N;
    cin >> N;
    vector<vector<ll>> M(N, vector<ll>(N));
    for (ll i = 0; i < N; i++) {
        string S;
        cin >> S;
        for (ll j = 0; j < N; j++) {
            M[i][j] = S[j] - '0';
        }
    }

    cout << (determinant(M) % 2 == 0 ? "Even" : "Odd") << endl;
}