東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）(Rated範囲外)

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

A - 2^N

問題

思考過程

1. は「1<<N」で計算することができる。
2. int型に収まる制約のため、「1L<<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();

        System.out.println(1 << n);
    }
}

ここまで0分18秒＋0ペナ。55位。

B - Batters

問題

思考過程

1. 各マスに存在する駒の数をシミュレーションすることを考える。
2. 回の各ターンでは、マスを加算し、マスの値をに移動させる。
3. この際、が大きい順に処理することで、二重に移動させることを防げる。
4. 配列のサイズは適当により少し大きめに用意しておき、回の操作後はマス以上の値を合計する。

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];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int[] c = new int[10];
        for (int i = 0; i < n; i++) {
            c[0]++;
            for (int j = 3; j >= 0; j--) {
                c[j + a[i]] += c[j];
                c[j] = 0;
            }
        }

        int ans = 0;
        for (int i = 4; i < c.length; i++) {
            ans += c[i];
        }
        System.out.println(ans);
    }
}

ここまで3分51秒＋0ペナ。242位。

C - Filling 3x3 array

問題

思考過程

1. なんとなく入力からを引いて、～で考えてみる。
2. 上の行を決めれば行目が決まるので、の全探索でぎりぎりいけそう？
3. よく考えたら、上の行についても左のマスを決めたらマス目は計算で求められたので、だった。
4. 上行のマス目、行目の各マスを計算で求め、それらが全て以上で、行目の合計が合えば答えをカウントアップする。（以上、合計が一致の片方だけしか入れていなくてサンプルが合わないとかをやっていて時間ロスした）

import java.util.Scanner;

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

        int ans = 0;
        // 1行目
        for (int i = 0; i <= h[0]; i++) {
            for (int i2 = 0; i2 <= h[0] - i; i2++) {
                int i3 = h[0] - i - i2;

                // 2行目
                for (int j = 0; j <= h[1]; j++) {
                    for (int j2 = 0; j2 <= h[1] - j; j2++) {
                        int j3 = h[1] - j - j2;

                        // 3行目
                        int k = w[0] - i - j;
                        int k2 = w[1] - i2 - j2;
                        int k3 = w[2] - i3 - j3;

                        // 整合性チェック
                        if (j3 >= 0 && k >= 0 && k2 >= 0 && k3 >= 0 &&
                                k + k2 + k3 == h[2]) {
                            ans++;
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで15分55秒＋0ペナ。638位。

D - Union of Interval

問題
わざわざ難しいやり方したっぽい。

思考過程

1. TreeMap＜L、R＞を頑張って更新していくことを考える。
2. 順不同だと既存区間との位置関係で場合分けが多すぎて大変なので、かでソートして処理することにする。
3. どちらが楽かはよくわからなかったが、区間スケジューリング問題でよくやるでソートをしてみることにする。
   　
4. 以下のキーが存在しない場合は、全体をの区間で置き換える。
5. 以下で最も近い区間がと重複すればマージ、そうでなければ単純に追加？　→WA
6. 以上の部分に存在する区間は全部削除する必要があった。　→処理順序に問題がありREの後修正してAC

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.PriorityQueue;
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());
        // 3
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o1.r - o2.r);
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.l = Integer.parseInt(sa[0]);
            o.r = Integer.parseInt(sa[1]);
            que.add(o);
        }
        br.close();

        TreeMap<Integer, Integer> map = new TreeMap<>();
        while (!que.isEmpty()) {
            Obj o = que.poll();
            Integer k = map.floorKey(o.l);
            if (k == null) {
                // 4
                map.clear();
                map.put(o.l, o.r);
            } else {
                int v = map.get(k);
                // 6
                map.tailMap(o.l).clear();
                // 5
                if (o.l <= v) {
                    map.put(k, o.r);
                } else {
                    map.put(o.l, o.r);
                }
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i : map.keySet()) {
            pw.println(i + " " + map.get(i));
        }
        pw.flush();
    }

    static class Obj {
        int l, r;
    }
}

なお、でソートした場合は以下のようになり、こちらの方が削除することを考えなくてよくて簡単だった。

        TreeMap<Integer, Integer> map = new TreeMap<>();
        Obj f = que.poll();
        map.put(f.l, f.r);
        while (!que.isEmpty()) {
            Obj o = que.poll();
            Integer k = map.floorKey(o.l);
            int v = map.get(k);
            if (o.l <= v) {
                map.put(k, Math.max(o.r, v));
            } else {
                map.put(o.l, o.r);
            }
        }

ここまで28分21秒＋1ペナ。902位。

E - Takahashi's Anguish

問題
実装が遅くて下手くそ。

思考過程

1. とりあえずからにコストの有向辺を張ったグラフを作ってみる。
2. 各サイクルの中から最小コストの辺をつずつ特定していけばよさそう。
   　
3. サイクル検出は、辿った頂点の履歴を持ちながらDFSをして、次の頂点が履歴に存在するかどうかという判定をする。
4. 履歴の内、サイクルが始まる頂点以降から最小値を求める。
5. 全頂点（の内未訪問のもの）を始点にして上記のDFSを試す。
6. 例２のように数字のの字のような形をしている場合、始点が未訪問の条件だけでは同じサイクルを何度も調べているため、DFS中でも訪問済み頂点に達したら終了させる。

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

public class Main {
    static int[] x, c;
    static boolean[] v;

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

        v = new boolean[n];
        long ans = 0;
        // 5
        for (int i = 0; i < n; i++) {
            if (!v[i]) {
                ans += dfs(i, new LinkedHashSet<>());
            }
        }
        System.out.println(ans);
    }

    static int dfs(int i, LinkedHashSet<Integer> his) {
        v[i] = true;
        // 3
        if (his.contains(x[i])) {
            // 4
            boolean flg = false;
            int min = c[i];
            for (int a : his) {
                // サイクルの開始箇所を特定
                if (a == x[i]) {
                    flg = true;
                }
                if (flg) {
                    min = Math.min(min, c[a]);
                }
            }
            return min;
        // 6
        } else if (v[x[i]]) {
            return 0;
        } else {
            his.add(i);
            int res = dfs(x[i], his);
            his.remove(i);
            return res;
        }
    }
}

ここまで50分17秒＋1ペナ。668位。

F、G、Exは全部問題は読んだが全然わからず。
解説をチラ見してどれも自力では解けそうになかった。

最終結果：ABCDEの5完1500点、60分17秒、856位、パフォーマンス1565相当
レート変動：2019（Unrated）

Bはぎりぎり許容範囲くらいで、CとEは完全に実装が遅すぎ。
Dはこういうのを見るとすぐTreeMapで管理していきたくなってしまうのだが、いもす法くらいは思い付きたかった。
まあクエリの度に出力するような形式であれば何らかのデータ構造で管理することになるとは思うが。