AtCoder Regular Contest 124

コンテスト前のレート:2114
レート通りのパフォーマンスが得られる順位:272位(1900点、125分28秒)

A - LR Constraints

問題

思考過程
  1. とりあえずO(N^2)とかが通る制約。
  2. k_iで指定された箇所は1通りだが、それ以外の箇所は、最も左、最も右の制限を無視すればK通り自由に決められる。
  3. 最も左、最も右の制限を取り入れるには、c_iが"R"ならば、カウント配列を用意し、k_iより左に全部+1c_iが"L"ならば、k_iより右に全部+1すればよい。
  4. このようにして作成できたカウント配列の各要素の積(ただし、k_iで指定された箇所は1)を求める。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] c = new int[n];
        boolean[] b = new boolean[n];
        for (int i = 0; i < k; i++) {
            String s = sc.next();
            int a = sc.nextInt() - 1;
            if (s.equals("R")) {
                for (int j = 0; j < a; j++) {
                    c[j]++;
                }
            } else {
                for (int j = a + 1; j < n; j++) {
                    c[j]++;
                }
            }
            b[a] = true;
        }
        sc.close();

        int mod = 998244353;
        long ans = 1;
        for (int i = 0; i < n; i++) {
            if (!b[i]) {
                ans *= c[i];
                ans %= mod;
            }
        }
        System.out.println(ans);
    }
}

ここまで7分32秒+0ペナ。201位。


B - XOR Matching 2

問題
答えを昇順に出力する必要はないと勘違いして1WA。

思考過程
  1. これもO(N^2)が通る制約。
  2. ということで、a_1b_1b_nそれぞれを対応させた場合のxを全部調べる。
     
  3. 数列a, bをMap形式<値、登場回数>にしておく。
  4. そうすると、まずそれぞれのMapのエントリ数が合っていなければ答えはなし。
     
  5. xについて2つのMapを突き合せる際は、xを構成するa_i, b_iの登場回数が全て一致する必要がある。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
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));
        int n = Integer.parseInt(br.readLine());
        // 3
        String[] sa = br.readLine().split(" ");
        Map<Integer, Integer> map1 = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(sa[i]);
            map1.put(a, map1.getOrDefault(a, 0) + 1);
        }
        sa = br.readLine().split(" ");
        Map<Integer, Integer> map2 = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(sa[i]);
            map2.put(a, map2.getOrDefault(a, 0) + 1);
        }
        br.close();

        // 4
        if (map1.size() != map2.size()) {
            System.out.println(0);
            return;
        }

        List<Integer> list = new ArrayList<>();
        Integer[] arr = map1.keySet().toArray(new Integer[0]);
        int a0 = arr[0];
        for (int bi : map2.keySet()) {
            int x = a0 ^ bi; // 2
            if (map1.get(a0) != map2.get(bi)) {
                continue;
            }
            // 5
            boolean flg = true;
            for (int i = 1; i < arr.length; i++) {
                int a = arr[i];
                int b = a ^ x;
                int cnt = map2.getOrDefault(b, 0);
                // 登場回数が異なればNG
                if (cnt != map1.get(a)) {
                    flg = false;
                    break;
                }
            }
            if (flg) {
                list.add(x);
            }
        }
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(list.size());
        Collections.sort(list);
        for (int i : list) {
            pw.println(i);
        }
        pw.flush();
    }
}

ここまで19分51秒+1ペナ。248位。



C問題は解けず。
素因数を上手くばらけさせたいような雰囲気だけ感じるも、単純にO(2^N)で分ける方法しか思いつかず。


D - Yet Another Sorting Problem

問題
C問題が300人に解かれているくらいになっても全然わからなかったので、飛ばしてこれをやることに。
最終的には、もはやC問題を通しても旨味が少ないと思い、こちらに集中することにした。
結果的になんとか通せた。
思考過程はかなりエスパー寄り。

思考過程
  1. i \neq p_iの場合、Nを境にしてどちらも同じ側の場合は最低2回、異なる側の場合は最低1回かかる。
  2. N以下の要素とN超の要素で、各要素の最低操作回数の合計が大きい方が答え? →例1で3, 4, 5の合計が5となり、合わない。
     
  3. 手で色々動かしてみると、ip_iをつなげていった連結成分内で移動させることが基本に思えてきたため、とりあえずUnionFindを使ってみる。
  4. Nの左側とか右側とかあまり関係なく、連結成分ごとに転倒数を求めてみればなんとなく合っているような? →3/110AC
     
  5. Nの左側⇔右側だけの移動に限らなければ、1回ごとに1つは確実に合わせることができ、全部ばらばらなら最後の1回だけ2箇所揃って、N+M-1回でできる感じ。
  6. 実験すると、左右にまたがる連結成分ならば、連結成分のサイズ-1回で揃えられそう。
  7. 片側だけの連結成分ならば、一時的にもう片方から1要素崩して動かすことになるが、連結成分のサイズ+1回で揃えられそう。 →84/110AC
     
  8. 大筋は合っていると信じて、コーナーケースを考える。
  9. 片側のみの連結成分が左右両方に存在すれば、上記7.の「一時的にもう片方から1要素崩して」の部分が、崩すのではなく揃えたい連結成分にとってプラスの操作にでき、結果それぞれの連結成分のサイズの和でよくなりそう。(+12つ落ちる)
  10. 片側のみの連結成分が左右両方に1つでも存在すれば、全ての片側のみの連結成分について+1が落とせる? →88/110AC
     
  11. さらに実験を重ねた結果、どうやら片側のみの連結成分は左右から1つずつ選んでペアにしないと、+1を落とせる効果はないようで、ペアにできる分は「連結成分のサイズ」、余りは「連結成分のサイズ+1」とする。 →AC
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

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]);
        int m = Integer.parseInt(sa[1]);
        int nm = n + m;
        sa = br.readLine().split(" ");
        int[] p = new int[nm];
        for (int i = 0; i < nm; i++) {
            p[i] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        // 3
        DSU uf = new DSU(nm);
        for (int i = 0; i < nm; i++) {
            uf.merge(i, p[i]);
        }

        List<List<Integer>> g = uf.groups();
        long ans = 0;
        Queue<Integer> x1 = new ArrayDeque<>();
        Queue<Integer> x2 = new ArrayDeque<>();
        for (List<Integer> g2 : g) {
            if (g2.size() > 1) {
                int min = g2.get(0);
                int max = g2.get(g2.size() - 1);
                if (min < n && n <= max) {
                    // 6: 左右にまたがる連結成分
                    ans += g2.size() - 1;
                } else if (max < n) {
                    // 左側のみの連結成分
                    x1.add(g2.size());
                } else if (n <= min) {
                    // 右側のみの連結成分
                    x2.add(g2.size());
                } else {
                    // 実装ミス検知用
                    throw new Exception();
                }
            }
        }
        // 11: ペアにできる分
        while (!x1.isEmpty() && !x2.isEmpty()) {
            ans += x1.poll();
            ans += x2.poll();
        }
        // 11: 余り
        while (!x1.isEmpty()) {
            ans += x1.poll() + 1;
        }
        while (!x2.isEmpty()) {
            ans += x2.poll() + 1;
        }
        System.out.println(ans);
    }
}

// 以下ACLを移植したDSU

提出
ここまで106分28秒+4ペナ。296位。



Eは一応問題文は読んだが、わけがわからずすぐ閉じた。
Fは開いてもいない。



終結果:ABDの3完1400点、126分28秒、354位、パフォーマンス1983
レート変動:2114→2101(-13)


2完でパフォ1380ほどになりそうだったことを思えば、十分浅い傷で済んだ。
約数全探索何で出てこなかったかな・・・。

D問題のペナは出す度に前進につながり、必要経費だったと思えるが、B問題のペナはひどすぎる。