#806718 (Java21) No.2136 Dice Calendar?

• 問題: No.2136 Dice Calendar?
• ユーザー: CuriousFairy315
• 提出日時: 2022-10-14 14:22:51
• 言語: Java21 (openjdk 21)
• 結果: TLE
• 実行時間: -
• コード長: 19,440 bytes
• コンパイル時間: 3,162 ms
• コンパイル使用メモリ: 85,328 KB
• 実行使用メモリ: 331,792 KB
• 最終ジャッジ日時: 2023-09-08 19:42:12
• 合計ジャッジ時間: 31,855 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	90 ms; 53,044 KB
testcase_01	AC	91 ms; 52,624 KB
testcase_02	AC	247 ms; 61,132 KB
testcase_03	AC	90 ms; 52,972 KB
testcase_04	AC	91 ms; 54,096 KB
testcase_05	AC	155 ms; 55,008 KB
testcase_06	AC	139 ms; 54,852 KB
testcase_07	AC	195 ms; 59,264 KB
testcase_08	AC	213 ms; 59,764 KB
testcase_09	AC	274 ms; 61,028 KB
testcase_10	AC	299 ms; 59,604 KB
testcase_11	AC	507 ms; 63,420 KB
testcase_12	AC	515 ms; 73,292 KB
testcase_13	AC	482 ms; 65,064 KB
testcase_14	AC	563 ms; 65,040 KB
testcase_15	AC	1,912 ms; 122,028 KB
testcase_16	AC	1,825 ms; 123,816 KB
testcase_17	AC	3,098 ms; 168,660 KB
testcase_18	AC	2,197 ms; 166,628 KB
testcase_19	AC	4,735 ms; 213,276 KB
testcase_20	AC	3,760 ms; 206,688 KB
testcase_21	TLE	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-

ソースコード

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashSet;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		InputChecker ic = new InputChecker(System.in);
		java.io.PrintWriter out = new java.io.PrintWriter(System.out);
		solve(ic, out);
		out.flush();
	}

	public void solve(InputChecker ic, java.io.PrintWriter out) {
		int N = ic.nextInt(1, 20);
		ic.readNewLine();
		int[][] S = new int[N][6];
		final int KIND = 9;
		for (int i = 0; i < N; ++i) {
			S[i][0] = ic.nextInt(1, KIND) - 1;
			for (int j = 1; j < 6; ++j) {
				ic.nextChar(' ');
				S[i][j] = ic.nextInt(1, KIND) - 1;
			}
			ic.readNewLine();
		}
		ic.checkEOF();
		long time = System.currentTimeMillis(), allTime = time;

		final int MEET_IN_THE_MIDDLE = 2;
		int lastChoose = Math.min(N, MEET_IN_THE_MIDDLE);

		ArrayList<int[]> lastCreate = new ArrayList<>();
		{
			HashSet<Long> val = new HashSet<>();
			enumerate(0, new int[KIND], val, Arrays.copyOfRange(S, N - lastChoose, N));
			for (long v : val) {
				int[] put = new int[lastChoose];
				for (int i = 0;i < lastChoose;++ i) {
					put[i] = (int)(v & 15);
					v >>= 4;
				}
				lastCreate.add(put);
			}
		}
		N -= lastChoose;

		long[] factorial = new long[21];
		factorial[0] = 1;
		for (int i = 1; i < factorial.length; ++i) factorial[i] = factorial[i - 1] * i;
		int[] max = new int[KIND];
		for (int[] i : S) for (int j : i) ++max[j];
		int[] remain = new int[KIND];
		for (int i = KIND - 2; i >= 0; --i) remain[i] = remain[i + 1] + max[i + 1];
		final int MOD = 998_244_353;

		ArrayList<int[]> divide = new ArrayList<>();
		for (int s = (1 << KIND - 1) - 1; s < 1 << N + KIND - 1;) {
			// この時点のsは条件を満たした整数
			divide.add(expansion(s, N, KIND));

			int t = s | s - 1;
			s = t + 1 | (~t & -~t) - 1 >> deBrujin32[(s & -s) * 0x077CB531 >>> 27] + 1;
		}
		System.err.println("partition: " + (System.currentTimeMillis() - time) + " ms (count:" + divide.size() + ")");
		time = System.currentTimeMillis();
		int source = N + KIND, sink = source + 1;
		MaxFlow flow = new MaxFlow(sink + 1);
		for (int i = 0; i < N; ++i) {
			flow.addEdge(source, i, 1);
			for (int j = 0; j < 6; ++j) {
				flow.addEdge(i, N + S[i][j], 1);
			}
		}
		int[] sinkEdge = new int[KIND];
		for (int i = 0; i < KIND; ++i) sinkEdge[i] = flow.addEdge(N + i, sink, 0);

		long flowSum = 0;
		ArrayList<int[]> goodPartition = new ArrayList<>(divide.size());
		for (int[] partition : divide) {
			for (int i = 0; i < KIND; ++i) {
				MaxFlow.CapEdge edge = flow.getEdge(sinkEdge[i]);
				if (partition[i] >= edge.flow) { // 容量の方が大きい
					flow.changeEdge(sinkEdge[i], partition[i], edge.flow);
				}
			}
			for (int i = 0; i < KIND; ++i) {
				MaxFlow.CapEdge edge = flow.getEdge(sinkEdge[i]);
				if (partition[i] < edge.flow) { // 流し直し
					long back = edge.flow - partition[i]; // 溢れる分
					flow.changeEdge(sinkEdge[i], 0, 0);
					back -= flow.flow(edge.from, edge.to, back);
					if (back != 0) {
						flow.flow(edge.from, source, back);
						flow.flow(edge.to, sink, back);
					}
					flow.changeEdge(sinkEdge[i], partition[i], partition[i]);
					flowSum -= back;
				}
			}
			if (flowSum != N) flowSum += flow.flow(source, sink, N - flowSum);
			if (flowSum != N) continue;
			goodPartition.add(partition);
		}
		System.err.println("flow: " + (System.currentTimeMillis() - time) + " ms (" + "create:" + goodPartition.size() + ")");
		time = System.currentTimeMillis();
		BitSet createPartition = new BitSet(1 << N + lastChoose + KIND - 1);
		int[] sb = new int[KIND];
		for (int[] partition : goodPartition) {
			int bit = compress(partition, N);
			for (int i = KIND - 2;i >= 0;-- i) sb[i] = sb[i + 1] + partition[i + 1] + 1;

			for (int[] add : lastCreate) {
				int next = bit;
				for (int i : add) {
					int mask = next & (1 << sb[i]) - 1;
					next = (next & ~mask) << 1 | next & mask;
				}
				createPartition.set(next);
			}
		}
		System.err.println("merge: " + (System.currentTimeMillis() - time) + " ms");
		time = System.currentTimeMillis();
		long ans = 0;
		for (int partition = createPartition.nextSetBit(0);partition >= 0;partition = createPartition.nextSetBit(partition + 1)) {
			long multichoose = factorial[N + lastChoose];
			for (int i : expansion(partition, N + lastChoose, KIND)) multichoose /= factorial[i];
			ans += multichoose % MOD;
		}
		ans %= MOD;
		out.println(ans);
		System.err.println("multichoose: " + (System.currentTimeMillis() - time) + " ms");
		time = System.currentTimeMillis();
		System.err.println("all: " + (System.currentTimeMillis() - allTime) + " ms");
	}

	public static void enumerate(int number, int[] create, HashSet<Long> set, int[]... S) {
		if (number == S.length) {
			long put = 0;
			for (int i = create.length - 1;i >= 0;-- i) {
				for (int j = 0;j < create[i];++ j) {
					put <<= 4;
					put |= i;
				}
			}
			set.add(put);
			return;
		}
		for (int i : S[number]) {
			++ create[i];
			enumerate(number + 1, create, set, S);
			-- create[i];
		}
	}


	static final int[] deBrujin32 = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7,
			26, 12, 18, 6, 11, 5, 10, 9 };

	public static int compress(int[] partition, int N) {
		int put = 0;
		for (int i : partition) {
			put <<= 1;
			put |= 1;
			put <<= i;
		}
		return put;
	}

	public static int[] expansion(int partition, int N, int KIND) {
		int[] put = new int[KIND];
		int lastCtz = 0;
		for (int i = put.length - 1;i != 0;-- i) {
			put[i] = deBrujin32[(partition & -partition) * 0x077CB531 >>> 27];
			partition ^= 1 << put[i];
			put[i] -= lastCtz;
			lastCtz += put[i] + 1;
		}
		put[0] = N + KIND - 1 - lastCtz;
		return put;
	}

	public static int exponent10(int n, int e) {
		return n * pow(10, e);
	}

	public static long exponent10L(int n, int e) {
		return n * pow(10L, e);
	}

	public static int pow(int a, int b) {
		int ans = 1;
		for (int mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
		return ans;
	}

	public static long pow(long a, long b) {
		long ans = 1;
		for (long mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
		return ans;
	}

	public static class CharSet {
		private final BitSet set = new BitSet(256);

		public void add(char... c) {
			for (char i : c) set.set(i);
		}

		public void add(CharSet... s) {
			for (CharSet i : s) set.or(i.set);
		}

		public boolean contains(char... c) {
			for (char i : c) if (!set.get(i)) return false;
			return true;
		}

		public boolean contains(String s) {
			return contains(s.toCharArray());
		}

		private static final class Chars extends CharSet {
			public Chars(char... c) {
				super.add(c);
			}

			public Chars(CharSet... s) {
				super.add(s);
			}

			@Override
			public void add(char... c) {
				throw new UnsupportedOperationException();
			}

			@Override
			public void add(CharSet... s) {
				throw new UnsupportedOperationException();
			}
		}

		public static final CharSet NUMBER = new Chars('0', '1', '2', '3', '4', '5', '6', '7', '8', '9');
		public static final CharSet LOWER = new Chars('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
				'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z');
		public static final CharSet UPPER = new Chars('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
				'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z');
		public static final CharSet ALPHABET = new Chars(LOWER, UPPER);

	}

	public static class InputChecker {
		private InputStream in;
		private final byte[] buffer = new byte[1024];
		private final byte[] undo = new byte[1024];
		private int undoSize = 0;
		private int read = 0;
		private int length = 0;

		public InputChecker(InputStream in) {
			this.in = in;
		}

		public final void setInputStream(InputStream in) { this.in = in; }

		public final void setInputStream(File in) {
			try {
				this.in = new FileInputStream(in);
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		private boolean hasNextByte() {
			if (undoSize > 0) return true;
			if (read < length) return true;
			read = 0;
			try {
				length = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			return length > 0;
		}

		private byte readByte() {
			if (hasNextByte()) return undoSize > 0 ? undo[--undoSize] : buffer[read++];
			throw new NoSuchElementException();
		}

		private void undo(byte b) {
			undo[undoSize++] = b;
		}

		private void undo(char c) {
			if ((c & 0xFF80) == 0) {
				undo((byte) c);
				return;
			}
			undo((byte) (c & 0x3F | 0x80));
			if ((c & 0xF800) == 0) {
				undo((byte) (c >> 6 & 0x1F | 0xC0));
			} else {
				undo((byte) (c >> 6 & 0x3F | 0x80));
				undo((byte) (c >> 12 | 0xE0));
			}
		}

		public final boolean hasNext() {
			return hasNextByte();
		}

		public final char nextChar() {
			byte b = readByte();
			if ((b & 0x80) == 0) return (char) b;
			if ((b & 0x20) == 0) return (char) ((b & 0x1F) << 6 | readByte() & 0x3F);
			return (char) ((b & 0xF) << 12 | (readByte() & 0x3F) << 6 | readByte() & 0x3F);
		}

		public final char nextChar(char estimate) {
			char c = nextChar();
			if (estimate == c) return estimate;
			undo(c);
			throw new AssertionError();
		}

		public final char nextChar(CharSet estimate) {
			char c = nextChar();
			if (estimate.contains(c)) return c;
			undo(c);
			throw new AssertionError();
		}

		public final void readNewLine() {
			char c = nextChar();
			if (c == '\r') {
				c = nextChar();
				if (c != '\n') undo(c);
				return;
			} else if (c == '\n') return;
			undo(c);
			throw new AssertionError();
		}

		public final void checkEOF() {
			if (hasNextByte()) throw new AssertionError();
		}

		public final String next(CharSet contains) {
			StringBuilder sb = new StringBuilder();
			try {
				do {
					char c = nextChar();
					if (!contains.contains(c)) {
						undo(c);
						return sb.toString();
					}
					sb.append(c);
				} while (true);
			} catch (NoSuchElementException e) {
				if (sb.length() <= 0) throw new AssertionError();
				return sb.toString();
			}
		}

		public final int nextInt() {
			byte b = readByte();
			int n = 0;
			if (b == '-') {
				if (!isNumber(b = readByte())) {
					undo(b);
					throw new NumberFormatException();
				}
				try {
					if (b == '0') {
						if (!isNumber(b = readByte())) {
							undo(b);
							return 0;
						}
						throw new NumberFormatException();
					}
					do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while (isNumber(b = readByte()));
					undo(b);
				} catch (NoSuchElementException e) {}
				return n;
			}
			if (!isNumber(b)) {
				undo(b);
				throw new NumberFormatException();
			}
			try {
				if (b == '0') {
					if (!isNumber(b = readByte())) {
						undo(b);
						return 0;
					}
					throw new NumberFormatException();
				}
				do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while (isNumber(b = readByte()));
				undo(b);
			} catch (NoSuchElementException e) {}
			return n;
		}

		public final int nextInt(int min, int max) {
			int n = nextInt();
			if (min <= n && n <= max) return n;
			throw new NumberFormatException();
		}

		private static boolean isNumber(byte c) {
			return '0' <= c && c <= '9';
		}

		public final long nextLong() {
			byte b = readByte();
			long n = 0;
			if (b == '-') {
				if (!isNumber(b = readByte())) {
					undo(b);
					throw new NumberFormatException();
				}
				try {
					if (b == '0') {
						if (!isNumber(b = readByte())) {
							undo(b);
							return 0;
						}
						throw new NumberFormatException();
					}
					do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while (isNumber(b = readByte()));
					undo(b);
				} catch (NoSuchElementException e) {}
				return n;
			}
			if (!isNumber(b)) {
				undo(b);
				throw new NumberFormatException();
			}
			try {
				if (b == '0') {
					if (!isNumber(b = readByte())) {
						undo(b);
						return 0;
					}
					throw new NumberFormatException();
				}
				do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while (isNumber(b = readByte()));
				undo(b);
			} catch (NoSuchElementException e) {}
			return n;
		}

		public final long nextLong(long min, long max) {
			long n = nextLong();
			if (min <= n && n <= max) return n;
			throw new NumberFormatException();
		}

		public final double nextDouble() {
			StringBuilder sb = new StringBuilder();
			byte b = readByte();
			if (b == '-') {
				sb.append(b);
				b = readByte();
			}
			if (b == '0') {
				sb.append(b);
				b = readByte();
			} else {
				while (isNumber(b)) {
					sb.append(b);
					b = readByte();
				}
			}
			if (b == '.') {
				sb.append(b);
				b = readByte();
				while (isNumber(b)) {
					sb.append(b);
					b = readByte();
				}
			}
			if (b == 'e' || b == 'E') {
				sb.append(b);
				b = readByte();
				if (b == '-' || b == '+') {
					sb.append(b);
					b = readByte();
				}
				while (isNumber(b)) {
					sb.append(b);
					b = readByte();
				}
			}
			undo(b);
			return Double.parseDouble(sb.toString());
		}
	}
}

class MaxFlow {
	private static final class InternalCapEdge {
		final int to;
		final int rev;
		long cap;

		InternalCapEdge(int to, int rev, long cap) {
			this.to = to;
			this.rev = rev;
			this.cap = cap;
		}
	}

	public static final class CapEdge {
		public final int from, to;
		public final long cap, flow;

		CapEdge(int from, int to, long cap, long flow) {
			this.from = from;
			this.to = to;
			this.cap = cap;
			this.flow = flow;
		}

		@Override
		public boolean equals(Object o) {
			if (o instanceof CapEdge) {
				CapEdge e = (CapEdge) o;
				return from == e.from && to == e.to && cap == e.cap && flow == e.flow;
			}
			return false;
		}
	}

	private static final class IntPair {
		final int first, second;

		IntPair(int first, int second) {
			this.first = first;
			this.second = second;
		}
	}

	static final long INF = Long.MAX_VALUE;

	private final int n;
	private final java.util.ArrayList<IntPair> pos;
	private final java.util.ArrayList<InternalCapEdge>[] g;

	@SuppressWarnings("unchecked")
	public MaxFlow(int n) {
		this.n = n;
		pos = new java.util.ArrayList<>();
		g = new java.util.ArrayList[n];
		for (int i = 0; i < n; i++) {
			g[i] = new java.util.ArrayList<>();
		}
	}

	public int addEdge(int from, int to, long cap) {
		rangeCheck(from, 0, n);
		rangeCheck(to, 0, n);
		nonNegativeCheck(cap, "Capacity");
		int m = pos.size();
		pos.add(new IntPair(from, g[from].size()));
		int fromId = g[from].size();
		int toId = g[to].size();
		if (from == to) toId++;
		g[from].add(new InternalCapEdge(to, toId, cap));
		g[to].add(new InternalCapEdge(from, fromId, 0L));
		return m;
	}

	private InternalCapEdge getInternalEdge(int i) {
		return g[pos.get(i).first].get(pos.get(i).second);
	}

	private InternalCapEdge getInternalEdgeReversed(InternalCapEdge e) {
		return g[e.to].get(e.rev);
	}

	public CapEdge getEdge(int i) {
		int m = pos.size();
		rangeCheck(i, 0, m);
		InternalCapEdge e = getInternalEdge(i);
		InternalCapEdge re = getInternalEdgeReversed(e);
		return new CapEdge(re.to, e.to, e.cap + re.cap, re.cap);
	}

	public CapEdge[] getEdges() {
		CapEdge[] res = new CapEdge[pos.size()];
		java.util.Arrays.setAll(res, this::getEdge);
		return res;
	}

	public void changeEdge(int i, long newCap, long newFlow) {
		int m = pos.size();
		rangeCheck(i, 0, m);
		nonNegativeCheck(newCap, "Capacity");
		if (newFlow > newCap) {
			throw new IllegalArgumentException(
					String.format("Flow %d is greater than the capacity %d.", newCap, newFlow));
		}
		InternalCapEdge e = getInternalEdge(i);
		InternalCapEdge re = getInternalEdgeReversed(e);
		e.cap = newCap - newFlow;
		re.cap = newFlow;
	}

	public long maxFlow(int s, int t) {
		return flow(s, t, INF);
	}

	public long maxFlow_fordFulkerson(int s, int t) {
		return flow_fordFulkerson(s, t, INF);
	}

	public long flow(int s, int t, long flowLimit) {
		rangeCheck(s, 0, n);
		rangeCheck(t, 0, n);
		long flow = 0L;
		int[] level = new int[n];
		int[] que = new int[n];
		int[] iter = new int[n];
		while (flow < flowLimit) {
			bfs(s, t, level, que);
			if (level[t] < 0) break;
			java.util.Arrays.fill(iter, 0);
			while (flow < flowLimit) {
				long d = dfs(t, s, flowLimit - flow, iter, level);
				if (d == 0) break;
				flow += d;
			}
		}
		return flow;
	}

	private int[] fordFulkersonDFSCheck;
	private int fordFulkersonDFSCheckNumber;

	public long flow_fordFulkerson(int s, int t, long flowLimit) {
		rangeCheck(s, 0, n);
		rangeCheck(t, 0, n);
		if (fordFulkersonDFSCheck == null) {
			fordFulkersonDFSCheck = new int[n];
			fordFulkersonDFSCheckNumber = 0;
		}
		long flow = 0;
		while(flow < flowLimit) {
			++ fordFulkersonDFSCheckNumber;
			fordFulkersonDFSCheck[s] = fordFulkersonDFSCheckNumber;
			long nowFlow = dfs_fordFulkerson(s, t, flowLimit - flow, fordFulkersonDFSCheckNumber);
			if (nowFlow == 0) return flow;
			flow += nowFlow;
		}
		return flow;
	}

	private long dfs_fordFulkerson(int s, int t, long flowLimit, int checkNumber) {
		if (s == t) return flowLimit;
		long sum = 0;
		for (InternalCapEdge e : g[s]) {
			if (e.cap == 0 || fordFulkersonDFSCheck[e.to] == checkNumber) continue;
			fordFulkersonDFSCheck[e.to] = checkNumber;
			long flow = dfs_fordFulkerson(e.to, t, Math.min(flowLimit, e.cap), checkNumber);
			sum += flow;
			e.cap -= flow;
			getInternalEdgeReversed(e).cap += flow;
		}
		return sum;
	}

	private void bfs(int s, int t, int[] level, int[] que) {
		java.util.Arrays.fill(level, -1);
		int hd = 0, tl = 0;
		que[tl++] = s;
		level[s] = 0;
		while (hd < tl) {
			int u = que[hd++];
			for (InternalCapEdge e : g[u]) {
				int v = e.to;
				if (e.cap == 0 || level[v] >= 0) continue;
				level[v] = level[u] + 1;
				if (v == t) return;
				que[tl++] = v;
			}
		}
	}

	private long dfs(int cur, int s, long flowLimit, int[] iter, int[] level) {
		if (cur == s) return flowLimit;
		long res = 0;
		int curLevel = level[cur];
		for (int itMax = g[cur].size(); iter[cur] < itMax; iter[cur]++) {
			int i = iter[cur];
			InternalCapEdge e = g[cur].get(i);
			InternalCapEdge re = getInternalEdgeReversed(e);
			if (curLevel <= level[e.to] || re.cap == 0) continue;
			long d = dfs(e.to, s, Math.min(flowLimit - res, re.cap), iter, level);
			if (d <= 0) continue;
			e.cap += d;
			re.cap -= d;
			res += d;
			if (res == flowLimit) break;
		}
		return res;
	}

	public boolean[] minCut(int s) {
		rangeCheck(s, 0, n);
		boolean[] visited = new boolean[n];
		int[] stack = new int[n];
		int ptr = 0;
		stack[ptr++] = s;
		visited[s] = true;
		while (ptr > 0) {
			int u = stack[--ptr];
			for (InternalCapEdge e : g[u]) {
				int v = e.to;
				if (e.cap > 0 && !visited[v]) {
					visited[v] = true;
					stack[ptr++] = v;
				}
			}
		}
		return visited;
	}

	private void rangeCheck(int i, int minInclusive, int maxExclusive) {
		if (i < 0 || i >= maxExclusive) {
			throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, maxExclusive));
		}
	}

	private void nonNegativeCheck(long cap, String attribute) {
		if (cap < 0) { throw new IllegalArgumentException(String.format("%s %d is negative.", attribute, cap)); }
	}
}