大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)(Rated範囲外)

ABC

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

A - ^{-1}

問題

思考過程
  1. Pを全探索し、P_i=Xとなった時のiを1-indexedに直して出力する。
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[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextInt();
        }
        sc.close();

        for (int i = 0; i < n; i++) {
            if (p[i] == x) {
                System.out.println(i + 1);
                return;
            }
        }
    }
}

ここまで1分02秒＋0ペナ。385位。


B - Playing Cards Validation

問題

思考過程
  1. 条件1つ目と2つ目は地道に調べる。
  2. 条件3つ目はSを全て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();
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next();
        }
        sc.close();

        Set<String> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(s[i]);

            char a = s[i].charAt(0);
            if (a == 'H' || a == 'D' || a == 'C' || a == 'S') {
            } else {
                System.out.println("No");
                return;
            }

            char b = s[i].charAt(1);
            if (b == 'A' || '2' <= b && b <= '9' ||
                    b == 'T' || b == 'J' || b == 'Q' || b == 'K') {
            } else {
                System.out.println("No");
                return;
            }
        }
        if (set.size() == n) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで5分39秒＋0ペナ。703位。


C - Ladder Takahashi

問題

思考過程
  1. A_iとB_iの間に辺があるとみなしてBFSを行う。
  2. 制約が大きく頂点数分の配列を用意することができないので、隣接リストはMap＜階、移動先階リスト＞の形で持ち、特定の階を訪れたかどうかの判定にはSetを使う。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
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());
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String[] 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);

            list = map.get(b);
            if (list == null) {
                list = new ArrayList<>();
                map.put(b, list);
            }
            list.add(a);
        }
        br.close();

        int ans = 1;
        Set<Integer> set = new HashSet<>();
        Queue<Integer> que = new ArrayDeque<>();
        set.add(1);
        que.add(1);
        while (!que.isEmpty()) {
            int cur = que.poll();
            List<Integer> list = map.get(cur);
            if (list == null) {
                continue;
            }
            for (int next : list) {
                if (set.add(next)) {
                    ans = Math.max(ans, next);
                    que.add(next);
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで11分08秒＋0ペナ。449位。


D - Takahashi's Solitaire

問題
例２が通ったことで全部取り除ける場合も問題ないと勘違いして1ペナ。

思考過程
  1. Aをソートすると、前後の要素と値が2以上離れていない連続した箇所をまとめて取り除けるということになる。
  2. そのような連続した箇所の和のリストを作る。
  3. A_1=0かつA_N=M-1の場合は、和のリストの先頭と末尾はまとめることができる。
  4. 和のリストの中の最大値を、Aの総和から引く。
  5. 0～M-1が全て含まれている場合に2倍にしてしまっていたので、和のリストの要素が1個の場合は先頭と末尾を足さないように修正。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
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 m = Integer.parseInt(sa[1]);
        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        // 1, 2
        Arrays.sort(a);
        List<Long> list = new ArrayList<>();
        long val = 0;
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i];
            val += a[i];
            if (i == n - 1 || a[i] + 2 <= a[i + 1]) {
                list.add(val);
                val = 0;
            }
        }
        // 3. 5
        if (a[0] == 0 && a[n - 1] == m - 1 && list.size() > 1) {
            list.set(0, list.get(0) + list.get(list.size() - 1));
            list.remove(list.size() - 1);
        }

        // 4
        long max = 0;
        for (long e : list) {
            max = Math.max(max, e);
        }
        System.out.println(sum - max);
    }
}

ここまで19分39秒＋1ペナ。166位。


E - Crystal Switches

問題

思考過程
  1. 「スイッチを押していない状態と押している状態それぞれで各頂点にいる場合」の2N個の頂点があるとみなしてダイクストラ法をする。
  2. 遷移はスイッチの押下状態に応じて使える辺の移動と、スイッチがある頂点について押下状態の変更を行う。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

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]);
        List<List<Hen>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        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]);

            list.get(a).add(new Hen(b, c));
            list.get(b).add(new Hen(a, c));
        }
        sa = br.readLine().split(" ");
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < k; i++) {
            set.add(Integer.parseInt(sa[i]) - 1);
        }
        br.close();

        int s = 0;
        long[][] d = new long[2][list.size()];
        Arrays.fill(d[0], Long.MAX_VALUE);
        Arrays.fill(d[1], Long.MAX_VALUE);
        d[0][s] = 0;
        PriorityQueue<Node> que = new PriorityQueue<Node>();
        Node first = new Node(s, 0);
        que.add(first);

        while (!que.isEmpty()) {
            Node cur = que.poll();
            int cx = cur.v / n;
            int cy = cur.v % n;
            if (cur.d > d[cx][cy]) {
                continue;
            }
            // 辺を移動
            for (Hen hen : list.get(cy)) {
                if (cx + hen.c == 1) {
                    long alt = d[cx][cy] + 1;
                    if (alt < d[cx][hen.v]) {
                        d[cx][hen.v] = alt;
                        que.add(new Node(cx * n + hen.v, alt));
                    }
                }
            }
            // スイッチを押す
            if (set.contains(cy)) {
                if (d[1 - cx][cy] > d[cx][cy]) {
                    d[1 - cx][cy] = d[cx][cy];
                    que.add(new Node((1 - cx) * n + cy, d[cx][cy]));
                }
            }
        }
        long ans = Math.min(d[0][n - 1], d[1][n - 1]);
        if (ans == Long.MAX_VALUE) {
            ans = -1;
        }
        System.out.println(ans);
    }

    static class Hen {
        int v, c;

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

    static class Node implements Comparable<Node> {
        int v;
        long d;

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

        public int compareTo(Node o) {
            return Long.compare(d, o.d);
        }
    }
}

ここまで32分05秒＋1ペナ。179位。



Fは行と列を独立に考え、0を無視してまずは行について
1行目最小\leq 1行目最大\leq 2行目最小\leq2行目最大\leq \cdots
を満たすかどうか調べる。
その後各行内の大小関係を元に必要最小限の辺を張ってトポロジカルソートできるかどうかを調べようとしたが、同じ値が複数存在した場合の辺の張り方が不十分であったらしい。

その後、誤読が原因かと勘違いして問題文を読み直し、0を相異なる値に変えなければならないとかえって誤読してさらにハマった。
誤読したおかげで、最後は3, 3, 3のような行と0, 3, 0のような行のどちらを先にすればよいか決めるのが困難だとか思いながら終わった。

Gはあまり考えていないが、「dp[i][j][k]:=i回目の操作で頂点jにいてレベルがkの確率」のようなO(NK^2)くらいになりそうな方法しか思い浮かばず。
明らかに計算量が駄目なのでこれでできているのかもまともに考えていない。



最終結果：ABCDEの5完1500点、37分05秒、309位、パフォーマンス2054相当
レート変動：2000（Unrated）


できればF解きたかった気もしなくはないが、まあ普通くらいの結果なのでヨシ。
さっさとAHC016に戻る。