結果
| 問題 | No.1773 Love Triangle |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-05-21 03:47:55 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,103 bytes |
| 記録 | |
| コンパイル時間 | 2,481 ms |
| コンパイル使用メモリ | 106,336 KB |
| 実行使用メモリ | 66,824 KB |
| 最終ジャッジ日時 | 2026-05-21 03:48:22 |
| 合計ジャッジ時間 | 26,016 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 39 WA * 51 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.nio.file.Files;
import java.nio.file.LinkOption;
import java.nio.file.OpenOption;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.file.attribute.FileAttribute;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Optional;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.DoubleUnaryOperator;
import java.util.function.IntBinaryOperator;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.LongToDoubleFunction;
import java.util.function.Predicate;
import java.util.function.Supplier;
import java.util.function.ToIntFunction;
import java.util.random.RandomGenerator;
import java.util.regex.Pattern;
import java.util.stream.IntStream;
import java.util.stream.Stream;
/**
* 線形マトロイドパリティ問題を解くクラス。
* 与えられたベクトルのペア集合から、線形独立なものの和集合のサイズが最大となるようなペアの集合を求める。
*
* アルゴリズムの概要:
* 1. 各ペア (b_i, c_i) に対してランダムな値 x_i を割り当て、歪対称行列 Y = Σ x_i (b_i c_i^T - c_i b_i^T) を作成する。
* 2. Y のランクの半分が、最大マッチングサイズ（選べるペアの最大数）に対応する。
* 3. 辞書順最小の解を求めるため、各ペアを順番に取り除いてみて、ランクが減らなければそのペアを除去する。
* 4. 行列の更新には Sherman-Morrison の公式を用いた逆行列の動的更新を行い、計算量を抑える。
*
* 参考:
* [1] H. Y. Cheung, L. C. Lau, K. M. Leung,
* "Algebraic Algorithms for Linear Matroid Parity Problems,"
* ACM Transactions on Algorithms, 10(3), 1-26, 2014.
*/
class LinearMatroidParity {
/**
* ベクトルのペアを表すレコード。
*/
public record VectorPair(long[] b, long[] c) {}
private LinearMatroidParity() {
}
/**
* 線形マトロイドパリティ問題の最大マッチングサイズを返す。
* 成功確率は少なくとも 1 - r/mod。
* 計算量: O(r^2(m + r)) (r: 次数, m: ペア数)
*
* @param bcs
* ベクトルのペアの配列
* @param mod
* 法（素数）
* @return 最大マッチングサイズ（選べるペアの最大数）
*/
public static int size(VectorPair[] bcs, long mod) {
return size(bcs, mod, System.currentTimeMillis());
}
/**
* 線形マトロイドパリティ問題の最大マッチングサイズを返す。
* 成功確率は少なくとも 1 - r/mod。
* 計算量: O(r^2(m + r)) (r: 次数, m: ペア数)
*
* @param bcs
* ベクトルのペアの配列
* @param mod
* 法（素数）
* @param seed
* 乱数の種
* @return 最大マッチングサイズ（選べるペアの最大数）
*/
public static int size(VectorPair[] bcs, long mod, long seed) {
if (bcs.length == 0) {
return 0;
}
int r = bcs[0].b().length;
// 歪対称行列 Y = Σ x_i (b_i c_i^T - c_i b_i^T) を構築
long[][] mat = new long[r][r];
Random rnd = new Random(seed);
for (VectorPair bc : bcs) {
long x = rnd.nextLong(mod);
long[] b = bc.b();
long[] c = bc.c();
for (int i = 0; i < r; i++) {
if ((b[i] == 0) && (c[i] == 0)) {
continue;
}
for (int j = 0; j < r; j++) {
// b_i * c_j^T - c_i * b_j^T
long val = (x * ((((b[i] * c[j]) % mod) - ((b[j] * c[i]) % mod)) + mod)) % mod;
mat[i][j] = (mat[i][j] + val) % mod;
}
}
}
// 歪対称行列のランクは常に偶数であり、その半分が最大パリティマッチングのサイズになる
return MatrixUtils.modRank(mat, mod) / 2;
}
}
class FastScanner {
private static FastScanner instance = null;
private final InputStream in = System.in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int buflen = 0;
private FastScanner() {
}
public static FastScanner getInstance() {
if (instance == null) {
instance = new FastScanner();
}
return instance;
}
private boolean hasNextByte() {
if (this.ptr < this.buflen) {
return true;
}
this.ptr = 0;
try {
this.buflen = this.in.read(this.buffer);
} catch (IOException e) {
e.printStackTrace();
}
return this.buflen > 0;
}
private int readByte() {
if (hasNextByte()) {
return this.buffer[this.ptr++];
} else {
return -1;
}
}
private boolean isPrintableChar(int c) {
return (33 <= c) && (c <= 126);
}
public boolean hasNext() {
while (hasNextByte() && (!isPrintableChar(this.buffer[this.ptr]))) {
this.ptr++;
}
return hasNextByte();
}
public long nextLong() {
if (!hasNext()) {
throw new NoSuchElementException();
}
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
while ((b >= '0') && (b <= '9')) {
// n = n * 10 + (b - '0');
n = ((n << 1) + (n << 3)) + (b - '0');
b = readByte();
}
return minus ? -n : n;
}
public int nextInt() {
return ((int) (nextLong()));
}
}
class MergeFiles {}
class ArrayUtils {
public static void swap(long[] A, long[] B) {
if (A.length != B.length) {
throw new AssertionError();
}
for (int i = 0; i < A.length; i++) {
long tmp = A[i];
A[i] = B[i];
B[i] = tmp;
}
}
public static long[][] copy(long[][] a) {
long[][] b = new long[a.length][];
Arrays.setAll(b, i -> Arrays.copyOf(a[i], a[i].length));
return b;
}
}
class MyPrintWriter extends PrintWriter {
private static MyPrintWriter instance = null;
private MyPrintWriter() {
super(System.out);
}
public static MyPrintWriter getInstance() {
if (instance == null) {
instance = new MyPrintWriter();
}
return instance;
}
}
class MatrixUtils {
/**
* 与えられた行列 {@code a} を法 {@code mod} 上で掃き出し法により
* 既約行階段形（Reduced Row Echelon Form, RREF）に変換した行列を返す。
* <ul>
* <li>零でない各行の先頭の非零成分、すなわちピボットは {@code 1} である。</li>
* <li>ピボットを含む列では、ピボット以外の成分はすべて {@code 0} である。</li>
* <li>ピボット列の位置は、下の行へ行くほど真に右へ進む。</li>
* <li>零行が存在する場合、それらは非零行の下に現れる。</li>
* </ul>
*
* @param a
* 法 {@code mod} 上の行列
* @param mod
* 計算に用いる法(素数)
* @return 行列 {@code a} の既約行階段形を表す新しい行列
* @see */
public static long[][] reducedRowEchelonFormOnFp(long[][] a, long mod) {
// https://atcoder.jp/contests/abc366/submissions/72615935 (mod 2, 正方行列)
var b = ArrayUtils.copy(a);
int n = b.length;
if (n == 0) {
return b;
}
int m = b[0].length;
int rank = 0;
for (int i = 0; (i < m) && (rank < n); ++i) {
{
int j = rank;
while ((j < n) && (b[j][i] == 0)) {
++j;
}
if (j == n) {
continue;
}
ArrayUtils.swap(b[rank], b[j]);
}
long inv = MathUtils.modInv(b[rank][i], mod);
for (int k = i; k < m; k++) {
b[rank][k] = (b[rank][k] * inv) % mod;
}
for (int j = 0; j < n; ++j) {
if ((rank == j) || (b[j][i] == 0)) {
continue;
}
long factor = b[j][i];
for (int k = i; k < m; k++) {
b[j][k] = ((b[j][k] - ((factor * b[rank][k]) % mod)) + mod) % mod;
}
}
++rank;
}
return b;
}
public static int modRank(long[][] a, long mod) {
// https://judge.yosupo.jp/submission/370813
if ((a.length == 0) || (a[0].length == 0)) {
return 0;
}
long[][] b = reducedRowEchelonFormOnFp(a, mod);
int rank = 0;
for (int i = 0; i < b.length; ++i) {
for (int j = 0; j < b[0].length; ++j) {
if (b[i][j] == 1) {
++rank;
break;
}
}
}
return rank;
}
}
class MathUtils {
/**
* 拡張ユークリッドの互除法で逆元を求める。
*
* @param a
* @param mod
* @return */
public static long modInv(long a, long mod) {
a = ((a % mod) + mod) % mod;
long[] f0 = new long[]{ 1, 0, mod };
long[] f1 = new long[]{ 0, 1, a };
while (f1[2] != 0) {
long q = f0[2] / f1[2];
for (int i = 0; i < 3; i++) {
f0[i] -= q * f1[i];
}
ArrayUtils.swap(f0, f1);
}
return f0[1] < 0 ? mod + f0[1] : f0[1];
}
}
public class Main {
static MyPrintWriter pw = MyPrintWriter.getInstance();
static FastScanner sc = FastScanner.getInstance();
public static void main(String[] args) throws IOException {
Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
new Main().run();
pw.flush();
}
void run() {
int N = sc.nextInt();
int M = sc.nextInt();
int[][] T = new int[M][3];
for (int i = 0; i < M; i++) {
for (int j = 0; j < 3; j++) {
T[i][j] = sc.nextInt() - 1;
}
}
long mod = 998244353;
LinearMatroidParity.VectorPair[] pairs = new LinearMatroidParity.VectorPair[M];
for (int i = 0; i < M; i++) {
long[] u = new long[N];
long[] v = new long[N];
u[T[i][0]] = u[T[i][1]] = 1;
v[T[i][1]] = v[T[i][2]] = 1;
pairs[i] = new LinearMatroidParity.VectorPair(u, v);
}
pw.println(LinearMatroidParity.size(pairs, mod));
}
}
// --- Original Code ---
// import java.io.IOException;
// import java.util.Arrays;
//
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.graph.Graph;
// import library.util.graph.LinearMatroidParity;
//
// public class Main {
// static MyPrintWriter pw=MyPrintWriter.getInstance();
// static FastScanner sc=FastScanner.getInstance();
//
// public static void main(String[] args) throws IOException {
// new Main().run();
// pw.flush();
// MergeFiles.export();
// }
//
// void run() {
//
// int N=sc.nextInt();
// int M=sc.nextInt();
// int[][]T=new int[M][3];
// for (int i = 0; i < M; i++) {
// for (int j = 0; j < 3; j++) {
// T[i][j]=sc.nextInt()-1;
// }
// }
// long mod=998244353;
// LinearMatroidParity.VectorPair[] pairs=new LinearMatroidParity.VectorPair[M];
// for (int i = 0; i < M; i++) {
// long[]u=new long[N];
// long[]v=new long[N];
// u[T[i][0]]=u[T[i][1]]=1;
// v[T[i][1]]=v[T[i][2]]=1;
// pairs[i] = new LinearMatroidParity.VectorPair(u, v);
// }
// pw.println(LinearMatroidParity.size(pairs, mod));
// }
//
//
//
// void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}
// }