NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）(Rated範囲外)

ABC

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

A - Median?

問題

思考過程
  1. a \leq b \leq cまたはc \leq b \leq aの場合に"Yes"。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        sc.close();

        if (a <= b && b <= c || c <= b && b <= a) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで1分06秒＋0ペナ。233位。


B - Distance Between Tokens

問題

思考過程
  1. 2点のマンハッタン距離（行indexの差と列indexの差の和）を求める。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        char[][] s = new char[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();

        List<Integer> x = new ArrayList<>();
        List<Integer> y = new ArrayList<>();
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (s[i][j] == 'o') {
                    x.add(i);
                    y.add(j);
                }
            }
        }
        int ans = Math.abs(x.get(0) - x.get(1)) + Math.abs(y.get(0) - y.get(1));
        System.out.println(ans);
    }
}

ここまで3分32秒＋0ペナ。277位。


C - Max - Min Query

問題

思考過程
  1. 先頭要素と末尾要素が取得できるMultiSet（JavaにはないのでTreeMap＜値、個数＞を使って自作）を用いて管理する。
  2. 削除するクエリは、追加が1個ずつなので1個ずつ削除しても全体でO(Q)回の操作で済む。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine());
        MultiTreeSet<Integer> set = new MultiTreeSet<>();
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            int t = Integer.parseInt(sa[0]);
            if (t == 1) {
                int x = Integer.parseInt(sa[1]);
                set.add(x);
            } else if (t == 2) {
                int x = Integer.parseInt(sa[1]);
                int c = Integer.parseInt(sa[2]);
                int min = Math.min(c, set.map.getOrDefault(x, 0));
                for (int j = 0; j < min; j++) {
                    set.remove(x);
                }
            } else {
                pw.println(set.last() - set.first());
            }
        }
        pw.flush();
        br.close();
    }

    // 以下ライブラリ（不要メソッドを除いている）

    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--;
            }
        }

        T first() {
            return map.firstKey();
        }

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

ここまで9分31秒＋0ペナ。483位。


D - FizzBuzz Sum Hard

問題
同じような実装が並んでいて、関数化してもよかったと思った頃にはほとんど実装終わってた。

思考過程
  1. 全体の合計-Aの倍数の合計-Bの倍数の合計+A,B両方の倍数の合計。
import java.math.BigInteger;
import java.util.Scanner;

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

        long total = n * (n + 1) / 2;

        long ca = n / a;
        long va = ca * (ca + 1) / 2 * a;

        long cb = n / b;
        long vb = cb * (cb + 1) / 2 * b;

        long ab = lcm(a, b);
        long cab = n / ab;
        long vab = cab * (cab + 1) / 2 * ab;

        long ans = total - va - vb + vab;
        System.out.println(ans);
    }

    // 以下ライブラリ

    static long lcm(long a, long b) {
        BigInteger ba = BigInteger.valueOf(a);
        BigInteger bb = BigInteger.valueOf(b);
        return ba.multiply(bb).divide(ba.gcd(bb)).longValue();
    }
}

ここまで12分41秒＋0ペナ。222位。


E - Distance Sequence

問題
順位表では1ペナがたくさん並んでいたので、多くの人が同じミスをしたのだと思う。

思考過程
  1. DP[i][j]:=長さiで最後の要素がjである数列の通り数。
  2. 遷移は1～(j-K)と(j+K)～Mの和がほしいので、両側から累積和を取っておく。　→2ケースWA
  3. K=0の場合に二重で足していた。
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 k = sc.nextInt();
        sc.close();

        int mod = 998244353;
        long[][] dp = new long[n][m];
        for (int i = 0; i < m; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            long[] sum1 = new long[m + 1];
            for (int j = 0; j < m; j++) {
                sum1[j + 1] = sum1[j] + dp[i - 1][j];
            }
            long[] sum2 = new long[m + 1];
            for (int j = m - 1; j >= 0; j--) {
                sum2[j] = sum2[j + 1] + dp[i - 1][j];
            }
            for (int j = 0; j < m; j++) {
                dp[i][j] += sum1[Math.max(j - k + 1, 0)];
                if (k == 0) {
                    dp[i][j] += sum2[Math.min(j + k + 1, m)];
                } else {
                    dp[i][j] += sum2[Math.min(j + k, m)];
                }
                dp[i][j] %= mod;
            }
        }

        long ans = 0;
        for (int i = 0; i < m; i++) {
            ans += dp[n - 1][i];
        }
        ans %= mod;
        System.out.println(ans);
    }
}

ここまで22分08秒＋1ペナ。146位。


F - Operations on a Matrix

問題
誤読した上、実装こんがらがって時間かかった。

思考過程
  1. 行と列を分けて管理する。
  2. クエリ１はBITを使って位置lに+x、r+1に-xを足す。
  3. クエリ２もBITを使って位置iに+x、i+1に-xを足す？　→加算ではなく置き換えだった。
    　
  4. クエリ３の際は、i行目に対する直近のクエリ２のxと、そのクエリ２以降に発生した分のみのクエリ１の情報が知りたい。
  5. 事前に各クエリ３に対する直近のクエリ２を特定しておき、そのクエリ２時点でクエリ１情報を引いておくことで、以降に発生した分のみのクエリ１情報が取得できることになる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
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 m = Integer.parseInt(sa[1]);
        int q = Integer.parseInt(sa[2]);
        int[] t = new int[q];
        int[] a = new int[q];
        int[] b = new int[q];
        int[] c = new int[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            t[i] = Integer.parseInt(sa[0]);
            a[i] = Integer.parseInt(sa[1]);
            b[i] = Integer.parseInt(sa[2]);
            if (t[i] == 1) {
                c[i] = Integer.parseInt(sa[3]);
            }
        }
        br.close();

        // Map＜クエリ２のNo、クエリ２の値＞を行数分（値の方は不要だった）
        List<TreeMap<Integer, Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new TreeMap<>());
        }
        for (int i = 0; i < q; i++) {
            if (t[i] == 2) {
                list.get(a[i] - 1).put(i, b[i]);
            }
        }

        // 各クエリ２に対応するクエリ３のリスト
        List<List<Integer>> target = new ArrayList<>();
        for (int i = 0; i < q; i++) {
            target.add(new ArrayList<>());
        }
        for (int i = 0; i < q; i++) {
            if (t[i] == 3) {
                // クエリ３に対応するクエリ２を特定
                TreeMap<Integer, Integer> map = list.get(a[i] - 1);
                Integer key = map.lowerKey(i);
                if (key == null) {
                    key = -1;
                } else {
                    // 特定したクエリ２にクエリ３を紐付け
                    target.get(key).add(i);
                }
            }
        }

        FenwickTree ft = new FenwickTree(m + 1);
        PrintWriter pw = new PrintWriter(System.out);
        long[] vx = new long[q];
        for (int i = 0; i < q; i++) {
            if (t[i] == 1) {
                ft.add(a[i] - 1, c[i]);
                ft.add(b[i], -c[i]);

            } else if (t[i] == 2) {
                // クエリ２に対応するクエリ３について、
                // クエリ１の情報を引いておく
                List<Integer> wk = target.get(i);
                for (int e : wk) {
                    vx[e] = b[i] - ft.sum(b[e]);
                }
            } else {
                long vy = ft.sum(b[i]);
                long ans = vx[i] + vy;
                pw.println(ans);
            }
        }
        pw.flush();
    }
}

// 以下ACLを移植したFenwickTree

提出
ここまで75分43秒＋1ペナ。371位。



Gも時間をかければ解けそうではあったが、実装できず。
公式解説の赤色の部分だけだったら、未確定部分のリストから末尾の要素を取り除いて答えのリストに追加していく形でできそうだと思ったが、青色部分の処理に手間取っている間に終了。
余計なことを考えずに愚直に処理すればよかっただけであることに気付かなかった。



最終結果：ABCDEFの6完2000点、80分43秒、445位、パフォーマンス1890相当
レート変動：2008（Unrated）


今日は細かい実装で頭が回らない辺り、疲れが取れてなさそうな感じ。
いつもそんなこと言っている気もしてきたが、ここ数ヶ月ずっと残業多い状態が続いているので・・・。