CodeChef Snackdown 2016 : Online Elimination Round - Jealous Numbers
問題
1000 以下の数が N 個与えられるので、部分集合の中の任意の2つが互いに素になるように部分集合を作るとき、最大の部分集合の数を答えよ。
解法
NUMSET - Editorial - CodeChef Discuss
uwiさんに聞いた。
すべての数は 31 以下の素数と、32以上の素数 0〜1 個からなる。
ルール上、1と素数のべき乗は無条件に含んで良いはずである。
31以下の素数のみからなる場合、素因数の構成をビットマスクに持って bitDP する。
コード
import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.*; public class NUMSET { private static class Task { final int[] primes = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}; int P = primes.length; int maximize(int[] A) { ArrayList<Integer> smalls = new ArrayList<>();// 31以下の素因数のみからなる合成数の、素因数のビットマスク HashMap<Integer, ArrayList<Integer>> larges = new HashMap<>();//32以上の素数を素因数に含む数について、32以上の素数をキーにして、ビットマスクを持っておく //素数のべき乗と1については無条件で含んで良い int used = 0; int cnt = 0; for (int a : A) { if (a == 1) { cnt++; continue; } int mask = 0; for (int i = 0; i < primes.length; i++) { if (a % primes[i] == 0) { mask |= (1 << i); while (a % primes[i] == 0) a /= primes[i]; } } if (a == 1) { if (Integer.bitCount(mask) == 1) { if ((used & mask) == 0) { used |= mask; cnt++; } } else { smalls.add(mask); } } else { if (!larges.containsKey(a)) larges.put(a, new ArrayList<>()); larges.get(a).add(mask); } } //dp[mask] := 使用した素因数のビットマスクが mask のときのグループの最大数 int[] dp = new int[1 << P]; dp[used] = cnt; //まずは31以下の素因数からのみなる数を見て遷移させていく ArrayDeque<Integer> deque = new ArrayDeque<>(); deque.add(used); while (!deque.isEmpty()) { int v = deque.poll(); for (int u : smalls) { if ((v & u) != 0) continue; if (dp[v | u] < dp[v] + 1) { dp[v | u] = dp[v] + 1; deque.add(v | u); } } } //32以上の素数を持つ数についてみる。この時、同じ素数を持つ数を使った遷移は1回しかできないことに注意しながらやる HashMap<Integer, Integer> map = new HashMap<>(); for (Map.Entry<Integer, ArrayList<Integer>> e : larges.entrySet()) { ArrayList<Integer> masks = e.getValue(); for (int mask : masks) { for (int i = 0; i < (1 << P); i++) { if ((mask & i) != 0) continue; if (map.containsKey(i | mask) && map.get(i | mask) >= dp[i] + 1) continue; map.put(i | mask, dp[i] + 1); } } for (Map.Entry<Integer, Integer> m : map.entrySet()) { int mask = m.getKey(); dp[mask] = Math.max(dp[mask], m.getValue()); } map.clear(); } int max = 0; for (int d : dp) max = Math.max(max, d); return max; } //ナイーブ int gcd(int x, int y) { return y > 0 ? gcd(y, x % y) : x; } int naive(int[] A) { int N = A.length; int max = 0; for (int mask = 0; mask < (1 << N); mask++) { if (Integer.bitCount(mask) < max) continue; boolean ok = true; check: for (int i = 0; i < N; i++) { if ((mask & (1 << i)) == 0) continue; for (int j = i + 1; j < N; j++) { if ((mask & (1 << j)) == 0) continue; if (gcd(A[i], A[j]) > 1) { ok = false; break check; } } } if (ok) { max = Math.max(Integer.bitCount(mask), max); } } return max; } void solve(FastScanner in, PrintWriter out) { int T = in.nextInt(); for (; T > 0; T--) { int N = in.nextInt(); int[] A = in.nextIntArray(N); out.println(maximize(A)); } } } // Template public static void main(String[] args) { OutputStream outputStream = System.out; FastScanner in = new FastScanner(); PrintWriter out = new PrintWriter(outputStream); Task solver = new Task(); solver.solve(in, out); out.close(); } private static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int bufferLength = 0; private boolean hasNextByte() { if (ptr < bufferLength) { return true; } else { ptr = 0; try { bufferLength = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (bufferLength <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) { array[i] = nextDouble(); } return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][]; for (int i = 0; i < n; i++) { map[i] = nextDoubleArray(m); } return map; } public int nextInt() { return (int) nextLong(); } public int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) { array[i] = nextInt(); } return array; } } }