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

43:47 + 0:00 全完で全体 46 位，日本人 39 位でした．賞金ワンチャンないかな...？

A - Star

コイン 100 枚で 1 up するアレかな？ $100-(X\bmod 100)$ が答え．

B - uNrEaDaBlE sTrInG

char[] s = sc.nextChars();
boolean y = true;
for (int i = 0; i < s.length; i += 2) {
    y &= Character.isLowerCase(s[i]);
}
for (int i = 1; i < s.length; i += 2) {
    y &= Character.isUpperCase(s[i]);
}
pw.println(y ? "Yes" : "No");

C - Kaprekar Number

やるだけなんだけど実装方針が決まらず迷子に．

long n = sc.nextInt();
int k = sc.nextInt();
long x = n;
for (int i = 0; i < k; i++) {
    if (x == 0) break;
    long _x = x;
    int p = 0;
    while (_x > 0) {
        _x /= 10;
        p += 1;
    }
    int[] c = new int[p];
    int q = 0;
    _x = x;
    while (_x > 0) {
        c[q++] = (int) (_x % 10);
        _x /= 10;
    }
    Arrays.sort(c);
    long g1 = 0, g2 = 0;
    for (int j = 0; j < p; j++) {
        g1 = g1 * 10 + c[j];
        g2 = g2 * 10 + c[p - j - 1];
    }
    x = g2 - g1;
}
pw.println(x);

D - Base n

順位表が真っ赤っか．雑にやるとオーバーフローするのと，桁数が 1 の時がコーナーケースになることが原因？

二分探索で毎回 $M$ 以下になるかを調べればいい．制約は厳しくないので，BigInteger を使っても TL には間に合いそうということで投げると通る．

char[] _x = sc.nextChars();
int n = _x.length;
int[] x = new int[n];
for (int i = 0; i < n; i++) {
    x[i] = _x[i] - '0';
}
int d = IntArrays.max(x);
long m = sc.nextLong();
if (n == 1) {
    pw.println(x[0] <= m ? 1 : 0);
    return;
}
BigInteger bm = BigInteger.valueOf(m);
long l = d, r = m + 1;
Out: while (r - l > 1) {
    BigInteger t = BigInteger.valueOf((l + r) >> 1);
    BigInteger v = BigInteger.ZERO;
    for (int i = 0; i < n; i++) {
        v = v.multiply(t).add(BigInteger.valueOf(x[i]));
        if (v.compareTo(bm) > 0) {
            r = t.longValue();
            continue Out;
        }
    }
    l = t.longValue();
}
pw.println(l - d);

E - Train

Dijkstra をやる．ボトルネック部に剰余演算が追加されて重くなりそうだったので，隣接リストを配列で持って定数倍高速化をした．結果的に多分要らなかったんだけど，万が一の TLE を考えると払ってもいい対価だったと思う．

public static void solve(ExtendedScanner sc, FastPrintStream pw) {
    int n = sc.nextInt();
    int m = sc.nextInt();
    int x = sc.nextInt() - 1;
    int y = sc.nextInt() - 1;
    Edge[] edges = new Edge[m];
    int[] cnt = new int[n];
    for (int i = 0; i < m; i++) {
        int u = sc.nextInt() - 1;
        int v = sc.nextInt() - 1;
        long t = sc.nextLong();
        int k = sc.nextInt();
        
        edges[i] = new Edge(u, v, k, t);
        cnt[u]++;
        cnt[v]++;
    }
    Edge[][] g = new Edge[n][];
    for (int i = 0; i < n; i++) {
        g[i] = new Edge[cnt[i]];
    }
    for (var e : edges) {
        int u = e.u;
        int v = e.v;
        g[u][--cnt[u]] = e;
        g[v][--cnt[v]] = new Edge(v, u, e.k, e.t);
    }

    long[] d = new long[n];
    PriorityQueue<State> pq = new PriorityQueue<>();

    java.util.Arrays.fill(d, Const.LINF);
    d[x] = 0;
    pq.add(new State(x, 0L));
    while (pq.size() > 0) {
        State st = pq.poll();
        int u = st.v;
        if (st.d != d[u]) continue;
        for (var e : g[u]) {
            int v = e.v;
            int k = e.k;
            long c = e.t;
            long r = d[u] % k;
            long du = r == 0 ? d[u] : d[u] + k - r;
            if (du + c < d[v]) {
                d[v] = du + c;
                pq.add(new State(v, d[v]));
            }
        }
    }

    if (d[y] == Const.LINF) {
        pw.println(-1);
    } else {
        pw.println(d[y]);
    }
}

private static final class State implements Comparable<State> {
    final int v;
    final long d;
    State(int v, long d) {this.v = v; this.d = d;}
    public int compareTo(State s) {return d == s.d ? v - s.v : d > s.d ? 1 : -1;}
}

static class Edge {
    int u, v;
    int k;
    long t;
    Edge(int u, int v, int k, long t) {
        this.u = u;
        this.v = v;
        this.k = k;
        this.t = t;
    }
}

F - Potion

選んだ素材の集合を $S$ ， $k=|S|$ とする．

制約より $\displaystyle\sum A_i\leq X$ が保証されているため， $\displaystyle \sum_{i\in S}A_i\equiv X \pmod k$ であることが丁度 $X$ となるための必要十分条件．このとき $\displaystyle \frac{X - \sum _ {i\in S}A _ i}{k}$ の時間が掛かる．

$k=1,\ldots,N$ に対して，次の DP を考える．

$\displaystyle \mathrm{dp}[i][j][m]=\max\left\{ \sum_{x\in S}A_x\;\middle |\; S\subset\{1,\ldots,i\},\;|S|=j,\;\sum_{x\in S}A_x\equiv m\;(\mathrm{mod}\;k) \right\}$