AtCoder Beginner Contest 260(Rated範囲外)

A - A Unique Letter
- 思考過程
B - Better Students Are Needed!
- 思考過程
C - Changing Jewels
- 思考過程
D - Draw Your Cards
- 思考過程
E - At Least One
- 思考過程

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

A - A Unique Letter

思考過程

a～zの出現回数を数える。
上記1.の結果が $1$ の文字があればそれを出力して終了、なければ $-1$ とする。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();

        int[] a = new int[26];
        for (int i = 0; i < s.length; i++) {
            a[s[i] - 'a']++;
        }
        for (int i = 0; i < a.length; i++) {
            if (a[i] == 1) {
                System.out.println((char) ('a' + i));
                return;
            }
        }
        System.out.println(-1);
    }
}

ここまで1分46秒＋0ペナ。831位。

B - Better Students Are Needed!

問題
実装量多くて大変だった。

思考過程

適切にコンパレータを設定したPriorityQueueに残った人を入れ、指定の回数取り出す。ということを $3$ 回行う。

import java.util.PriorityQueue;
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 x = sc.nextInt();
        int y = sc.nextInt();
        int z = sc.nextInt();
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.i = i;
            o.a = sc.nextInt();
            arr[i] = o;
        }
        // aの降順、iの昇順
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> {
            if (o1.a != o2.a) {
                return o2.a - o1.a;
            }
            return o1.i - o2.i;
        });
        for (int i = 0; i < n; i++) {
            Obj o = arr[i];
            o.b = sc.nextInt();
            o.c = o.a + o.b;
            que.add(o);
        }
        sc.close();

        PriorityQueue<Integer> ans = new PriorityQueue<>();
        for (int i = 0; i < x; i++) {
            ans.add(que.poll().i);
        }

        // bの降順、iの昇順
        PriorityQueue<Obj> que2 = new PriorityQueue<>((o1, o2) -> {
            if (o1.b != o2.b) {
                return o2.b - o1.b;
            }
            return o1.i - o2.i;
        });
        que2.addAll(que);
        for (int i = 0; i < y; i++) {
            ans.add(que2.poll().i);
        }

        // a+bの降順、iの昇順
        PriorityQueue<Obj> que3 = new PriorityQueue<>((o1, o2) -> {
            if (o1.c != o2.c) {
                return o2.c - o1.c;
            }
            return o1.i - o2.i;
        });
        que3.addAll(que2);
        for (int i = 0; i < z; i++) {
            ans.add(que3.poll().i);
        }

        while (!ans.isEmpty()) {
            System.out.println(ans.poll() + 1);
        }
    }

    static class Obj {
        int a, b, c, i;
    }
}

ここまで9分21秒＋0ペナ。439位。

C - Changing Jewels

問題
順序以外特に気を付ける要素なさそうで、本当にそれだけでいいのかと困惑した。

思考過程

レベル $n$ の赤い宝石を全て変換し、その後レベル $n$ の青い宝石を全て変換する。ということをレベル $N$ から $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 x = sc.nextInt();
        int y = sc.nextInt();
        sc.close();

        long[] r = new long[n + 1];
        long[] b = new long[n + 1];
        r[n] = 1;
        for (int i = n; i >= 2; i--) {
            r[i - 1] += r[i];     // レベルiの赤→レベルi-1の赤
            b[i] += r[i] * x;     // レベルiの赤→レベルiの青
            r[i - 1] += b[i];     // レベルiの青→レベルi-1の赤
            b[i - 1] += b[i] * y; // レベルiの青→レベルi-1の青
        }
        System.out.println(b[1]);
    }
}

ここまで14分09秒＋0ペナ。206位。

D - Draw Your Cards

問題

思考過程

TreeMap＜場に見えている整数、重なっているカードのList＞を管理することを考える。
カードを重ねる操作をする際は、Listへの参照を取得した後に元のエントリを削除して新しいエントリを追加すればよい。
カードを食べる場合は、Listの各要素にターン数を設定する。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

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

        TreeMap<Integer, List<Integer>> map = new TreeMap<>();
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        for (int i = 0; i < n; i++) {
            Integer key = map.higherKey(p[i]);
            List<Integer> list = null;
            if (key == null) {
                list = new ArrayList<>();
            } else {
                list = map.get(key);
                map.remove(key);
            }
            list.add(p[i]);
            if (list.size() == k) {
                for (int e : list) {
                    ans[e] = i + 1;
                }
            } else {
                map.put(p[i], list);
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i : ans) {
            pw.println(i);
        }
        pw.flush();
    }
}

ここまで21分25秒＋0ペナ。63位。

E - At Least One

問題
初め全然わからず、一旦飛ばして先にFを解こうとする。
20分ほどで怪しい解法を一度提出してみるも大半がWAで、Eに戻ってくる。

思考過程

普通に該当するものを数えるのと、余事象を数えるのを両方捨てずに考える。
余事象を考えても、「全ての $i$ について満たさない」ならまだしも、「いずれかの $i$ について満たさない」だとかえって数えにくそう。
該当するものを数えるなら、連続部分列の左側を固定してみるのがいいか？
左側を固定すると、右側が特定の箇所より先のものは全て条件を満たす。
　
まず左側を $1$ とすると、右側は $A$ の最大値以上であることが条件となる。
左側を $2, 3, \cdots$ と増やしていった場合、「 $A_i \lt$ 左側」となった $A_i$ は最大値判定の集合から除外し、代わりに $B_i$ を入れれば、同様に集合内の最大値以上であることを右側の条件とできる。
「 $B_i \lt$ 左側」となるものが発生した（集合の要素数が $N$ でなくなった）時点で、以降条件を満たすことはなくなる。
最大値の取得ができ、値に該当する要素の削除ができ、重複要素の存在も可能なデータ構造ということで、MultiSet（自作）を使う。
　
上記4.を答えに反映させる部分は、左側を $i$ 、右側の最小値を $j$ とすると、 $f(j-i+1)$ ～ $f(M-i+1)$ に $1$ ずつ加算したい形になっているため、いもす法で求められる。

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

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]);
        Map<Integer, List<Integer>> map = new HashMap<>();
        MultiTreeSet<Integer> set = new MultiTreeSet<>();
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]);
            int b = Integer.parseInt(sa[1]);
            List<Integer> list = map.get(a);
            if (list == null) {
                list = new ArrayList<>();
                map.put(a, list);
            }
            list.add(b);
            set.add(a);
        }
        br.close();

        int[] ans = new int[m + 5];
        for (int i = 1; i <= m; i++) {
            // 7
            if (set.sizeAll() < n) {
                break;
            }

            // 9
            int j = set.last();
            ans[j - i + 1]++;
            ans[m - i + 2]--;

            // 6
            while (set.contains(i)) {
                set.remove(i);
            }
            List<Integer> list = map.get(i);
            if (list != null) {
                for (int e : list) {
                    set.add(e);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= m; i++) {
            ans[i] += ans[i - 1]; // 9
            sb.append(ans[i]).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    // 以下ライブラリ（未使用メソッド省略）

    static class MultiTreeSet<T> {
        TreeMap<T, Integer> map = new TreeMap<>();
        int size = 0;

        void add(T e) {
            map.put(e, map.getOrDefault(e, 0) + 1);
            size++;
        }

        void remove(T e) {
            if (e != null && map.containsKey(e)) {
                int val = map.get(e);
                if (val == 1) {
                    map.remove(e);
                } else {
                    map.put(e, val - 1);
                }
                size--;
            }
        }

        int sizeAll() {
            return size;
        }

        boolean contains(T e) {
            return map.containsKey(e);
        }

        T last() {
            return map.lastKey();
        }
    }
}