AtCoder Beginner Contest 252(Rated範囲外)

A - ASCII code
- 思考過程
B - Takahashi's Failure
- 思考過程
C - Slot Strategy
- 思考過程
D - Distinct Trio
- 思考過程
E - Road Reduction
- 思考過程
F - Bread
- 思考過程

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

A - ASCII code

思考過程

'a'に $(N-97)$ を足して・・・とか考えたりしてみるが、その前に $N$ をそのままcharにキャストしたらどうなるんだっけと試してみる。
合っていそうなので単純なキャストだけで提出。

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((char) n);
    }
}

ここまで0分45秒＋0ペナ。556位。

B - Takahashi's Failure

問題

思考過程

$A_i$ の最大値を求めておく。
$A_i$ を全て調べ、「 $A_i=$ 最大値かつ $i$ が $B$ に含まれている」ものがあれば"Yes"。
「 $i$ が $B$ に含まれている」の部分を判定するためには、 $B$ はSetの形で持っておくとやりやすい。

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();
        int k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        // 3
        Set<Integer> b = new HashSet<>();
        for (int i = 0; i < k; i++) {
            b.add(sc.nextInt() - 1);
        }
        sc.close();

        // 1
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, a[i]);
        }

        // 2
        for (int i = 0; i < n; i++) {
            if (a[i] == max && b.contains(i)) {
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }
}

ここまで3分13秒＋0ペナ。260位。

C - Slot Strategy

問題
実装手間取った。

思考過程

どの数字を合わせるかを全探索する。
合わせたい数字について、止めたい秒数ごとに該当リールが何個あるかを数えておく。
時間を進めていき、その時間に止めたいリールが残っていたら止めるという貪欲をシミュレーションする。

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 = 10;
        char[][] s = new char[n][m];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();

        int ans = 1000000007;
        // 1
        for (int i = 0; i < m; i++) {
            char c = (char) ('0' + i);
            // 2
            int[] cnt = new int[m];
            for (int j = 0; j < n; j++) {
                for (int j2 = 0; j2 < m; j2++) {
                    if (s[j][j2] == c) {
                        cnt[j2]++;
                        break;
                    }
                }
            }
            // 3
            int rem = n;
            int t = 0;
            while (rem > 0) {
                if (cnt[t % m] > 0) {
                    cnt[t % m]--;
                    rem--;
                }
                t++;
            }
            ans = Math.min(ans, t);
        }
        System.out.println(ans - 1);
    }
}

ここまで12分06秒＋0ペナ。395位。

D - Distinct Trio

問題
解法わかってから振り返ってみると、色々変なところで詰まっていた。
下記思考過程4.まででもう経過時間30分を過ぎていたので、一旦飛ばしてE、Fを解いてから戻ってくる。
20分解けなかったのに戻ってきてから8分ほどでAC。

思考過程

入力を各値の個数の形で受け取ってみると、 $A_i$ の最大値を $M$ として、 $_MC_3$ 通りについて $3$ 種類の個数の積を求めていくことになってしまい、これでは $O(M^3)$ 。
$A_i$ を順番通りに見ていって、「 $DP[i][j]:=i$ 番目を $j$ 個目として選ぶ通り数」を考えてみるが、 $3$ 個目を決める時に同じ値が含まれる通り数を上手く除けそうにない。
$j$ を全探索し、 $j$ より前および後で $A_j$ と異なる要素の個数（ $A_i, A_k$ の候補数）を求めて、その積を足していけば・・・と考えてみるが、 $A_i=A_k$ の場合を数えてしまっていて駄目。
全体から駄目なものを引くのもなんか重複とか発生して難しそう？
　
上記4.をきちんと考え直してみると、まず $A_i, A_j, A_k$ の全てが同じ値の通り数は、各値について個数 $C_3$ 。
$2$ 個が同じ値の通り数は、どの値を $2$ 個にするかを全探索したとして、残りの $1$ 個を何にしたとしても、各値について求めた結果は重複にはならない。
結局、 $_NC_3$ から $3$ 個同じ値の場合と $2$ 個同じ値の場合を引くので求められる。

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 m = 200001;
        int[] c = new int[m];
        for (int i = 0; i < n; i++) {
            c[a[i]]++;
        }

        long ans = nCr(n, 3);
        for (int i = 1; i < m; i++) {
            if (c[i] >= 3) {
                ans -= nCr(c[i], 3);
            }
            if (c[i] >= 2) {
                ans -= nCr(c[i], 2) * (n - c[i]);
            }
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    static long nCr(int n, int r) {
        long val = 1;
        for (int i = 1; i <= r; i++) {
            val = val * (n - i + 1) / i;
        }
        return val;
    }
}

ABCEFDと解いた時点で65分56秒＋1ペナ。401位。

E - Road Reduction

問題

思考過程

クラスカル法をしたのでは、都市 $1$ と直接つながる長めの辺より、迂回ルートとなる短い辺の方が優先され、損する可能性がある。
直接つながる辺を別管理にして、上記のどちらが得かを判定しながらやる？とかは難しそう。
　
そもそもまず元のグラフで最小値を求めようとすると、ダイクストラ法で求まる。
ということはダイクストラ法をして経路復元するだけだった。
実装はダイクストラ法を貼って、辺番号の情報を追加する。（下記コード内の★）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

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]);
        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, i)); // ★
            list.get(b).add(new Hen(a, c, i)); // ★
        }
        br.close();

        int s = 0;
        long[] d = new long[n];
        int[] p = new int[n]; // ★
        Arrays.fill(d, Long.MAX_VALUE);
        d[s] = 0;
        PriorityQueue<Node> que = new PriorityQueue<Node>();
        Node first = new Node(s, 0);
        que.add(first);

        while (!que.isEmpty()) {
            Node cur = que.poll();
            if (cur.d > d[cur.v]) {
                continue;
            }
            for (Hen hen : list.get(cur.v)) {
                long alt = d[cur.v] + hen.c;
                if (alt < d[hen.v]) {
                    d[hen.v] = alt;
                    p[hen.v] = hen.i; // ★
                    que.add(new Node(hen.v, alt));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < n; i++) {
            sb.append(p[i] + 1).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    static class Hen {
        int v, c, i; // ★

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

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

ABCEと解いた時点で44分26秒＋0ペナ。555位。

F - Bread

問題

思考過程

操作を逆にして、切っていくのではなくつなげる時につなげた後の長さ分のコストがかかると見ることにする。
何回もつなげる操作を行うと、それを構成しているパーツに対して操作回数分のコストがかかる形になっていることから、短いものを優先的に操作するとよさそう。
単にPriorityQueueに入れて先頭の $2$ つをくっつけていくだけでは？
例２のように合計が $L$ に満たないケースは、 $L$ を足すことにする。　→半分くらいWA
　
余りが少ない場合は、その部分を早めに操作した方がよさそう。
余り部分も一緒にPriorityQueueに入れてみる。　→AC

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

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]);
        long l = Long.parseLong(sa[1]);
        sa = br.readLine().split(" ");
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(sa[i]);
        }
        br.close();

        PriorityQueue<Long> que = new PriorityQueue<>();
        long sum = 0;
        for (int i = 0; i < n; i++) {
            que.add(a[i]);
            sum += a[i];
        }
        if (sum < l) {
            que.add(l - sum);
        }

        long ans = 0;
        while (que.size() > 1) {
            long e1 = que.poll();
            long e2 = que.poll();
            long e = e1 + e2;
            ans += e;
            que.add(e);
        }
        System.out.println(ans);
    }
}

ABCEFと解いた時点で57分25秒＋1ペナ。346位。

Gは単調増加部分ごとに分けるとか、葉から木DPとか、意外とそのまま前から見ていって・・・とか考えてみるが何もわからず。
想定解の方法は全く考えもしていなかった。制約エスパーを取っ掛かりにするくらいしか自分には気付ける可能性なさそう。

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

Dで詰まらなければちょうどノルマ通りくらいだった。
EとFを順調に通せなければDを落ち着いて考え直せなかったかも。