NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)

ABC

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

A - Saturday

問題

思考過程
  1. 5分岐のif文を書くより楽な実装方法を考える。
  2. とりあえず問題文の文字列をコピペして配列を作ってみれば楽に変換できそう？　ダブルクォートを自力で付加する羽目になっているのはイマイチ。
  3. 一応for文を回して文字列が一致した時のループカウンタを元に計算して出力できた。楽にはなっていないかも。
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[] arr = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].equals(s)) {
                System.out.println(5 - i);
                return;
            }
        }
    }
}

ここまで1分36秒＋0ペナ。319位。


B - Split?

問題

思考過程
  1. 列ごとに立っているピンが残っているかを調べる。これはif文を10個並べてしまった方が早そう。
  2. 列iと列j (\ge i+2)の組で両方ピンが残っている組が存在するかを調べる。　→例３が"Yes"になる。
  3. 列i+1が全て倒れているかチェックしていなかったのでチェックする。　→例４が"Yes"になる。
  4. ピン1をチェックしていなかったのでチェックする。
import java.util.Scanner;

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

        // 1
        boolean[] b = new boolean[7];
        if (s[0] == '1') b[3] = true;
        if (s[1] == '1') b[2] = true;
        if (s[2] == '1') b[4] = true;
        if (s[3] == '1') b[1] = true;
        if (s[4] == '1') b[3] = true;
        if (s[5] == '1') b[5] = true;
        if (s[6] == '1') b[0] = true;
        if (s[7] == '1') b[2] = true;
        if (s[8] == '1') b[4] = true;
        if (s[9] == '1') b[6] = true;

        // 4
        if (s[0] == '1') {
            System.out.println("No");
            return;
        }
        for (int i = 0; i < 6; i++) {
            // 3
            if (b[i + 1]) {
                continue;
            }
            // 2
            for (int j = i + 2; j < 7; j++) {
                if (b[i] && b[j]) {
                    System.out.println("Yes");
                    return;
                }
            }
        }
        System.out.println("No");
    }
}

ここまで6分24秒＋0ペナ。89位。


C - Index × A(Continuous ver.)

問題

思考過程
  1. A_i \times iの累積和Sを求めておき、S_Mを初期解として、右側を加算して左側を減算して全体を1回分引くような差分計算をしていくことを考える。
  2. 全体を1回分引くためには普通の累積和も必要。
  3. ここまで用意したら、結局(S_{i+M} - S_i)から通常累積和(B_{i+M} - B_i)のi倍を引けば普通に求まるので、差分計算する考えをやめる。
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 = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        long[] b = new long[n + 1];
        long[] s = new long[n + 1];
        for (int i = 0; i < n; i++) {
            b[i + 1] = b[i] + a[i];
            s[i + 1] = s[i] + a[i] * (i + 1L);
        }

        long ans = s[m];
        int end = n - m;
        for (int i = 0; i <= end; i++) {
            int j = m + i;
            long val = s[j] - s[i];
            val -= (b[j] - b[i]) * i;
            ans = Math.max(ans, val);
        }
        System.out.println(ans);
    }
}

ここまで16分50秒＋0ペナ。410位。


D - Index × A(Not Continuous ver.)

問題

思考過程
  1. 「DP[i][j]:=i番目まででj個選んでいる時の最大値」をする。
  2. 初期値がLong.MIN_VALUEだと負の値を加算してオーバーフローしたため、適当にもう少し絶対値を減らした値にする。
import java.util.Arrays;
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 = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        long[][] dp = new long[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], -10000000000000000L); // 2
        }
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            // i番目を選ばない
            for (int j = 0; j <= m; j++) {
                dp[i + 1][j] = dp[i][j];
            }
            // i番目を選ぶ
            for (int j = 0; j < m; j++) {
                dp[i + 1][j + 1] = Math.max(dp[i + 1][j + 1], dp[i][j] + a[i] * (j + 1));
            }
        }
        System.out.println(dp[n][m]);
    }
}

ここまで20分01秒＋0ペナ。227位。


E - Erasing Vertices 2

問題

思考過程
  1. とりあえず答えの二分探索をする。
  2. 答えの最大値はだいたいO(AN)として2 \times 10^{14}くらいの想定だが、余裕を持って10^{16}としておく。（1回の判定が結構重そうなO(N)なのでむやみに10^{18}とかにはしたくないと思った）
  3. 判定部分は、コストが答え以下の頂点を操作可能な頂点としてキューに追加し、キューがなくなるまで操作をし続けた後、全ての頂点を操作していればOKとする。
    　
  4. 辺を削除する部分も実装した方が定数倍は早いか？と思ったが、毎回グラフ情報をコピーするのがかえって重かったようでTLE。
  5. 辺を削除しなくても参照回数2倍になるだけなので、同じ頂点を二度キューに入れないようにするくらいで問題なかった。とはいえ4000ms制限のところ3024msでそんなに余裕でもなかったが。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

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]);
        }
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        long[] b = new long[n];
        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);
            b[u] += a[v];
            b[v] += a[u];
        }
        br.close();

        long ok = 10000000000000000L;
        long ng = -1;
        while (Math.abs(ok - ng) > 1) {
            long mid = (ok + ng) / 2;
            long[] b2 = Arrays.copyOf(b, n);
            Queue<Integer> que = new ArrayDeque<>();
            boolean[] can = new boolean[n];
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (b2[i] <= mid) {
                    que.add(i);
                    can[i] = true;
                    cnt++;
                }
            }
            while (!que.isEmpty()) {
                int cur = que.poll();
                for (int next : list.get(cur)) {
                    b2[next] -= a[cur];
                    if (!can[next] && b2[next] <= mid) {
                        que.add(next);
                        can[next] = true;
                        cnt++;
                    }
                }
            }

            if (cnt == n) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        System.out.println(ok);
    }
}

ここまで38分17秒＋1ペナ。265位。



残り時間は全部Fに使っており、GとExは問題も見ていない。

Fは木の中心を根として、U_iから親の方向にK_i進んで根に到達しないならその頂点（ダブリングで求める）を出力。
根を通り過ぎる必要があるなら、根から深さが残りの距離に一致する頂点の中から（根の頂点が存在しないものとした森における）異なる連結成分に属するものを探して出力。
ということをやろうとしたが、半分WAで2割TLEといったところ。

おそらく異なる連結成分に属するものを探すところでTLEだがやっていることは合っていると信じており、最初はREも出ていたのでWAはまだ何かバグっているのかな・・・と。



最終結果：ABCDEの5完1500点、43分17秒、544位、パフォーマンス1801
レート変動：1985→1968（-17）


このFは自分としては解けなければ駄目な問題だったと思う。
GとExはDPだったみたいだし、手を出さなくて正解。

日本245位なら社会人100位以内の可能性はぎりぎりありそう？