キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）

ABC

コンテスト前のレート：1929
レート通りのパフォーマンスが得られる順位：399位（1500点、48分54秒）

A - Batting Average

問題

思考過程
  1. BigDecimalを使って問題文の通り割り算と四捨五入を行う。
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;

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

        BigDecimal ans = b.divide(a, 3, RoundingMode.HALF_UP);
        System.out.println(ans.toPlainString());
    }
}

ここまで2分02秒＋0ペナ。734位。


B - Line Sensor

問題

思考過程
  1. 二次元配列を縦に見て'#'を数える。
import java.util.Scanner;

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

        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < w; j++) {
            int ans = 0;
            for (int i = 0; i < h; i++) {
                if (c[i][j] == '#') {
                    ans++;
                }
            }
            sb.append(ans).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで4分05秒＋0ペナ。438位。


C - Ameba

問題

思考過程
  1. A_iがx代目であるとすると、A_{2i}, A_{2i+1}がx+1代目となる。（0-indexedの場合はA_{2i+1}, A_{2i+2}）
import java.io.PrintWriter;
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() - 1;
        }
        sc.close();

        int n2 = n * 2 + 1;
        int[] ans = new int[n2];
        for (int i = 0; i < n; i++) {
            ans[i * 2 + 1] = ans[a[i]] + 1;
            ans[i * 2 + 2] = ans[a[i]] + 1;
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i : ans) {
            pw.println(i);
        }
        pw.flush();
    }
}

ここまで7分37秒＋0ペナ。117位。


D - Robot Arms 2

問題

思考過程
  1. 「dp[i]:=i点目の配置場所としてあり得る座標の集合」をやりたい。
  2. Aを奇数番目と偶数番目に分けることで、x, y座標を独立に見ることができる。
  3. この手のDPは集合の大きさがO(2^N)になってしまいそうな気がするが、取り得る値の範囲かによりO(NA)に収まる。
  4. 操作回数がNなので全体でO(N^2A)となり間に合う。
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 x = sc.nextInt();
        int y = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        Set<Integer> setx = new HashSet<>();
        setx.add(a[0]);
        for (int i = 2; i < n; i += 2) {
            Set<Integer> wk = new HashSet<>();
            for (int e : setx) {
                wk.add(e + a[i]);
                wk.add(e - a[i]);
            }
            setx = wk;
        }

        Set<Integer> sety = new HashSet<>();
        sety.add(0);
        for (int i = 1; i < n; i += 2) {
            Set<Integer> wk = new HashSet<>();
            for (int e : sety) {
                wk.add(e + a[i]);
                wk.add(e - a[i]);
            }
            sety = wk;
        }

        if (setx.contains(x) && sety.contains(y)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで14分47秒＋0ペナ。54位。


E - Booster

問題

思考過程
  1. 街と宝箱をまとめて、基本形としては普通の巡回セールスマン問題と同様に「dp[i][j]:=訪問済みの座標の集合がiで現在地がjの場合にかかる時間の最小値」とする。
  2. jからいずれかの未訪問座標への移動を計算する際、訪問済みの宝箱の数を考慮する。
  3. DP配列の情報の内、街を全て訪問している各パターンから原点に戻る時間を足したものの最小値を求める。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
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 nm = n + m;
        int nm1 = n + m + 1;
        // 0：原点、1～n：街、n+1～n+m：宝箱
        int[] x = new int[nm1];
        int[] y = new int[nm1];
        for (int i = 1; i <= nm; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        sc.close();

        // 宝箱部分
        int mask = 0;
        for (int i = n + 1; i <= nm; i++) {
            mask += 1 << i;
        }

        // 座標間の距離
        double[][] d = new double[nm1][nm1];
        for (int i = 0; i < nm1; i++) {
            for (int j = i + 1; j < nm1; j++) {
                d[i][j] = Math.hypot(x[i] - x[j], y[i] - y[j]);
                d[j][i] = d[i][j];
            }
        }

        int end = 1 << nm1;
        double[][] dp = new double[end][nm1];
        for (int i = 0; i < end; i++) {
            Arrays.fill(dp[i], 1e20);
        }
        dp[1][0] = 0;
        for (int i = 1; i < end; i++) {
            List<Integer> from = new ArrayList<>();
            List<Integer> to = new ArrayList<>();
            for (int j = 0; j < nm1; j++) {
                if ((i >> j & 1) == 1) {
                    from.add(j);
                } else {
                    to.add(j);
                }
            }
            int bs = Integer.bitCount(i & mask);
            int sp = 1 << bs;
            for (int a : from) {
                for (int b : to) {
                    int next = i + (1 << b);
                    dp[next][b] = Math.min(dp[next][b], dp[i][a] + d[a][b] / sp);
                }
            }
        }

        // 街部分
        int mask2 = 0;
        for (int i = 1; i <= n; i++) {
            mask2 += 1 << i;
        }

        double ans = 1e20;
        for (int i = 0; i < end; i++) {
            if ((i & mask2) == mask2) {
                int bs = Integer.bitCount(i & mask);
                int sp = 1 << bs;
                for (int j = 0; j < nm1; j++) {
                    ans = Math.min(ans, dp[i][j] + d[0][j] / sp);
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで36分40秒＋0ペナ。116位。


F - Fishing

問題

思考過程
  1. xをいずれかの魚の位置であるとして損をしないので、対象の魚iを全探索する。
  2. 魚jが魚iの位置+0～+Aの範囲に入る時刻に+W_j、範囲から出る時刻に-W_jとしたいもす法を行う。
  3. いもす法の際、時刻が0以上の部分のみが答えの候補。　→WAとTLEが発生。よく見ると例３も1100となっていてWA。
    　
  4. 同じ時刻に入る魚と出る魚がいる場合、入る方を先に処理してmaxを取ってから出る方を処理する必要があった。
  5. これは適当に入る時刻を-eps、出る時刻を+epsして対処することにする。
  6. 計算量はO(N^2logN)で大きく問題はないはずなので定数倍改善を考える。
  7. 初期位置の関係でt \geq 0の範囲でプラスにならない魚はいもす法のマップに入れないことにしてみる。　→TLEが2ケースだけになったがまだ打ち切られレベルの3310ms
    　
  8. 手元で最大ケースを適当に作って試してみるが、やっぱりだいたい2秒しないくらいで終わる。他にできる小細工何かないか？
  9. 時刻を整数で扱えればdouble型の計算が減って速くなりそうだが、今更そこまで書き換えるのは厳しい。精度でWAが心配になってくるが、doubleをfloatにしてみる。　→1ケースのみTLEで3009msまで来た。これなら提出しまくればその内運良く通るのでは？
  10. よく見たら入力にScannerを使っていたので、より高速なBufferedReaderに変える。これで平均30msくらいは縮むはず。　→2532ms。いやそんなに変わるはずはないと思うんだけど何で？
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeMap;

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

        float eps = (float) 1e-7;
        float inf = Float.MAX_VALUE;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            TreeMap<Float, Integer> map = new TreeMap<>();
            for (int j = 0; j < n; j++) {
                if (v[i] == v[j]) {
                    if (x[i] <= x[j] && x[j] <= x[i] + a) {
                        map.put(-inf, map.getOrDefault(-inf, 0) + w[j]);
                        map.put(inf, map.getOrDefault(inf, 0) - w[j]);
                    }

                } else if (v[i] < v[j] && x[j] <= x[i] + a) {
                    // x[i] + v[i]*t + a = x[j] + v[j]*t
                    // (v[i] - v[j])*t = x[j] - x[i] - a
                    float t = (float) (x[j] - x[i]) / (v[i] - v[j]) - eps;
                    map.put(t, map.getOrDefault(t, 0) + w[j]);
                    t = (float) (x[j] - x[i] - a) / (v[i] - v[j]) + eps;
                    map.put(t, map.getOrDefault(t, 0) - w[j]);

                } else if (v[i] > v[j] && x[i] <= x[j]) {
                    float t = (float) (x[j] - x[i] - a) / (v[i] - v[j]) - eps;
                    map.put(t, map.getOrDefault(t, 0) + w[j]);
                    t = (float) (x[j] - x[i]) / (v[i] - v[j]) + eps;
                    map.put(t, map.getOrDefault(t, 0) - w[j]);
                }
            }
            int now = 0;
            for (Float k : map.keySet()) {
                if (k >= -eps) {
                    ans = Math.max(ans, now);
                }
                now += map.get(k);
                if (k >= -eps) {
                    ans = Math.max(ans, now);
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで81分10秒＋3ペナ。157位。



Gは全然わからず、Exは見てもいない。
Gは一応残り数分で適当に嘘貪欲（カバーできるマスの数が多い箇所から順にカメラを置いていく）でもやるだけやってみようと思ったが実装途中で時間切れ。



最終結果：ABCDEFの6完2000点、96分10秒、214位、パフォーマンス2185
レート変動：1929→1957（+28）


Fは解けなくてもパフォ2020くらい出たらしい。
TLEで苦しまなければペナ込み70分くらいでFまで通せた見込みで、その場合は2280くらい。

最高レートが2129なので2185だとそんなに大きく上がるような感覚がないのだが、28も上がるほど落ち込んでいたんだな・・・。
とりあえずそこそこ大きく回復して何より。