LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）(Rated範囲外)

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

A - Full House

問題

思考過程

1. 回登場する値と回登場する値がつずつあればよい。
2. これを調べられるようにするには、「各値の出現回数」の出現回数を求めたい。
   　
3. まず入力を各値～の出現回数をカウントしながら受け取る。
4. さらに上記3.の各回数～の出現回数を調べる。

import java.util.Scanner;

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

        // 4
        int[] c = new int[6];
        for (int i = 0; i < 14; i++) {
            c[a[i]]++;
        }
        // 1
        if (c[2] == 1 && c[3] == 1) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで1分46秒＋0ペナ。236位。

B - Ancestor

問題

思考過程

1. 人から始めて、人にたどり着くまで回数をカウントしながらをたどっていく。

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

        int now = n - 1;
        int ans = 0;
        while (now > 0) {
            ans++;
            now = p[now];
        }
        System.out.println(ans);
    }
}

ここまで3分21秒＋0ペナ。128位。

C - Monotonically Increasing

問題
for文の終了条件でイコールが抜けていて1ペナ。
下記4.で空の場合の方にしていればミスらなかったかも。

思考過程

1. 要素をつずつ追加していく再帰処理を考える。
2. 要素数が個になったら出力してリターン。
3. 追加する要素は、現在の数列の末尾の要素～を順番に試す。
4. 空の場合は末尾の要素を取れないため、空の場合としてもよいが、最初につ入れた状態から再帰処理を始めることにしてみる。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int n, m;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        sc.close();

        // 4
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            list.add(i);
            dfs(list);
            list.remove(list.size() - 1);
        }
    }

    static void dfs(List<Integer> list) {
        // 2
        if (list.size() == n) {
            StringBuilder sb = new StringBuilder();
            for (int i : list) {
                sb.append(i).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
            return;
        }

        // 3
        for (int i = list.get(list.size() - 1) + 1; i <= m; i++) {
            list.add(i);
            dfs(list);
            list.remove(list.size() - 1);
        }
    }
}

ここまで8分29秒＋1ペナ。397位。

D - Left Right Operation

問題
明らかにおかしいのに、下記2.みたいなことをやっていて10分以上ロスしている。

思考過程

1. 左側個をに置き換える操作しかない場合の左から番目までの総和の最小値と、右側についても同様に右側からの総和の最小値を求めておき、左側と右側の境目を通り全探索する形にしたい。
2. 左から番目までの総和の最小値は、番目までの累積和との小さい方？と思ったりするが、これでは全く置き換えないか全部置き換えるかしか考慮できていない。
3. 正しくは、はとの小さい方のような求め方をする必要がある。

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        // 3
        long[] lm = new long[n + 1];
        for (int i = 0; i < n; i++) {
            lm[i + 1] = Math.min(lm[i] + a[i], l * (i + 1));
        }
        long[] rm = new long[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            rm[i] = Math.min(rm[i + 1] + a[i], r * (n - i));
        }

        // 1
        long ans = lm[n];
        for (int i = 0; i <= n; i++) {
            long val = lm[i] + rm[i];
            ans = Math.min(ans, val);
        }
        System.out.println(ans);
    }
}

ここまで28分32秒＋1ペナ。679位。

Eはそれらしい実装をしてみるも例２が合わず。30分ほどかけても解けず、飛ばしてFへ。
Fは全くわかる気がせず、10分も考えずに飛ばしてGへ。

Gは最大流一発やるだけだろうとグラフの形を一生懸命考えているばかりで、同じ値つで作れるのがだけであるとかそういった考察を一切しようとしていなかった。

最終結果：ABCDの4完1000点、33分32秒、1102位、パフォーマンス1424相当
レート変動：2052（Unrated）

なんかやっぱりDPが得意ではないのは間違いないと思う。
EDPCをもう一度最初からやった方がいいか・・・。