日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257）

コンテスト前のレート：1981
レート通りのパフォーマンスが得られる順位：338位（2000点、75分57秒）

A - A to Z String 2

問題
A問題とはいえ考え方が雑だった。

思考過程

1. おおよそ'A'にを足した文字になる。
2. 例２での場合に計算結果がになってほしいので、が正解っぽいか。
3. 色々テストして合っていそうなので提出。

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 x = sc.nextInt() - 1;
        sc.close();

        int a = x / n;
        System.out.println((char) ('A' + a));
    }
}

ここまで2分09秒＋0ペナ。796位。

B - 1D Pawn

問題

思考過程

1. 問題文の通り回処理する。
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 k = sc.nextInt();
        int q = sc.nextInt();
        int[] a = new int[k];
        for (int i = 0; i < k; i++) {
            a[i] = sc.nextInt();
        }
        int[] l = new int[q];
        for (int i = 0; i < q; i++) {
            l[i] = sc.nextInt() - 1;
        }
        sc.close();

        for (int i = 0; i < q; i++) {
            if (a[l[i]] != n) {
                if (l[i] == k - 1 || a[l[i]] + 1 < a[l[i] + 1]) {
                    a[l[i]]++;
                }
            }
        }

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

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

C - Robot Takahashi

問題

思考過程

1. を全探索して最大値を求めたい。としては通り調べれば十分。
2. の小さい順に見て、を（よりわずかに大きい値）とした時に正しい子供の数または誤った大人の数を増やしていく。
3. 同じが複数存在した場合、子供を先に見るべき？と思ったがそうではなく、同じは全てカウントしてから最大値判定をする必要があった。
4. がつ前と同じ場合はスキップさせる。　→半分くらいWA
5. つ後ろと同じ場合にスキップが正解だった。

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));
        int n = Integer.parseInt(br.readLine());
        char[] s = br.readLine().toCharArray();
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> {
            if (o1.w != o2.w) {
                return o1.w - o2.w;
            }
            return o1.c - o2.c;
        });
        String[] sa = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.c = s[i] - '0';
            o.w = Integer.parseInt(sa[i]);
            que.add(o);
        }
        br.close();

        int z1 = 0; // 子供の総数
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                z1++;
            }
        }
        int z2 = n - z1; // 大人の総数

        int ans = z2;
        int x1 = 0; // 正しい子供の数
        int x2 = 0; // 誤った大人の数
        while (!que.isEmpty()) {
            Obj o = que.poll();
            if (o.c == 0) {
                x1++;
            } else {
                x2++;
            }
            // 次と同じ場合スキップ
            if (!que.isEmpty() && o.w == que.peek().w) {
                continue;
            }
            int val = x1 + z2 - x2;
            ans = Math.max(ans, val);
        }
        System.out.println(ans);
    }

    static class Obj {
        int c, w;
    }
}

ここまで19分12秒＋1ペナ。598位。

D - Jumping Takahashi 2

問題

思考過程

1. 明らかに、が答え未満ならNG、以上ならOKという単調性があるので、二分探索を行う。
2. 判定部分は、若干計算量に自信がなかったが、とりあえず単純に回BFSをする。
3. 答えの上限はでいいかな？　→8割ほどWA
4. だった。　→WA数変わらず
5. オーバーフローだけでこんなに落ちるか？とも思ったが、他に悪いところがわからないのでオーバーフロー対策をしっかりやる。　→AC

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

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

        long ok = 4000000000L;
        long ng = 0;
        while (Math.abs(ok - ng) > 1) {
            long mid = (ok + ng) / 2;
            boolean flg = false;
            for (int s = 0; s < n; s++) {
                Queue<Integer> que = new ArrayDeque<>();
                que.add(s);
                boolean[] b = new boolean[n];
                b[s] = true;
                int cnt = 1;
                while (!que.isEmpty()) {
                    int cur = que.poll();
                    for (int i = 0; i < n; i++) {
                        long d = (long) Math.abs(x[cur] - x[i]) + Math.abs(y[cur] - y[i]);
                        if (!b[i]) {
                            if (Long.MAX_VALUE / mid <= p[cur] ||  mid * p[cur] >= d) {
                                que.add(i);
                                b[i] = true;
                                cnt++;
                            }
                        }
                    }
                }
                if (cnt == n) {
                    flg = true;
                    break;
                }
            }
            if (flg) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        System.out.println(ok);
    }
}

ここまで39分54秒＋3ペナ。609位。

E - Addition and Multiplication 2

問題

思考過程

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

        int min = n;
        for (int i = 1; i < m; i++) {
            min = Math.min(min, c[i]);
        }

        int keta = n / min;
        int rem = n;
        int yoyu = n - min * keta;
        StringBuilder sb = new StringBuilder();
        int x = 9;
        while (x > 0) {
            if (c[x] == min) {
                while (rem - min >= 0) {
                    rem -= min;
                    sb.append(x);
                }
                break;
            }
            int d = c[x] - min;
            while (yoyu - d >= 0) {
                yoyu -= d;
                rem -= c[x];
                sb.append(x);
            }
            x--;
        }
        System.out.println(sb.toString());
    }
}

ここまで48分12秒＋3ペナ。357位。

F - Teleporter Setting

問題

思考過程

1. 移動先未定のテレポーターがある町から町、町までの距離を知っておきたい感じなので、両側からBFSをしておく。
2. 移動先未定のテレポーターがある町の内、町に最も近い町から町までの距離を求めておく。町についても同様。
   　
3. 最短ルートとして考えられるものが以下のパターンのため、これらの最小値を求める。
   • 未定テレポーター使用なし
   • 町　→　町　→　未定テレポーター　→　町　→　未定テレポーター　→　町　→　町
   • 町　→　町　→　未定テレポーター　→　町　→　町
   • 町　→　町　→　未定テレポーター　→　町　→　町
4. 初め上記の下つは、が元々未定テレポーターの片方がある町である場合限定かと思っていたりしたが、未定の方がの場合もあるためそんなことはなかった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class Main {
    static int n, m;
    static List<List<Integer>> list;
    static int inf = 100000000;

    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<>());
        }
        Set<Integer> set = new HashSet<>();
        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;
            if (u == -1) {
                set.add(v);
            } else {
                list.get(u).add(v);
                list.get(v).add(u);
            }
        }
        br.close();

        // 1
        int[] d1 = bfs(0);
        int[] dn = bfs(n - 1);
        // 2
        int m1 = inf;
        int mn = inf;
        for (int i = 0; i < n; i++) {
            if (set.contains(i)) {
                m1 = Math.min(m1, d1[i]);
                mn = Math.min(mn, dn[i]);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            // 3
            int ans = Math.min(m1 + 2 + mn, dn[0]);
            ans = Math.min(ans, d1[i] + 1 + mn);
            ans = Math.min(ans, m1 + 1 + dn[i]);
            if (ans >= inf) {
                ans = -1;
            }
            sb.append(ans).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    static int[] bfs(int s) {
        Queue<Integer> que = new ArrayDeque<>();
        que.add(s);
        int[] d = new int[n];
        Arrays.fill(d, inf);
        d[s] = 0;
        while (!que.isEmpty()) {
            int cur = que.poll();
            for (int next : list.get(cur)) {
                if (d[next] == inf) {
                    que.add(next);
                    d[next] = d[cur] + 1;
                }
            }
        }
        return d;
    }
}

ここまで76分52秒＋3ペナ。334位。

Gはとを繋げた文字列にZアルゴリズムを使って、後ろのの部分について何らかのDPというところまでは考えたが、DP部分が書けず時間切れ。
その後解説を見てそれらしくやってみたが1WAと2TLE。
この記事をここまで書いた後にもう一度やってみて、実装ミスを直したらWAは消え、TLEは以下の提出で39行目のfor文の終了条件を一度変数に入れたら解消した。こんなことで600ms以上も変わるとは思えないんだが・・・。
TLE提出
AC提出

最終結果：ABCDEFの6完2000点、91分52秒、408位、パフォーマンス1890相当
レート変動：1981→1972（-9）

今回もペナなしならほぼノルマ通りであった。
実装の手が遅いのと、注意力が足りていない。

Gはこれまでほぼ使用実績のないZアルゴリズムにたどり着けただけで上出来なので仕方ない。