43:47 + 0:00 全完で全体 46 位,日本人 39 位でした.賞金ワンチャンないかな...?
A - Star
コイン 100 枚で 1 up するアレかな? が答え.
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 の時がコーナーケースになることが原因?
二分探索で毎回 以下になるかを調べればいい.制約は厳しくないので,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
選んだ素材の集合を , とする.
制約より が保証されているため, であることが丁度 となるための必要十分条件.このとき の時間が掛かる.
に対して,次の DP を考える.
この DP は以下のようにして計算でき, が を固定した場合の最適値である.
計算量は だが,適切に , の範囲を絞れば定数倍が 1 よりも小さくなり,余裕を持って通すことができる.