パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 273)

コンテスト前のレート:1965
レート通りのパフォーマンスが得られる順位:313位(1500点、59分01秒)

A - A Recursive Function

問題
今までのA問題と雰囲気が全然違ってびっくりした。
タイトルが再帰関数だったことに後から気付いた。

思考過程
  1. 問題文通りの漸化式を元にf(1)f(N)を順に求めていく。
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();

        int[] a = new int[n + 1];
        a[0] = 1;
        for (int i = 1; i <= n; i++) {
            a[i] = i * a[i - 1];
        }
        System.out.println(a[n]);
    }
}

ここまで1分36秒+0ペナ。1464位。


B - Broken Rounding

問題
結構悩んだ。
後から思えば、BigIntegerを使えばよかったかも。

思考過程
  1. 数値として扱うと4以下か5以上か判定したい桁の値を取り出すのがちょっとめんどくさそう。
  2. 文字列として扱うと特定の桁の値は取り出しやすいが、桁数が足りなかったり繰り上がりが発生したりする場合にかなり面倒。
  3. 基本は数値で扱い、四捨五入部分は10^{i+1}で割った余りを文字列化して先頭桁を調べることにする。(本当は文字列化ではなく10^iで割った方が正しくて実装量も少なかったが、頭回っていなかった。)
import java.util.Scanner;

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

        long ans = Long.parseLong(x);
        long b = 1;
        for (int i = 0; i < k; i++) {
            long b2 = b * 10;
            long d = ans % b2;
            ans -= d;
            String s = String.valueOf(d);
            if (s.charAt(0) >= '5') { // d / b >= 5 でよかった
                ans += b2;
            }
            b = b2;
        }
        System.out.println(ans);
    }
}

ここまで9分29秒+0ペナ。1184位。


C - (K+1)-th Largest Number

問題
種類数ではなく個数と勘違いし、下記1.と2.の間で迷走していたがそこは省略。

思考過程
  1. ソートして後ろから上手い具合に数えていきたい。
  2. Setに追加しながら「K= Setの要素数」の箇所をカウントアップしていけばよさそう。
  3. A_iと同じ値が既にSetに存在する場合は-1する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

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

        Arrays.sort(a);
        Set<Integer> set = new HashSet<>();
        int[] ans = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int cnt = set.size();
            if (set.contains(a[i])) {
                cnt--;
            }
            ans[cnt]++;
            set.add(a[i]);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            pw.println(ans[i]);
        }
        pw.flush();
    }
}

ここまで19分37秒+0ペナ。1007位。

ここで一度順位表を見たが、やっぱりBとCで手間取り過ぎ。
でもDはまだ2桁しか解かれていない。

D - LRUD Instructions

問題

思考過程
  1. グリッドが非常に大きいので、壁が存在する行や列についてのみ情報を持つようにする。
  2. Map<行、TreeSet<列>>および行列を入れ替えた形で情報を持っておけば、現在地から特定の方向に最も近い壁の位置を対数オーダーで取得できる。
  3. あとは実際にシミュレーションをする。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        int rs = Integer.parseInt(sa[2]);
        int cs = Integer.parseInt(sa[3]);
        int n = Integer.parseInt(br.readLine());
        // 1, 2
        Map<Integer, TreeSet<Integer>> mapx = new HashMap<>();
        Map<Integer, TreeSet<Integer>> mapy = new HashMap<>();
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            int r = Integer.parseInt(sa[0]);
            int c = Integer.parseInt(sa[1]);

            TreeSet<Integer> set = mapx.get(r);
            if (set == null) {
                set = new TreeSet<>();
                mapx.put(r, set);
            }
            set.add(c);

            set = mapy.get(c);
            if (set == null) {
                set = new TreeSet<>();
                mapy.put(c, set);
            }
            set.add(r);
        }

        // 3
        int q = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int l = Integer.parseInt(sa[1]);
            if (sa[0].equals("L")) {
                // rs行目の情報
                TreeSet<Integer> set = mapx.get(rs);
                // cs列目より左の最初の壁(存在しなければグリッドの端)
                int k = 0;
                if (set != null && set.lower(cs) != null) {
                    k = set.lower(cs);
                }
                cs = Math.max(cs - l, k + 1);

            } else if (sa[0].equals("R")) {
                TreeSet<Integer> set = mapx.get(rs);
                int k = w + 1;
                if (set != null && set.higher(cs) != null) {
                    k = set.higher(cs);
                }
                cs = Math.min(cs + l, k - 1);

            } else if (sa[0].equals("U")) {
                TreeSet<Integer> set = mapy.get(cs);
                int k = 0;
                if (set != null && set.lower(rs) != null) {
                    k = set.lower(rs);
                }
                rs = Math.max(rs - l, k + 1);

            } else {
                TreeSet<Integer> set = mapy.get(cs);
                int k = h + 1;
                if (set != null && set.higher(rs) != null) {
                    k = set.higher(rs);
                }
                rs = Math.min(rs + l, k - 1);
            }
            pw.println(rs + " " + cs);
        }
        pw.flush();
        br.close();
    }
}

ここまで32分29秒+0ペナ。266位。

だいぶ挽回できた。

E - Notebook

問題

思考過程
  1. SAVEやLOADでリストを複製したりしていたらどう考えてもTLEやMLE。
  2. DELETEの場合も削除せず手前の要素を追加していったらどうか?
  3. どこまで戻っているかを管理するのが大変そうだし、そもそもLOADの後ADDやDELETEがあると結局リストを枝分かれさせる必要が生じる。
     
  4. 枝分かれ?なんか木構造で扱うことができれば上手くいきそうな気がする。以下の通りでできた。
    • ADD:現在地から新しい子を追加してそこに移動する。
    • DELETE:現在地を親に移動する。
    • SAVE:yに対応する頂点を保持する。
    • LOAD:zに対応する頂点(なければ根)に移動する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

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());

        Node root = new Node(-1, null);
        Node now = root;
        Map<Integer, Node> map = new HashMap<>();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            // ADD
            if (sa[0].charAt(0) == 'A') {
                int x = Integer.parseInt(sa[1]);
                Node next = new Node(x, now);
                now = next;

            // DELETE
            } else if (sa[0].charAt(0) == 'D') {
                if (now.p != null) {
                    now = now.p;
                }

            // SAVE
            } else if (sa[0].charAt(0) == 'S') {
                int y = Integer.parseInt(sa[1]);
                map.put(y, now);

            // LOAD
            } else {
                int z = Integer.parseInt(sa[1]);
                now = map.getOrDefault(z, root);
            }
            sb.append(now.v).append(' ');
        }
        br.close();

        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    static class Node {
        int v;
        Node p;

        public Node(int v, Node p) {
            this.v = v;
            this.p = p;
        }
    }
}

ここまで54分51秒+0ペナ。211位。



一応FとGを読んでからFに集中することにしたが解けず。

Fは壁もハンマーもゴールも混ぜて原点から負方向にi番目、正方向にj番目まで移動している場合の最小値をDPで求めることまでは思い付いていたが、それを20分かけても実装できず。
左端と右端どちらにいるかという情報が抜けていたし、そこまで気付いてやり直すには1時間くらいかかってしまいそう・・・。



終結果:ABCDEの5完1500点、54分51秒、272位、パフォーマンス2027
レート変動:1965→1971(+6)


今回は一気にレートを戻すチャンスであったようにも思えたが、やっぱりDPが・・・。
あとCまでがもっと早ければパフォ100近く違ったかも。
まあプラスであるだけいいけど。実にRated11回ぶりの黄パフォ。(前回までの10回が橙2、青5、水3)