#1196553 (C++23) No.1773 Love Triangle

提出ソース
結果

問題	No.1773 Love Triangle
コンテスト
ユーザー	kwm_t
提出日時	2026-11-02 12:35:15
言語	C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) コンパイル: `g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	133 ms / 2,000 ms
	+ 320µs
コード長	10,078 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	5,690 ms
コンパイル使用メモリ	394,020 KB
実行使用メモリ	9,904 KB
最終ジャッジ日時	2026-11-02 12:35:58
合計ジャッジ時間	15,422 ms
ジャッジサーバーID （参考情報）	judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 88
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
using mint = modint998244353;
const int mod = 998244353;
const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
/**
 * @file xor_shift.hpp
 * @brief Xorshift 乱数生成器
 * @author kwm_t
 * @see https://github.com/kwm-t/cp-library/blob/main/utility/xor_shift.hpp
 */
#ifndef KWM_T_UTILITY_XORSHIFT_HPP
#define KWM_T_UTILITY_XORSHIFT_HPP

#include <cstdint>
#include <limits>

namespace kwm_t::utility {

/**
 * @brief Xorshift 乱数生成器（軽量・高速）
 *
 * 典型用途:
 *   - 競プロの乱択
 *   - テストケース生成
 *
 * 計算量:
 *   O(1)
 *
 * 注意:
 *   - 暗号用途には不適
 *   - seed=0 は避ける
 *
 * verified:
 *   - 競技プログラミング用途
 */
class Xorshift {
public:
	using result_type = uint32_t;

	explicit Xorshift(uint64_t seed = 1) : x(seed ? seed : 1) {}

	static constexpr result_type min() {
		return std::numeric_limits<result_type>::min();
	}

	static constexpr result_type max() {
		return std::numeric_limits<result_type>::max();
	}

	/**
	 * @brief [0, 2^32) の乱数
	 */
	result_type operator()() {
		x ^= x << 9;
		x ^= x >> 7;
		return static_cast<result_type>(x);
	}

	/**
	 * @brief [0, m) の整数乱数
	 */
	int64_t operator()(int64_t m) {
		return (static_cast<uint64_t>((*this)()) * m) >> 32;
	}

	/**
	 * @brief [0, 1) の実数乱数
	 */
	double uniform() {
		return static_cast<double>((*this)()) / (static_cast<uint64_t>(1) << 32);
	}

private:
	uint64_t x;
};

} // namespace kwm_t::utility

#endif // KWM_T_UTILITY_XORSHIFT_HPP

/**
 * @file gauss_jordan.hpp
 * @brief Gauss-Jordan 消去法
 * @author kwm_t
 * @see https://github.com/kwm-t/cp-library/blob/main/math/matrix/gauss_jordan.hpp
 */
#ifndef KWM_T_MATH_MATRIX_GAUSS_JORDAN_HPP
#define KWM_T_MATH_MATRIX_GAUSS_JORDAN_HPP

#include <vector>
#include <utility>

namespace kwm_t::math::matrix {

/**
 * @brief Gauss-Jordan elimination（掃き出し法）
 *
 * Ax = b を解く / ランク / kernel を求める
 *
 * 要件:
 *   - T は体（+,-,*,/ が使える）
 *   - 0 判定ができる（== 0）
 *
 * verified:
 *   https://judge.yosupo.jp/submission/367294
 */
template <class T>
class GaussJordan {
public:
	GaussJordan(std::vector<std::vector<T>> A,
		std::vector<T> b)
		: A(std::move(A)), b(std::move(b)) {}

	/**
	 * @brief 掃き出し（内部状態を書き換える）
	 * @return rank
	 */
	int sweep() {
		int n = A.size();
		int m = A[0].size();
		rank = 0;

		for (int col = 0; col < m; ++col) {
			int pivot = -1;
			for (int row = rank; row < n; ++row) {
				if (A[row][col] != T(0)) {
					pivot = row;
					break;
				}
			}
			if (pivot == -1) continue;

			std::swap(A[rank], A[pivot]);
			std::swap(b[rank], b[pivot]);

			T inv = T(1) / A[rank][col];

			for (int j = col; j < m; ++j) A[rank][j] *= inv;
			b[rank] *= inv;

			for (int row = 0; row < n; ++row) {
				if (row == rank) continue;
				if (A[row][col] == T(0)) continue;

				T factor = A[row][col];
				for (int j = col; j < m; ++j) {
					A[row][j] -= factor * A[rank][j];
				}
				b[row] -= factor * b[rank];
			}

			++rank;
		}
		return rank;
	}

	/**
	 * @brief 解を1つ求める（存在すれば）
	 */
	bool solve(std::vector<T>& x) {
		int n = A.size();
		int m = A[0].size();

		sweep();
		x.assign(m, T(0));

		for (int i = rank; i < n; ++i) {
			if (b[i] != T(0)) return false;
		}

		for (int i = 0; i < rank; ++i) {
			for (int j = 0; j < m; ++j) {
				if (A[i][j] != T(0)) {
					x[j] = b[i];
					break;
				}
			}
		}
		return true;
	}

	/**
	 * @brief kernel（解空間の基底）
	 */
	std::vector<std::vector<T>> kernel() {
		int n = A.size();
		int m = A[0].size();

		sweep();

		std::vector<int> pivot_col(m, -1);
		int row = 0;

		for (int col = 0; col < m && row < rank; ++col) {
			if (A[row][col] == T(1)) {
				pivot_col[col] = row;
				++row;
			}
		}

		std::vector<std::vector<T>> res;

		for (int col = 0; col < m; ++col) {
			if (pivot_col[col] != -1) continue;

			std::vector<T> v(m, T(0));
			v[col] = T(1);

			for (int c = 0; c < m; ++c) {
				if (pivot_col[c] != -1) {
					v[c] = -A[pivot_col[c]][col];
				}
			}
			res.push_back(v);
		}

		return res;
	}

	int rank = 0;

private:
	std::vector<std::vector<T>> A;
	std::vector<T> b;
};

} // namespace kwm_t::math::matrix

#endif


/**
 * @file linear_matroid_parity.hpp
 * @brief 線形マトロイドパリティ
 * @author kwm_t
 * @see https://github.com/kwm-t/cp-library
 */
#ifndef KWM_T_MATH_MATROID_LINEAR_MATROID_PARITY_HPP
#define KWM_T_MATH_MATROID_LINEAR_MATROID_PARITY_HPP

#include <algorithm>
#include <utility>
#include <vector>

 //#include "../matrix/gauss_jordan.hpp"
 //#include "../../utility/xorshift.hpp"

namespace kwm_t::math::matroid {

namespace internal {

/**
 * @brief 0 でないランダムな Mint を生成する
 */
template <class Mint>
Mint random_nonzero(kwm_t::utility::Xorshift& rnd) {
	Mint x = Mint(rnd());
	while (x == Mint(0)) {
		x = Mint(rnd());
	}
	return x;
}

/**
 * @brief 行列のランクを求める
 */
template <class Mint>
int rank(std::vector<std::vector<Mint>> mat) {
	int n = static_cast<int>(mat.size());
	if (n == 0) return 0;

	std::vector<Mint> b(n, Mint(0));
	kwm_t::math::matrix::GaussJordan<Mint> gj(
		std::move(mat), std::move(b)
	);
	return gj.sweep();
}

/**
 * @brief 2 本のベクトルの外積による歪対称行列への加算
 */
template <class Mint>
void add_pair(
	std::vector<std::vector<Mint>>& mat,
	const std::vector<std::pair<int, Mint>>& p,
	const std::vector<std::pair<int, Mint>>& q
) {
	for (const auto& [i, x] : p) {
		for (const auto& [j, y] : q) {
			mat[i][j] += x * y;
			mat[j][i] -= x * y;
		}
	}
}

}  // namespace internal

/**
 * @brief 線形マトロイドパリティ（dense）
 *
 * 各ペアは 2 本のベクトル (p, q) からなる。
 * 各ベクトルの非ゼロ座標に独立なランダム値を割り当て、
 * 線形独立なペアの最大数を確率的に求める。
 *
 * 入力の T は座標が 0 か非 0 かを判定するためだけに使う。
 * 実際のベクトルの値としては使用しない。
 *
 * @tparam Mint 有限体の型
 * @tparam T 入力ベクトルの要素型
 * @param pairs ベクトルのペア
 * @param rnd 乱数生成器
 * @return 最大ペア数の確率的な推定値
 *
 * 各ベクトルの長さはすべて等しいこと。
 */
template <class Mint, class T>
int dense(
	const std::vector<std::pair<std::vector<T>, std::vector<T>>>& pairs,
	kwm_t::utility::Xorshift& rnd,
	int repeat = 2
) {
	int n = 0;
	if (!pairs.empty()) {
		n = static_cast<int>(pairs[0].first.size());
	}

	int ans = 0;
	for (int rep = 0; rep < repeat; ++rep) {
		std::vector<std::vector<Mint>> mat(n, std::vector<Mint>(n));

		for (const auto& [p, q] : pairs) {
			std::vector<std::pair<int, Mint>> x, y;

			for (int i = 0; i < n; ++i) {
				if (p[i] != T(0)) {
					x.emplace_back(i, p[i] * internal::random_nonzero<Mint>(rnd));
				}
				if (q[i] != T(0)) {
					y.emplace_back(i, q[i] * internal::random_nonzero<Mint>(rnd));
				}
			}

			internal::add_pair(mat, x, y);
		}

		ans = std::max(ans, internal::rank(std::move(mat)) / 2);
	}

	return ans;
}

/**
 * @brief 線形マトロイドパリティ（sparse）
 *
 * 各ベクトルは (座標, 値) の組の列で表す。
 * 値が T(0) でない座標に独立なランダム値を割り当てる。
 *
 * 入力の T は座標が 0 か非 0 かを判定するためだけに使う。
 * 実際のベクトルの値としては使用しない。
 *
 * @tparam Mint 有限体の型
 * @tparam T 入力ベクトルの要素型
 * @param n ベクトルの次元
 * @param pairs ベクトルのペア
 * @param rnd 乱数生成器
 * @return 最大ペア数の確率的な推定値
 *
 * 各ベクトル内で座標は重複せず、0 <= 座標 < n を満たすこと。
 */
template <class Mint, class T>
int sparse(
	int n,
	const std::vector<
	std::pair<
	std::vector<std::pair<int, T>>,
	std::vector<std::pair<int, T>>
	>
	>& pairs,
	kwm_t::utility::Xorshift& rnd,
	int repeat = 2
) {
	int ans = 0;
	for (int rep = 0; rep < repeat; ++rep) {
		std::vector<std::vector<Mint>> mat(n, std::vector<Mint>(n));

		for (const auto& [p, q] : pairs) {
			std::vector<std::pair<int, Mint>> x, y;
			x.reserve(p.size());
			y.reserve(q.size());

			auto r = internal::random_nonzero<Mint>(rnd);
			for (const auto& [i, val] : p) {
				if (val != T(0)) {
					x.emplace_back(i, val * r);
				}
			}
			for (const auto& [i, val] : q) {
				if (val != T(0)) {
					y.emplace_back(i, val * r);
				}
			}

			internal::add_pair(mat, x, y);
		}
		ans = std::max(ans, internal::rank(std::move(mat)) / 2);
	}

	return ans;
}

}  // namespace kwm_t::math::matroid

#endif


void solve() {
	int n, m; cin >> n >> m;
	kwm_t::utility::Xorshift rnd;
	{
		vector<pair<vector<pair<int, int>>, vector<pair<int, int>>>> pairs;
		rep(i, m) {
			int u, v, w; cin >> u >> v >> w;
			u--, v--, w--;
			pair<vector<pair<int, int>>, vector<pair<int, int>>> tmp;
			tmp.first.emplace_back(u, 1);
			tmp.first.emplace_back(w, -1);
			tmp.second.emplace_back(v, 1);
			tmp.second.emplace_back(w, -1);
			pairs.push_back(tmp);
		}
		int ans = kwm_t::math::matroid::sparse<mint>(n, pairs, rnd);
		cout << ans << endl;
	}
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t = 1;
	while (t--)solve();
	return 0;
}
yukicoder

結果

ソースコード
