結果

問題 No.2136 Dice Calendar?
ユーザー CuriousFairy315CuriousFairy315
提出日時 2022-10-09 16:38:04
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 19,349 bytes
コンパイル時間 3,226 ms
コンパイル使用メモリ 93,556 KB
実行使用メモリ 242,392 KB
最終ジャッジ日時 2024-06-23 15:50:53
合計ジャッジ時間 33,146 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 99 ms
60,240 KB
testcase_01 AC 101 ms
53,148 KB
testcase_02 AC 261 ms
59,656 KB
testcase_03 AC 104 ms
53,036 KB
testcase_04 AC 102 ms
53,212 KB
testcase_05 AC 122 ms
53,488 KB
testcase_06 AC 119 ms
53,288 KB
testcase_07 AC 186 ms
57,868 KB
testcase_08 AC 207 ms
59,444 KB
testcase_09 AC 257 ms
58,956 KB
testcase_10 AC 287 ms
59,160 KB
testcase_11 AC 469 ms
61,688 KB
testcase_12 AC 491 ms
61,100 KB
testcase_13 AC 498 ms
61,664 KB
testcase_14 AC 589 ms
61,516 KB
testcase_15 AC 1,384 ms
80,220 KB
testcase_16 AC 1,545 ms
85,444 KB
testcase_17 AC 2,542 ms
113,580 KB
testcase_18 AC 3,262 ms
131,596 KB
testcase_19 AC 4,967 ms
170,264 KB
testcase_20 TLE -
testcase_21 TLE -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder_8614.solver5;

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 = 3;
		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);
				} else { // 流し直し
					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)); }
	}
}
0