AtCoder Beginner Contest 216(Rated範囲外)

A - Signed Difficulty
- 思考過程
B - Same Name
- 思考過程
C - Many Balls
- 思考過程
D - Pair of Balls
- 思考過程
E - Amusement Park
- 思考過程
F - Max Sum Counting
- 思考過程
G - 01Sequence
- 思考過程

コンテスト前のレート：2034
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：309位（2600点、100分19秒）

A - Signed Difficulty

思考過程

入力を文字列で受け取って、普通は" "（半角スペース）で分割することがほとんどだが、この問題では"."（半角ピリオド）で $X, Y$ に分割する。
あとは問題文の通り条件分岐を行う。
　
としたかったが、何故か分割後の文字列配列が要素数 $2$ ではなく $0$ になってしまう。
splitメソッドの引数は正規表現であり、"."は任意の $1$ 文字を表してしまうため、エスケープする必要があった。

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split("\\."); // 4
        int x = Integer.parseInt(sa[0]);
        int y = Integer.parseInt(sa[1]);
        br.close();

        if (y <= 2) {
            System.out.println(x + "-");
        } else if (y <= 6) {
            System.out.println(x);
        } else {
            System.out.println(x + "+");
        }
    }
}

ここまで3分35秒＋0ペナ。1720位。

B - Same Name

問題

思考過程

苗字と名前を英小文字以外の適当な文字で連結した文字列を、Setに追加していく。
Setのサイズが $N$ と一致するかどうかを判定する。

わざわざ連結なんてしなくても、行単位で読み込んだ文字列を追加していけばよかった。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<String> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(sc.next() + "-" + sc.next());
        }
        sc.close();

        if (set.size() == n) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }
}

ここまで4分57秒＋0ペナ。645位。

C - Many Balls

問題

思考過程

ABC188-Fなどのように、 $N$ を $0$ にする方向で手順を求め、最後に逆順にして出力する。
現在の数 $N$ が $2$ で割れるなら割り、そうでなければ $1$ を引くのが最短手順。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        sc.close();

        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            if (n % 2 == 0) {
                sb.append('B');
                n /= 2;
            } else {
                sb.append('A');
                n--;
            }
        }
        sb.reverse();
        System.out.println(sb.toString());
    }
}

ここまで6分50秒＋0ペナ。177位。

D - Pair of Balls

問題
ABC139-Eを思い浮べていた。これを探し出して一部コピペできないか検討するのと、普通に一から実装するのとどちらが早いかと一瞬思ったが、普通に一から実装した。

思考過程

操作可能な箇所があれば、特に順番は気にせず貪欲に操作してよい。
上記の類題では、操作を行えた箇所のみを次のループでの処理対象候補とすることで、計算量を抑えていた記憶があったので、そのような流れをベースにして進めていくことを考える。
各筒の次の要素のインデックス（これはListではなくQueueにしておけば不要だった）や、相方となるボールの情報（色と筒の場所）を適切に更新しながら処理していく。
最終的に $N$ 回処理できたかどうかを判定する。

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]);
        int m = Integer.parseInt(sa[1]);
        int[] k = new int[m];
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            List<Integer> l2 = new ArrayList<>();
            k[i] = Integer.parseInt(br.readLine());
            sa = br.readLine().split(" ");
            for (int j = 0; j < k[i]; j++) {
                int a = Integer.parseInt(sa[j]);
                l2.add(a);
            }
            list.add(l2);
        }
        br.close();

        // キー：色、値：筒index
        Map<Integer, Integer> map = new HashMap<>();
        // 処理対象筒index
        List<Integer> target = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            target.add(i);
        }
        // 各筒の次の要素のindex
        int[] idx = new int[m];
        // 操作回数
        int cnt = 0;
        while (!target.isEmpty()) {
            List<Integer> next = new ArrayList<>(); // 次回ループの処理対象
            for (int i : target) {
                int e = list.get(i).get(idx[i]);
                if (map.containsKey(e)) {
                    // 相方がどこかの筒の先頭にある場合
                    cnt++;
                    int j = map.get(e);
                    idx[j]++;
                    if (idx[j] < k[j]) {
                        next.add(j);
                    }
                    map.remove(e);

                    idx[i]++;
                    if (idx[i] < k[i]) {
                        next.add(i);
                    }
                } else {
                    // 相方がまだ見つかっていない場合
                    map.put(e, i);
                }
            }
            target = next;
        }
        // 4
        if (cnt == n) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで22分29秒＋0ペナ。330位。

E - Amusement Park

問題
オーバーフローで1ペナ。

思考過程

PriorityQueueを使うだけでは・・・と思ったが、 $O(KlogN)$ では駄目な制約だった。
$A$ を降順にソートし、例１であれば、 $102$ ～ $101$ が $1$ 個ずつ、 $100$ ～ $51$ が $2$ 個ずつ、 $50$ ～ $1$ が $3$ 個ずつあると捉えて、大きい値を使えるだけ使うようにする。
　
例えば $A_1, A_2$ で $A_3$ より大きい値を合計 $sum$ 回使用済みの場合、次は $A_3$ ～ $(A_4+1)$ の値を $3$ 回ずつ使っていきたい。
$sum + (A_3 - A_4) \times 3 \leq K$ ならば、上記の範囲の値を全部使い切って、次の $A_4$ ～ $(A_5+1)$ の範囲の処理に移る。
そうでなければ、残数を $rem$ として、 $A_3$ ～ $(A_3 - \frac{rem}{3} + 1)$ までは $3$ 個ずつ、余った $0$ ～ $2$ 個は $(A_3 - \frac{rem}{3})$ となる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        Arrays.sort(a);
        reverse(a);

        long ans = 0;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            long d = a[i - 1] - a[i];
            long d2 = d * i;
            if (sum + d2 <= k) {
                // 4
                long val = (a[i - 1] + a[i] + 1) * d2 / 2;
                ans += val;
                sum += d2;
            } else {
                // 5
                int rem = k - sum;
                int t = rem / i;
                long val = (a[i - 1] * 2 - t + 1) * t * i / 2;
                ans += val;
                rem %= i;
                val = (a[i - 1] - t) * rem;
                ans += val;
                break;
            }
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    static void reverse(long[] a) {
        for (int i = 0; i < a.length / 2; i++) {
            long tmp = a[i];
            a[i] = a[a.length - 1 - i];
            a[a.length - 1 - i] = tmp;
        }
    }
}

ここまで35分37秒＋1ペナ。280位。

F - Max Sum Counting

問題
$B$ の方も $A$ と同じインデックスの集合内の最大値だと勘違いして30分近く溶かした。。。
正しい問題を認識してからACするまでは10分くらい。

思考過程

何らかの順でソートして、前から順に見ていける形にできないか考える。
$B$ の方は、合計として現れる値を数え上げるならやっぱりナップサックDPのようなことはするのではないかと思う。
$A$ の昇順にペアソートした上で、 $B$ についてナップサックDPを行い、「 $dp[i][j]:=i$ 番目までで合計が $j$ の通り数」とした内の $j=1$ ～ $A_i$ のみを答えに足していけばよさそう。
なお、 $i$ 番目について答えに足す値は、 $B_i$ を使う場合（つまり $A_i$ を使う場合）の通り数のみとすることで、重複を排除する。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        int mod = 998244353;
        Arrays.sort(arr, (o1, o2) -> o1.a - o2.a);

        long ans = 0;
        long[] dp = new long[5001];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            Obj o = arr[i];
            long[] wk = new long[5001];
            for (int j = 5000 - o.b; j >= 0; j--) {
                wk[j + o.b] += dp[j];
                dp[j + o.b] += dp[j];
                dp[j + o.b] %= mod;
            }
            for (int j = 1; j <= o.a; j++) {
                ans += wk[j];
            }
            ans %= mod;
        }
        System.out.println(ans);
    }

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

ここまで74分27秒＋1ペナ。515位。

G - 01Sequence

問題
実装ミスにより、無限ループが発生するケースがあって1ペナ。

思考過程

区間スケジューリング問題のような要領で、 $R$ の降順でソートして $X$ に満たない分を右から順に $1$ で埋めるようにすれば条件は満たせそう。
ただし、単純にやれば $O(NM)$ なので、右から順に埋める際に既に $1$ にしたところは見ない工夫をしたい。
　
$L$ ～ $R$ の範囲に既にある $1$ の数は、BITを使って取得する。
二度見ないためには、次に調べるべきindexを管理する配列を用意し（ $next[i]$ を $i-1$ で初期化）、例えば $R$ ～ $L$ の範囲を $1$ に変えたら、 $next[R+1]$ を $L-1$ にする更新を行う。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        // rの降順、xの降順
        Arrays.sort(arr, (o1, o2) -> {
            if (o1.r != o2.r) {
                return o1.r - o2.r;
            }
            return o2.x - o1.x;
        });
        FenwickTree ft = new FenwickTree(n);

        int[] ans = new int[n];
        int[] next = new int[n + 1];
        for (int i = 1; i < n; i++) {
            next[i] = i - 1;
        }
        for (Obj o : arr) {
            long sum = ft.sum(o.l, o.r); // 3
            if (sum < o.x) {
                long rem = o.x - sum;
                int idx = o.r - 1;
                while (rem > 0) {
                    if (ans[idx] == 0) {
                        ans[idx] = 1;
                        ft.add(idx, 1);
                        rem--;
                    }
                    idx = next[idx];
                }
                next[o.r] = idx; // 4
            }
        }

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

    static class Obj {
        int l, r, x;
    }
}

// 以下ACLを移植したFenwickTree

提出
ここまで93分57秒＋2ペナ。312位。

ACを見届けていたら残り5分もなく、正解者数からして解ける気は全くしなかったので、H問題は開くこともせず。

最終結果：ABCDEFGの7完、103分57秒、330位、パフォーマンス2008相当
レート変動：2034（Unrated）

誤読とペナさえなければほぼ2400出ていたくらいのスピードで解けたので、まあ上出来だったかなと思う。
でもAとDはもっと早く解きたかった。