パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 251）

A - Six Characters
- 思考過程
B - At Most 3 (Judge ver.)
- 思考過程
C - Poem Online Judge
- 思考過程
D - At Most 3 (Contestant ver.)
- 思考過程
E - Tahakashi and Animals
- 思考過程
F - Two Spanning Trees
- 思考過程

コンテスト前のレート：1969
レート通りのパフォーマンスが得られる順位：309位（2000点、76分43秒）

A - Six Characters

思考過程

$S$ の長さは必ず $6$ の約数。
長さが $6$ 未満である限り $S$ を付け足していけば、どこかで長さがちょうど $6$ になる。

import java.util.Scanner;

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

        String ans = s;
        while (ans.length() < 6) {
            ans += s;
        }
        System.out.println(ans);
    }
}

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

B - At Most 3 (Judge ver.)

問題

思考過程

$O(N^3)$ が間に合う制約。
添え字が重複しない形で三重ループを回して、 $A_i+A_j+A_k \leq W$ の場合にSetに入れていって要素数を出力する。　→例１が $0$ になる。
$3$ 個ちょうどではなく以下だったので、 $A_i$ と $A_i+A_j$ についても対象にする。

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

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int b = a[i];
            if (b <= w) {
                set.add(b);
            }
            for (int j = 0; j < i; j++) {
                b = a[i] + a[j];
                if (b <= w) {
                    set.add(b);
                }
                for (int k = 0; k < j; k++) {
                    b = a[i] + a[j] + a[k];
                    if (b <= w) {
                        set.add(b);
                    }
                }
            }
        }
        System.out.println(set.size());
    }
}

ここまで4分01秒＋0ペナ。166位。

C - Poem Online Judge

問題

思考過程

オリジナルな提出かどうかを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();
        String[] s = new String[n];
        int[] t = new int[n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next();
            t[i] = sc.nextInt();
        }
        sc.close();

        Set<String> set = new HashSet<>();
        int max = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (set.add(s[i])) {
                if (t[i] > max) {
                    max = t[i];
                    ans = i;
                }
            }
        }
        System.out.println(ans + 1);
    }
}

ここまで6分26秒＋0ペナ。79位。

D - At Most 3 (Contestant ver.)

問題
一瞬Bと同じ問題が間違って設定されているのかと思った。
しょうもないミスで1ペナ。

思考過程

入力の $W$ は意味がない。 $10^6$ であるとして、全ケース同じ出力でよい。
$1, 2, 4, 8, 15, \cdots$ のように、構成不可能な値が出てきたところでそれを入れていくことを考えてみるが、入れていく値の間隔が広がっていく気があまりしない。
　
仮に $2$ 数の組み合わせで $1$ ～ $1000$ くらいを全部作れれば、 $3$ つ目用に $1000, 2000, 3000, \cdots$ を用意しておけばよい。
ただし、 $N$ の制約的に、 $200$ 個以内で $10000$ くらいまでを作れる必要がある。
　
$1$ つ目用に $1$ ～ $10$ を入れたとすると、 $2$ つ目用は $10, 20, 30, \cdots$ にできる。
$100$ 個ずつ使えば、 $1, 2, \cdots, 100$ 、 $100, 200, \cdots, 10000$ 、 $10000, 20000, \cdots, 1000000$ でちょうどでは？
$100$ 進数であると考えれば漏れはなさそう。　→全ケースWA
　
B問題の提出コードを引っ張ってきて問題ないことを確認する。
出力に $N$ が抜けていると気付く。

import java.util.Scanner;

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

        int[] a = new int[300];
        for (int i = 0; i < 100; i++) {
            a[i] = i + 1;
        }
        for (int i = 0; i < 100; i++) {
            a[i + 100] = (i + 1) * 100;
        }
        for (int i = 0; i < 100; i++) {
            a[i + 200] = (i + 1) * 10000;
        }

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

ここまで22分16秒＋1ペナ。262位。

E - Tahakashi and Animals

問題

思考過程

$i$ 番目まで見て最後の動物に餌をあげているかいないかの $2$ つの配列を用意してDPをやってみるが、どうにも $N$ と $1$ のところの帳尻合わせが怪しい。
情報量が過剰な気もするが、動物 $1$ にあげているかどうかと、最後の動物にあげているかどうかを組み合わせた $4$ つを用意してDPをすることにする。

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

        long[] dp00 = new long[n + 3]; // 動物1：×、動物i：×
        long[] dp01 = new long[n + 3]; // 動物1：×、動物i：○
        long[] dp10 = new long[n + 3]; // 動物1：○、動物i：×
        long[] dp11 = new long[n + 3]; // 動物1：○、動物i：○
        dp11[1] = a[n - 1];
        for (int i = 2; i <= n; i++) {
            // dpx1への遷移：i-2まで済の場合とi-1まで済の場合のminに、
            //               i-1とiにあげるコストを追加
            // dpx0への遷移：i-1まで済の状態そのもの
            dp11[i] = Math.min(dp10[i - 1] + a[i - 2], dp11[i - 1] + a[i - 2]);
            dp10[i] = dp11[i - 1];
            dp01[i] = Math.min(dp00[i - 1] + a[i - 2], dp01[i - 1] + a[i - 2]);
            dp00[i] = dp01[i - 1];
        }
        long ans = Math.min(dp11[n], dp00[n] + a[n - 1]);
        System.out.println(ans);
    }
}

ここまで37分13秒＋1ペナ。254位。

F - Two Spanning Trees

問題

思考過程

例１を描いてみると、 $T_1$ はなるべく頂点 $1$ と繋がる辺を除外していて、 $T_2$ はなるべく頂点 $1$ と繋がる辺を残しているように見える。
実際 $T_1$ については、多数に枝分かれしている頂点から最小限の辺だけ残すようにすると、除外した辺は必然的に子と繋がっていることになりそう。
DFS順に辿った場合を考えてみると問題なさそうに思える。
では $T_2$ はBFS順だったりするか？　→問題なさそうに思える。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Main {
    static int n, m;
    static List<List<Integer>> list;
    static boolean[] visit;
    static List<String> ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        n = Integer.parseInt(sa[0]);
        m = Integer.parseInt(sa[1]);
        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 u = Integer.parseInt(sa[0]) - 1;
            int v = Integer.parseInt(sa[1]) - 1;
            list.get(u).add(v);
            list.get(v).add(u);
        }
        br.close();

        // T1
        visit = new boolean[n];
        ans = new ArrayList<>(n - 1);
        dfs(0, -1);
        PrintWriter pw = new PrintWriter(System.out);
        for (String s : ans) {
            pw.println(s);
        }

        // T2
        visit = new boolean[n];
        ans = new ArrayList<>(n - 1);
        Queue<Integer> que = new ArrayDeque<>();
        que.add(0);
        visit[0] = true;
        while (!que.isEmpty()) {
            int cur = que.poll();
            for (int next : list.get(cur)) {
                if (!visit[next]) {
                    ans.add((cur + 1) + " " + (next + 1));
                    que.add(next);
                    visit[next] = true;
                }
            }
        }
        for (String s : ans) {
            pw.println(s);
        }
        pw.flush();
    }

    static void dfs(int x, int p) {
        visit[x] = true;
        for (int c : list.get(x)) {
            if (c != p && !visit[c]) {
                ans.add((x + 1) + " " + (c + 1));
                dfs(c, x);
            }
        }
    }
}