京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)(Rated範囲外)

コンテスト前のレート:2023
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:327位(2000点、75分39秒)

A - 484558

問題

思考過程
  1. とりあえずInteger.toHexStringを使ってみる。
  2. 小文字になってしまうので大文字に変換し、さらに1桁なら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();
        sc.close();

        String s = Integer.toHexString(n);
        s = s.toUpperCase();
        if (s.length() == 1) {
            s = "0" + s;
        }
        System.out.println(s);
    }
}

ここまで1分32秒+0ペナ。151位。


B - Maintain Multiple Sequences

問題
なんとなくListを使ってしまったが、配列でもよかった。

思考過程
  1. aの入力をListのListの形で受け取る。
  2. Listのs_i番目のt_i番目を出力する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

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 q = Integer.parseInt(sa[1]);

        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            int l = Integer.parseInt(sa[0]);
            List<Integer> wk = new ArrayList<>(l);
            for (int j = 0; j < l; j++) {
                wk.add(Integer.parseInt(sa[j + 1]));
            }
            list.add(wk);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int s = Integer.parseInt(sa[0]) - 1;
            int t = Integer.parseInt(sa[1]) - 1;
            pw.println(list.get(s).get(t));
        }
        pw.flush();
        br.close();
    }
}

ここまで4分05秒+0ペナ。284位。


C - Manga

問題
考慮漏れがないかかなり不安になり、実装も手間取った。

思考過程
  1. 入力を素直に配列で受け取ってソートして、適宜後ろから売りながら前から見ていけばいいかと思ったが、\{1, 2, 2, 2, 2, 4, 5\}のように後ろの方が1冊しかないと前の方を売らないといけない場合もある。
    結局TreeMap<巻数、冊数>の形で持っておいた方が処理しやすそう。
     
  2. まず重複は1冊を残して全部売れる冊数に加算する。
  3. そうしたらあとは抜けがあった際に上記2.を2ずつ消費していき、それでも足りなくなったら後ろから売っていく貪欲で問題なさそう。
import java.io.BufferedReader;
import java.io.InputStreamReader;
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(" ");
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(sa[i]);
            map.put(a, map.getOrDefault(a, 0) + 1);
        }
        br.close();

        int s = 0; // 売れる数
        for (int v : map.values()) {
            s += v - 1;
        }

        int ans = 0;
        label:
        for (int i = 1; ; i++) {
            if (map.containsKey(i)) {
                ans = i;
            } else if (s >= 2) {
                s -= 2;
                ans = i;
            } else {
                while (s < 2) {
                    if (map.isEmpty()) {
                        break label;
                    }
                    int k = map.pollLastEntry().getKey();
                    if (k < i) {
                        break label;
                    }
                    s++;
                }
                if (s >= 2) {
                    s -= 2;
                    ans = i;
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで13分21秒+0ペナ。203位。


D - Flip and Adjust

問題

思考過程
  1. DP[i][j]:=i番目までで総和をjにできるか」をする。
  2. true/falseの代わりに遷移元'H'か'T'を持たせてしまうことにする。
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 s = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        sc.close();

        char[][] dp = new char[n + 1][s + 1];
        dp[0][0] = 'A';
        for (int i = 0; i < n; i++) {
            // 表を選んだ場合
            for (int j = s - a[i]; j >= 0; j--) {
                if (dp[i][j] != '\u0000') {
                    dp[i + 1][j + a[i]] = 'H';
                }
            }
            // 裏を選んだ場合
            for (int j = s - b[i]; j >= 0; j--) {
                if (dp[i][j] != '\u0000') {
                    dp[i + 1][j + b[i]] = 'T';
                }
            }
        }

        if (dp[n][s] == '\u0000') {
            System.out.println("No");
        } else {
            System.out.println("Yes");
            StringBuilder sb = new StringBuilder();
            int x = s;
            for (int i = n; i > 0; i--) {
                sb.append(dp[i][x]);
                if (dp[i][x] == 'H') {
                    x -= a[i - 1];
                } else {
                    x -= b[i - 1];
                }
            }
            sb.reverse();
            System.out.println(sb.toString());
        }
    }
}

ここまで20分27秒+0ペナ。137位。


E - Subsequence Path

問題
問題を理解したらやるだけだった。

思考過程
  1. 各頂点までの最短経路を始点のみ0、その他をINFで初期化する。
  2. E_iを順に適用(頂点B_{E_i}に対し、dist_{B_{E_i}}とdist_{A_{E_i}}+C_{E_i}のminを取る)させていく。
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]);
        int k = Integer.parseInt(sa[2]);

        Hen[] arr = new Hen[m];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            int c = Integer.parseInt(sa[2]);
            arr[i] = new Hen(a, b, c);
        }

        sa = br.readLine().split(" ");
        int[] e = new int[k];
        for (int i = 0; i < k; i++) {
            e[i] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        long inf = 100000000000000000L;
        long[] d = new long[n];
        Arrays.fill(d, inf);
        d[0] = 0;
        for (int i = 0; i < k; i++) {
            Hen h = arr[e[i]];
            if (d[h.a] < inf) {
                d[h.b] = Math.min(d[h.b], d[h.a] + h.c);
            }
        }
        if (d[n - 1] == inf) {
            System.out.println(-1);
        } else {
            System.out.println(d[n - 1]);
        }
    }

    static class Hen {
        int a, b, c;

        public Hen(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
}

ここまで31分57秒+0ペナ。139位。


F - XOR on Grid Path

問題
考察1~2分、実装に15分。

思考過程
  1. 各マスに対しあり得る値とその通り数を保持しながら左上から右下へ調べていくと、1マス進むごとにあり得る値の種類数が2倍になっていき、最終的に2^{2N-1}ほどになってしまう。
  2. 半分(右上から左下の対角線上)までならば2^Nで済むので、左上と右下から半分全列挙を行う。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
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();
        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        sc.close();

        List<List<Map<Integer, Integer>>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            List<Map<Integer,Integer>> wk = new ArrayList<>(n);
            for (int j = 0; j < n; j++) {
                wk.add(new HashMap<>());
            }
            list.add(wk);
        }
        list.get(0).get(0).put(a[0][0], 1);
        list.get(n - 1).get(n - 1).put(a[n - 1][n - 1], 1);

        // 左上から半分(対角線上含む)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i; j++) {
                Map<Integer, Integer> to = list.get(i).get(j);
                if (i > 0) {
                    Map<Integer, Integer> from = list.get(i - 1).get(j);
                    for (int k : from.keySet()) {
                        int k1 = k ^ a[i][j];
                        to.put(k1, to.getOrDefault(k1, 0) + from.get(k));
                    }
                }
                if (j > 0) {
                    Map<Integer, Integer> from = list.get(i).get(j - 1);
                    for (int k : from.keySet()) {
                        int k1 = k ^ a[i][j];
                        to.put(k1, to.getOrDefault(k1, 0) + from.get(k));
                    }
                }
            }
        }

        // 右下から半分(対角線上除く)
        for (int i = n - 1; i > 0; i--) {
            for (int j = n - 1; j >= n - i; j--) {
                Map<Integer, Integer> to = list.get(i).get(j);
                if (i < n - 1) {
                    Map<Integer, Integer> from = list.get(i + 1).get(j);
                    for (int k : from.keySet()) {
                        int k1 = k ^ a[i][j];
                        to.put(k1, to.getOrDefault(k1, 0) + from.get(k));
                    }
                }
                if (j < n - 1) {
                    Map<Integer, Integer> from = list.get(i).get(j + 1);
                    for (int k : from.keySet()) {
                        int k1 = k ^ a[i][j];
                        to.put(k1, to.getOrDefault(k1, 0) + from.get(k));
                    }
                }
            }
        }

        long ans = 0;
        for (int i = 1; i < n; i++) {
            Map<Integer, Integer> from1 = list.get(i - 1).get(n - i);
            Map<Integer, Integer> from2 = list.get(i).get(n - i - 1);
            Map<Integer, Integer> to = list.get(i).get(n - i);
            for (int k : to.keySet()) {
                int v = to.get(k);
                int v1 = from1.getOrDefault(k, 0);
                int v2 = from2.getOrDefault(k, 0);
                ans += (long) v * v1;
                ans += (long) v * v2;
            }
        }
        System.out.println(ans);
    }
}

ここまで49分18秒+0ペナ。126位。



Gは行列累乗っぽいけど行列の作り方を考える気もしない。

Exはなんか場合分け頑張るだけでは?とばかりにとりあえず0 \leq B \leq Aとなるように入力を読み替えた上で場合分けを頑張るも、4/18しか通らず。



終結果:ABCDEFの6完2000点、49分18秒、197位、パフォーマンス2303相当
レート変動:2023(Unrated)


Exは本当にただの場合分けっぽかったので、40分ほどもかけて解けなかったのは辛い。
AHC014で散々考慮漏れ探すのに苦労していたことに比べれば大したことないだろうと思ったのに。

Fまでは全体的に考察はスムーズだったが実装が遅めだった感じ。ミスがなくてまあ良かった。