AtCoder Regular Contest 114 - ks2mのブログ

A - Not coprime
- 思考過程
B - Special Subsets
- 思考過程

コンテスト前のレート：2065
レート通りのパフォーマンスが得られる順位：331位（1300点、107分57秒）

A - Not coprime

問題
雑すぎて2ペナ。
さらに、 $2^{15}$ 通り全探索の中身が、GCDを取ればいいのに面倒なことしている。

思考過程

$X_i$ の最小の素因数が $Y$ に入っていなければ $Y$ に掛ける？　→5ケースWA
実装ミスったかもと思って間違いのない実装に直す。　→変わらず
　
$X_i$ の最小以外の素因数が既に入っている可能性もあるのでおかしい。
$50$ 以下の素数を列挙してみたら $15$ 個しかなかったので、 $Y$ に掛ける素因数の集合を全探索すればよさそう。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        sa = br.readLine().split(" ");
        int[] x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        List<Map<Integer, Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(bunkai(x[i]));
        }

        int[] sosuu = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
        int m = sosuu.length;
        int end = 1 << m;
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < end; i++) {
            long y = 1;
            for (int j = 0; j < m; j++) {
                if ((i >> j & 1) == 1) {
                    y *= sosuu[j];
                }
            }
            boolean flg = true; // xが全て条件を満たすか
            for (int j = 0; j < n; j++) {
                boolean flg2 = false; // x[j]の素因数の中にyの素因数と共通するものがあるか
                for (int k : list.get(j).keySet()) {
                    if (y % k == 0) {
                        flg2 = true;
                        break;
                    }
                }
                if (!flg2) {
                    flg = false;
                    break;
                }
            }
            if (flg) {
                ans = Math.min(ans, y);
            }
        }
        System.out.println(ans);
    }

    // 以下ライブラリ（素因数分解）

    static Map<Integer, Integer> bunkai(int n) {
        Map<Integer, Integer> soinsu = new HashMap<>();
        int end = (int) Math.sqrt(n);
        int d = 2;
        while (n > 1) {
            if (n % d == 0) {
                n /= d;
                soinsu.put(d, soinsu.getOrDefault(d, 0) + 1);
                end = (int) Math.sqrt(n);
            } else {
                if (d > end) {
                    d = n - 1;
                }
                d++;
            }
        }
        return soinsu;
    }
}

ここまで13分54秒＋2ペナ。637位。

B - Special Subsets

問題

思考過程

$a$ と $f(a)$ は同じ集合に入れるしかない。
UnionFindで $a$ と $f(a)$ を結合していった時にできる各連結成分が（条件を満たしていれば）最小の集合 $T$ で、集合同士を合わせるかどうかは自由に決められるので、条件を満たしている連結成分の個数を $M$ として、 $2^M-1$ が答え。
　
各連結成分が条件を満たしているかどうかは、連結成分の頂点数と、各頂点 $a$ の $f(a)$ の種類数が一致しているかどうかを調べればよさそう？　→実装ミスして $a$ の種類数を数えるという意味のないことしていたおかげでAC
　
コンテスト終了後に気付いたが、上記3.は誤りで、 $f(a)$ の種類数が $a$ の個数より少ない場合は、連結成分内の $f(a)$ 個を取ればサイクルになっており、また、連結成分 $1$ つにつき必ず $1$ 個のみサイクルができるようである。
よって、余計な判定をせずに連結成分数をそのまま $M$ とすればよかった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        sa = br.readLine().split(" ");
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        DSU uf = new DSU(n);
        for (int i = 0; i < n; i++) {
            uf.merge(i, f[i]);
        }

        int mod = 998244353;
        // ↓コンテスト中の無意味実装
//      int m = 0;
//      List<List<Integer>> g = uf.groups();
//      for (List<Integer> g2 : g) {
//          Set<Integer> set = new HashSet<>();
//          for (Integer i : g2) {
//              set.add(i); // 頭の中ではここがf[i]だったがそれだとWA
//          }
//          if (g2.size() == set.size()) {
//              m++;
//          }
//      }
        // ↓これで十分
        int m = uf.num();

        long ans = power(2, m, mod);
        ans += mod - 1;
        ans %= mod;
        System.out.println(ans);
    }

    // 以下ライブラリ

    static long power(long x, long n, int m) {
        if (n == 0) {
            return 1;
        }
        long val = power(x, n / 2, m);
        val = val * val % m;
        if (n % 2 == 1) {
            val = val * x % m;
        }
        return val;
    }
}

// 以下ACLを移植したDSU