AtCoder Beginner Contest 261(Rated範囲外)

ABC

コンテスト前のレート：2026
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：325位（2000点、57分58秒）

A - Intersection

問題

思考過程
  1. 共通部分は、左側の大きい方から右側の小さい方までの長さとなる。
  2. 上記を計算してマイナスになる場合は0とする。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int l1 = sc.nextInt();
        int r1 = sc.nextInt();
        int l2 = sc.nextInt();
        int r2 = sc.nextInt();
        sc.close();

        int l = Math.max(l1, l2);
        int r = Math.min(r1, r2);
        System.out.println(Math.max(r - l, 0));
    }
}

ここまで1分44秒＋0ペナ。246位。


B - Tournament Result

問題

思考過程
  1. i \lt jの範囲を全部調べ、問題文の3点を判定する。
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();
        char[][] a = new char[n][n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.next().toCharArray();
        }
        sc.close();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[i][j] == 'W' && a[j][i] != 'L') {
                    System.out.println("incorrect");
                    return;
                }
                if (a[i][j] == 'L' && a[j][i] != 'W') {
                    System.out.println("incorrect");
                    return;
                }
                if (a[i][j] == 'D' && a[j][i] != 'D') {
                    System.out.println("incorrect");
                    return;
                }
            }
        }
        System.out.println("correct");
    }
}

ここまで4分01秒＋0ペナ。108位。


C - NewFolder(1)

問題

思考過程
  1. Map＜文字列、登場回数＞で管理しながら処理していく。
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
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();
        Map<String, Integer> map = new HashMap<>();
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            int x = map.getOrDefault(s, 0);
            if (x == 0) {
                pw.println(s);
            } else {
                pw.println(s + "(" + x + ")");
            }
            map.put(s, x + 1);
        }
        pw.flush();
        sc.close();
    }
}

ここまで6分34秒＋0ペナ。116位。


D - Flipping and Bonus

問題

思考過程
  1. O(N^2)とかが間に合う制約。
  2. 「dp[i][j]:=i回コイントス後、カウンタがjである場合の最大値」を考える。
  3. 遷移は表の場合と裏の場合の2通り。
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 m = sc.nextInt();
        int[] x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
        }
        int[] y = new int[n + 1];
        for (int i = 0; i < m; i++) {
            y[sc.nextInt()] = sc.nextInt();
        }
        sc.close();

        long[][] dp = new long[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                // 表
                dp[i + 1][j + 1] = Math.max(dp[i + 1][j + 1], dp[i][j] + x[i] + y[j + 1]);
                // 裏
                dp[i + 1][0] = Math.max(dp[i + 1][0], dp[i][j]);
            }
        }

        long ans = 0;
        for (int i = 0; i <= n; i++) {
            ans = Math.max(ans, dp[n][i]);
        }
        System.out.println(ans);
    }
}

ここまで11分45秒＋0ペナ。78位。


E - Many Operations

問題
最後のループを初め1～nではなく0～n-1にしていたことでデバッグに5分ほど要した。

思考過程
  1. 操作の累積和のようなもの（合成関数）を求められれば、愚直に操作すればO(N^2)のところをO(N)にできる。
  2. and、or、xorが混ざった合成関数ってどうやって求めれば？
  3. よくわからないので桁ごとに考えることにする。
    　
  4. andの場合、A_i=1の場合は元の値、A_i=0の場合は0
  5. orの場合、A_i=0の場合は元の値、A_i=1の場合は1
  6. xorの場合、A_i=0の場合は元の値、A_i=1の場合は元の値の反転
  7. 必ず0、必ず1、元の値、元の値の反転の4状態があり得ることになるので、桁ごと、操作回数ごとにどの状態になるかを前計算した後、Cに適用する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

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

        int m = 30;
        // 0：cによらず0
        // 1：cによらず1
        // 2：c
        // 3：not c
        int[][] b = new int[m][n + 1];
        for (int k = 0; k < m; k++) {
            b[k][0] = 2;
            for (int i = 0; i < n; i++) {
                int d = a[i] >> k & 1;
                if (t[i] == 1) {
                    // 思考過程4
                    if (d == 1) {
                        b[k][i + 1] = b[k][i];
                    }
                } else if (t[i] == 2) {
                    // 思考過程5
                    if (d == 0) {
                        b[k][i + 1] = b[k][i];
                    } else {
                        b[k][i + 1] = 1;
                    }
                } else {
                    // 思考過程6
                    if (d == 0) {
                        b[k][i + 1] = b[k][i];
                    } else {
                        if (b[k][i] < 2) {
                            // 0⇔1
                            b[k][i + 1] = 1 - b[k][i];
                        } else {
                            // 2⇔3
                            b[k][i + 1] = 5 - b[k][i];
                        }
                    }
                }
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 1; i <= n; i++) {
            int ans = 0;
            for (int k = 0; k < m; k++) {
                if (b[k][i] < 2) {
                    ans += b[k][i] << k;
                } else {
                    int d = c >> k & 1;
                    if (b[k][i] == 3) {
                        d = 1 - d;
                    }
                    ans += d << k;
                }
            }
            pw.println(ans);
            c = ans;
        }
        pw.flush();
    }
}

ここまで31分34秒＋0ペナ。253位。


F - Sorting Color Balls

問題
自分の転倒数ライブラリが、要素の値が大きい場合に対して簡単な小細工だけ入っている状態だったが、きちんと座圧するものを用意しておくべきか・・・。

思考過程
  1. Xが同じ球が複数存在する場合にどのような並べ方にすればよいかだが、これは元の順序を保ったままにするのが良さそう。
  2. 入れ替えコスト0があることで、元の順序から変えても損しないことはあっても、得することはない。
  3. とりあえず各球の移動先を求めておく。
    　
  4. コスト0がない場合の総コストは、各球の移動距離の合計の半分・・・ではなく転倒数。
  5. 上記4.からコスト0で済む回数を引くことを考える。
  6. これは各色について、同じ色の球だけに注目した時の転倒数となる。
    　
  7. 色の種類数分毎回要素数O(N)のBITを生成していてTLEになったので、座標圧縮を行って合計でO(N)となるようにする。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeMap;

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());
        String[] sa = br.readLine().split(" ");
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.i = i;
            o.c = Integer.parseInt(sa[i]);
            arr[i] = o;
        }
        sa = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i].x = Integer.parseInt(sa[i]);
        }
        br.close();

        // 3. 移動先pを求める（xの昇順、iの昇順）
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> {
            if (o1.x != o2.x) {
                return o1.x - o2.x;
            }
            return o1.i - o2.i;
        });
        for (Obj o : arr) {
            que.add(o);
        }
        for (int i = 0; i < n; i++) {
            Obj o = que.poll();
            o.p = i;
        }

        // 4. コスト0がない場合の総コスト
        List<Integer> list = new ArrayList<>(n);
        for (Obj o : arr) {
            list.add(o.p);
        }
        long ans = tentousuu(zaatu(list));

        // 色ごとに元の順序を保ってまとめる
        que = new PriorityQueue<>((o1, o2) -> {
            if (o1.c != o2.c) {
                return o1.c - o2.c;
            }
            return o1.i - o2.i;
        });
        for (Obj o : arr) {
            que.add(o);
        }

        list.clear();
        while (!que.isEmpty()) {
            Obj o = que.poll();
            list.add(o.p);
            // 次も同じ色の場合
            if (!que.isEmpty() && que.peek().c == o.c) {
                continue;
            }
            // 5, 6
            ans -= tentousuu(zaatu(list));
            list.clear();
        }
        System.out.println(ans);
    }

    static class Obj {
        int i, c, x, p;
    }

    // 以下ライブラリ

    static int[] zaatu(List<Integer> a) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < a.size(); i++) {
            map.put(a.get(i), null);
        }
        Integer[] arr = map.keySet().toArray(new Integer[0]);
        int cnt = 0;
        for (Integer i : arr) {
            cnt++;
            map.put(i, cnt);
        }
        int[] b = new int[a.size()];
        for (int i = 0; i < a.size(); i++) {
            b[i] = map.get(a.get(i));
        }
        return b;
    }

    static long tentousuu(int[] a) {
        int n = a.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            min = Math.min(min, a[i]);
            max = Math.max(max, a[i]);
        }
        min--;
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = a[i] - min;
        }

        BIT bit = new BIT(max - min);
        long ret = 0;
        for (int i = 0; i < n; i++) {
            ret += i - bit.sum(b[i]);
            bit.add(b[i], 1);
        }
        return ret;
    }

    static class BIT {
        int n;
        long[] arr;

        public BIT(int n) {
            this.n = n;
            arr = new long[n + 1];
        }

        void add(int idx, long val) {
            for (int i = idx; i <= n; i += i & -i) {
                arr[i] += val;
            }
        }

        long sum(int idx) {
            long sum = 0;
            for (int i = idx; i > 0; i -= i & -i) {
                sum += arr[i];
            }
            return sum;
        }
    }
}

ここまで58分09秒＋1ペナ。339位。



正解者数がGよりExの方が多かったので両方の問題を見てできそうな方をやることにする。

Exの方がいいかなとは思ったが、Gで適当な解法を思い付いたので一応投げるだけ投げてみる。
それは、Tから始めてA_i→C_iの置換を辺とみなしてSにたどり着くまでBFSするというもの。
あまり期待していなかったが結果は半分TLEと1ケースWA。TLEはともかくWAは何で出たのかわからない。

Exは出次数0から逆向きに辿ることを考えるが、例３が上手くいかず。



最終結果：ABCDEFの6完2000点、63分09秒、385位、パフォーマンス1948相当
レート変動：2026（Unrated）


またDまでは十分早かったがE、Fが微妙という結果。
まあ考察部分では遅れていなかったと思うので、実装であと少し注意力があればノルマ達成くらいはできていたかな・・・。
Eは後から思えば何故ループ回す範囲を間違えたという感じだし、Fは転倒数ライブラリを持ち出す前まではBITを毎回生成しないように気を付ける意識を持っていたのに忘れる始末。

なお、ABCトーナメントの相手が326位で、ちょうどノルマ達成＝勝ちだった。