SOMPO HD プログラミングコンテスト2021（AtCoder Beginner Contest 192）

A - Star
- 思考過程
B - uNrEaDaBlE sTrInG
- 思考過程
C - Kaprekar Number
- 思考過程
D - Base n
- 思考過程
E - Train
- 思考過程
F - Potion
- 思考過程

コンテスト前のレート：1970
レート通りのパフォーマンスが得られる順位：438位（2100点、111分04秒）
黄色になれるパフォーマンスが得られる順位：247位（2100点、79分56秒）

A - Star

思考過程

次の $100$ の倍数まであといくつかということなので、とりあえず $X$ を $100$ で割った余りを求める。
$100$ から上記1.の結果を引く。
コーナーケースとなる余り $0$ の場合（例２）も合っているので特に場合分け等不要。

import java.util.Scanner;

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

        x %= 100;
        System.out.println(100 - x);
    }
}

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

B - uNrEaDaBlE sTrInG

問題

思考過程

全ての文字が条件を満たせば"Yes"なので、前から $1$ 文字ずつ見ていき、 $1$ 文字でも条件を満たさなければ"No"とする処理構造にする。
奇数番目が大文字の場合"No"、偶数番目が小文字の場合"No"。
大文字小文字の判定は、大文字の方が文字コード順で小さいことを知っていれば、「s[i] < 'a'」の場合大文字といったように短く書くこともできるが、覚えていなかったので無難な判定をすることにする。

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

        for (int i = 0; i < s.length; i++) {
            if (i % 2 == 0) {
                if ('A' <= s[i] && s[i] <= 'Z') {
                    System.out.println("No");
                    return;
                }
            } else {
                if ('a' <= s[i] && s[i] <= 'z') {
                    System.out.println("No");
                    return;
                }
            }
        }
        System.out.println("Yes");
    }
}

ここまで2分32秒＋0ペナ。120位。

C - Kaprekar Number

問題

思考過程

問題文の通り素直に実装しても計算量が問題にはならなそう。
各桁の数字を並べ替えるところは、 $a_i$ を数値→文字列→文字配列と変換してソートすることにする。
数値に戻すところは、文字配列の $j$ 番目 $\times 10^j$ を足していく感じ。（ということをしたが、後から思えば文字列に戻してInteger.parseIntした方が楽だった）

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

        long[] a = new long[k + 1];
        a[0] = n;
        for (int i = 0; i < k; i++) {
            char[] g = String.valueOf(a[i]).toCharArray();
            Arrays.sort(g);
            long g1 = 0;
            long g2 = 0;
            long b = 1;
            for (int j = 0; j < g.length; j++) {
                g1 += b * (g[j] - '0');
                g2 += b * (g[g.length - 1 - j] - '0');
                b *= 10;
            }
            a[i + 1] = g1 - g2;
        }
        System.out.println(a[k]);
    }
}

ここまで7分26秒＋0ペナ。333位。

D - Base n

問題
下記3.の二分探索を書きかけるところまでやって手が止まってしまったので、一度順位表を確認。
まだ正解者数10人や20人程度でそこまで当てになるものではなかったが、一応E問題の方が解かれていたので、E問題を見てみることに。
Eの解法はほぼ問題文を読み終えると同時にわかったので、先にEを解いた。

思考過程

$X$ の下から $i$ 桁目を $X_i$ とすると、得られる値は $X_0 + X_1n + X_2n^2 + \ldots$ となるので、 $n$ が大きい方が得られる値は大きくなる。
上記のような単調性があるので、二分探索で条件を満たす $n$ の上限を求め、 $d$ を引いたものを答えとする方針で考える。
とりあえず二分探索のテンプレートを引っ張り出してくるが、okとngの初期値をどうすればよいのか悩む。
　
ok（確実に条件を満たすことがわかっている値）は、条件を満たす値がないときに $d$ になってほしいので $d$ とする。
ng（確実に条件を満たさないことがわかっている値）は $M+1$ ？
$X$ が"1"の場合、 $n=M$ どころかいくら大きくなっても $1$ になるような？
と思ったが、 $n$ 進数に変換した後の値の種類数だったので、 $n$ の値によらず $1$ 種類しか作れない。
というわけで、まずは $X$ が $1$ 桁の場合を別途処理してしまうことにする。
　
異なる進数 $n$ について、変換後の値が同じになることがあるか？
$2$ 桁以上であれば、 $X_0$ 以外に $0$ 以外である桁が存在するので、上記1.の式によりないとわかる。
　
あとは上記1.の式が $M$ 以下かどうかで二分探索すればよいが、この式は簡単にオーバーフローするので、オーバーフローの回避方法が問題。
安全に回避できる方法が思いつかなかったので、 $n^i$ を計算する部分だけBigIntegerを使うことにする。
$n^i$ だけで $10^{18}$ を超えるなら $M$ 以下にはならないし、 $9 \times 10^{18}$ をしてもまだオーバーフローしない。（と思ったが、それに前の桁までの合計を足してるので怪しいかも）

import java.math.BigInteger;
import java.util.Scanner;

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

        // Xが1桁の場合
        int n = x.length;
        if (n == 1) {
            int y = x[0] - '0';
            if (y <= m) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
            return;
        }

        int d = 1;
        for (int i = 0; i < n; i++) {
            int y = x[i] - '0';
            d = Math.max(d, y);
        }
        long ok = d;
        long ng = m + 1;
        BigInteger ba = BigInteger.valueOf(1000000000000000000L);
        label:
        while (Math.abs(ok - ng) > 1) {
            long mid = (ok + ng) / 2;
            BigInteger bm = BigInteger.valueOf(mid);
            BigInteger b = BigInteger.ONE;
            long val = 0;
            for (int i = 0; i < n; i++) {
                // mid^i > 10^18
                if (b.compareTo(ba) > 0) {
                    ng = mid;
                    continue label;
                }
                int y = x[n - 1 - i] - '0';
                val += b.longValue() * y;
                b = b.multiply(bm);
            }
            if (val <= m) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        System.out.println(ok - d);
    }
}

ABCEDと解いた時点で35分26秒＋0ペナ。96位。

E - Train

問題
類題の覚えがなんとなくあり、ダイクストラに一工夫入れるだけでできることはすぐにわかった。

思考過程

辺 $i$ を使う際に時刻を $K_i$ の倍数に切り上げる必要がある以外は、ただのダイクストラ。
切り上げ部分が一瞬A問題と同じかと思ったが違った。一旦切り捨ててから、割り切れなければ $K_i$ を足すことにした。（ $K_i-1$ を足してから切り捨ての方が書きやすかった）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

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]);
        int x = Integer.parseInt(sa[2]) - 1;
        int y = Integer.parseInt(sa[3]) - 1;
        List<List<Hen>> 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 a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            int t = Integer.parseInt(sa[2]);
            int k = Integer.parseInt(sa[3]);

            list.get(a).add(new Hen(b, t, k));
            list.get(b).add(new Hen(a, t, k));
        }
        br.close();

        long[] d = new long[list.size()];
        Arrays.fill(d, Long.MAX_VALUE);
        d[x] = 0;
        PriorityQueue<Node> que = new PriorityQueue<Node>();
        Node first = new Node(x, 0);
        que.add(first);

        while (!que.isEmpty()) {
            Node cur = que.poll();
            if (cur.d > d[cur.v]) {
                continue;
            }
            for (Hen hen : list.get(cur.v)) {
                long alt = d[cur.v] / hen.k * hen.k + hen.c;
                if (d[cur.v] % hen.k != 0) {
                    alt += hen.k;
                }
                if (alt < d[hen.v]) {
                    d[hen.v] = alt;
                    que.add(new Node(hen.v, alt));
                }
            }
        }
        long ans = d[y];
        if (ans == Long.MAX_VALUE) {
            ans = -1;
        }
        System.out.println(ans);
    }

    static class Hen {
        int v, c, k;

        public Hen(int v, int c, int k) {
            this.v = v;
            this.c = c;
            this.k = k;
        }
    }

    static class Node implements Comparable<Node> {
        int v;
        long d;

        public Node(int v, long d) {
            this.v = v;
            this.d = d;
        }

        public int compareTo(Node o) {
            return Long.compare(d, o.d);
        }
    }
}

ABCEと解いた時点で17分35秒＋0ペナ。44位。

F - Potion

問題
下記8.から9.へと進むまでが時間かかった。
しかし、実装で添え字をぐちゃぐちゃにした割には、ペナルティ喰らわずに一発で通って助かった。

思考過程

素材を $i$ 個使うとし、選んだ $i$ 個の合計を $S$ とすると、 $S \equiv X (mod$ $i)$ であれば作れる。
$i$ は $1$ から $N$ まで全探索する。
各 $i$ について、最大の $S$ （あるいは $S$ が存在しないか）を求めたい。
　
ナップサックDPをするのは制約が大きくて無理。
配列ではなくSetとかで作れる値のみの情報を持ちながらナップサックをしても、最大 $10^9$ 種類の値を作れるので変わらない。
$_NC_i$ 通りを全探索するのはもっと無理。
半分全列挙ができるのも $N \leq 40$ くらいまでなので無理。
$S$ が存在するかどうかだけなら長さ $i$ の情報を持てばいいような気もするがよくわからない。
　
と思ったが、基本形はナップサックDPで、 $j$ 個目まで見て $k$ 個選んだ時の合計が $mod$ $i$ で $k2$ となる中の最大値だけ残せばできそう。（初回実装時は「 $k$ 個選んだ時」が抜けてしまっていたが、例１が通らなかったことで気付く）
ループが何重にもなっていてなんとなく計算量が心配になり、せめてインラインDPにしようとする。 $k$ のループを逆順にすれば、同じ素材を $2$ 回使ってしまうことはない。

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

        long ans = x;
        for (int i = 1; i <= n; i++) { // 素材を使う数
            int m = (int) (x % i);
            long[][] dp = new long[i + 1][i];
            for (int j = 0; j <= i; j++) {
                Arrays.fill(dp[j], -1);
            }
            dp[0][0] = 0;
            for (int j = 0; j < n; j++) { // j個目まで見て、
                // 遷移元：k個使ってmod iで余りがk2　を全部調べる
                for (int k = Math.min(i - 1, j); k >= 0; k--) {
                    for (int k2 = 0; k2 < i; k2++) {
                        if (dp[k][k2] != -1) {
                            // j個目を使う場合の遷移
                            int k3 = (int) ((dp[k][k2] + a[j]) % i);
                            dp[k + 1][k3] = Math.max(dp[k + 1][k3], dp[k][k2] + a[j]);
                        }
                    }
                }
            }
            if (dp[i][m] != -1) {
                long val = (x - dp[i][m]) / i;
                ans = Math.min(ans, val);
            }
        }
        System.out.println(ans);
    }
}

ここまで64分17秒＋0ペナ。133位。

最終結果：ABCDEFの全完、64分17秒、133位、パフォーマンス2400
レート変動：1970→2021（+51）

というわけで、1年3ヶ月ほどの青色期間を経てついに黄色になりました！
近い内によくある色変記事でも書いてみようかと。
このブログを始めた時には既に青で、それ以降今まで一度も色が変わったことがなく、橙まで上がることは多分一生ないので最初で最後になる予定。

黄色になったばかりで翌日にARCがあるのが怖いところだが、パフォ1789以上で黄色に留まれるようなので、多分大丈夫だと信じたい。