AtCoder Beginner Contest 224(Rated範囲外)

コンテスト前のレート:2038
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:273位(2000点、96分17秒)

A - Tires

問題

思考過程
  1. endsWithメソッドを使うことで末尾の判定ができるので、それで末尾が"er"かどうかを判定する。
import java.util.Scanner;

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

        if (s.endsWith("er")) {
            System.out.println("er");
        } else {
            System.out.println("ist");
        }
    }
}

ここまで0分50秒+0ペナ。119位。


B - Mongeness

問題

思考過程
  1. O(H^2W^2)が間に合う制約なので、四重ループを回し、全ての組について条件を満たすか判定する。
  2. 満たさない組が1つでもあった時点で"No"を出力して終了。途中で終了しなければ"Yes"。
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();
        int[][] a = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        sc.close();

        for (int i1 = 0; i1 < h; i1++) {
            for (int i2 = i1 + 1; i2 < h; i2++) {
                for (int j1 = 0; j1 < w; j1++) {
                    for (int j2 = j1 + 1; j2 < w; j2++) {
                        if (a[i1][j1] + a[i2][j2] > a[i1][j2] + a[i2][j1]) {
                            System.out.println("No");
                            return;
                        }
                    }
                }
            }
        }
        System.out.println("Yes");
    }
}

ここまで3分13秒+0ペナ。103位。


C - Triangle?

問題

思考過程
  1. O(N^3)が間に合う制約なので、_NC_3通りの組み合わせを全て調べる。
  2. 三角形の面積が0になるのは3i, j, kが一直線上にある場合なので、それ以外の場合をカウントしたい。
  3. i, jを通る直線とi, kを通る直線の傾きが同じならば、3点は一直線上にある。
  4. \frac{Y_j - Y_i}{X_j - X_i} \ne \frac{Y_k - Y_i}{X_k - X_i}は正確に判定しづらいので、移項して(X_k - X_i)(Y_j - Y_i) \ne (X_j - X_i)(Y_k - Y_i)を判定する。
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 = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        sc.close();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                for (int k = 0; k < j; k++) {
                    long dx1 = x[j] - x[i];
                    long dx2 = x[k] - x[i];
                    long dy1 = y[j] - y[i];
                    long dy2 = y[k] - y[i];
                    if (dx2 * dy1 != dx1 * dy2) {
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで6分40秒+0ペナ。87位。


D - 8 Puzzle on Graph

問題

思考過程
  1. あり得るコマの配置(以下盤面)が9!通り程度に収まるため、それらの盤面を頂点、コマの移動を辺に見立てたグラフでBFSを行う。
  2. 盤面を表す情報は、各コマが置かれている頂点番号を連結した数値か文字列としたい。初期盤面であれば入力のpをそのまま連結したもの。
  3. 数値か文字列かは、実装が楽な方にしたいが、文字列の方が1桁入れ替える処理を実装しやすいと判断した。
  4. コマの移動に合わせて盤面情報を作り直すことができれば、あとは普通にBFSを行うだけ。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = 9;
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            list.get(u).add(v);
            list.get(v).add(u);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 8; i++) {
            int p = sc.nextInt() - 1;
            sb.append(p);
        }
        sc.close();

        String s = sb.toString();
        Queue<String> que = new ArrayDeque<>();
        que.add(s);
        Map<String, Integer> map = new HashMap<>();
        map.put(s, 0);
        while (!que.isEmpty()) {
            String cur = que.poll();
            int x = 36; // 0~8の合計
            // 合計から各桁の値を引くことで、curに含まれていない値を得る
            for (int i = 0; i < 8; i++) {
                x -= cur.charAt(i) - '0';
            }
            for (int y : list.get(x)) {
                // コマを頂点y→xに移動
                String next = cur.replace((char) ('0' + y), (char) ('0' + x));
                if (!map.containsKey(next)) {
                    que.add(next);
                    map.put(next, map.get(cur) + 1);
                }
            }
        }
        if (map.containsKey("01234567")) {
            System.out.println(map.get("01234567"));
        } else {
            System.out.println(-1);
        }
    }
}

ここまで17分55秒+0ペナ。52位。


E - Integers on Grid

問題

思考過程
  1. a_iが大きいマスから順に処理し、既に処理済みのマスへのみ移動させられるとすることで、「真に大きい」の条件を満たせる。a_iが同じである処理済みマスを見てしまわないようにする必要はあるが。
  2. 各マスは、「他のマスへ移動できるならば「移動先マスの答え+1」の最大値が答え」といった形でa_iが大きいマスから埋めていくDPができる。
     
  3. 移動先の候補として処理済みマスを全て調べてしまったら各マスごとにO(N)かかり、全体でO(N^2)となりTLE。
  4. 各行、各列ごとの最大値だけ保持しておくようにすれば、各マスごとにO(1)で済む。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        int n = Integer.parseInt(sa[2]);
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o2.a - o1.a);
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.i = i;
            o.x = Integer.parseInt(sa[0]) - 1;
            o.y = Integer.parseInt(sa[1]) - 1;
            o.a = Integer.parseInt(sa[2]);
            que.add(o);
            arr[i] = o;
        }
        br.close();

        int[] mx = new int[h]; // 各行の最大値
        int[] my = new int[w]; // 各列の最大値
        Arrays.fill(mx, -1);
        Arrays.fill(my, -1);
        Queue<Obj> que2 = new ArrayDeque<>(); // aが同じものを溜めておく
        while (!que.isEmpty()) {
            Obj o = que.poll();
            while (!que2.isEmpty() && que2.peek().a > o.a) {
                Obj o2 = que2.poll();
                mx[o2.x] = Math.max(mx[o2.x], o2.ans);
                my[o2.y] = Math.max(my[o2.y], o2.ans);
            }
            o.ans = Math.max(mx[o.x], my[o.y]) + 1;
            que2.add(o);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (Obj o : arr) {
            pw.println(o.ans);
        }
        pw.flush();
    }

    static class Obj {
        int i, x, y, a, ans;
    }
}

ここまで28分25秒+0ペナ。43位。


F - Problem where +s Separate Digits

問題
下記の「i文字目」は0-indexedとする。

思考過程
  1. 特定の数が何回現れるかという方向性で考えてみる。
  2. Si文字目がどれくらい最終的な答えに寄与するかを考えてみる。
  3. Si文字目が1の位で何回、10の位で何回、\cdots10^{|S|-1}の位で何回現れるかを、例1を書き出して調べてみる。
  4. まず1の位で何回現れるかは、i文字目の直後で切られることが前提で、
    • i文字目より左側は、i箇所を切る切らないを自由に選択可能なので、2^i通り。
    • i文字目より右側は、|S|-i-2箇所を切る切らないを自由に選択可能なので、2^{|S|-i-2}通り。
  5. 10の位、100の位、\cdotsと調べていくと、上記1点目は変わらず、2点目は選択可能箇所が1つずつ減っていき、通り数としては半分ずつになっていく。ただし、最後は1通りが2回。
     
  6. 以上をまとめると、\sum_{i=0}^{|S|-1}S_i 2^i \sum_{j=0}^{|S|-i-1} 10^j 2^{max(|S|-i-2-j, 0)}を求めたい。
  7. jに関する総和の部分について高速化する必要があるので、累乗や累積和等の前計算をしておき、頑張って帳尻合わせをする。
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));
        char[] s = br.readLine().toCharArray();
        br.close();

        int n = s.length;
        int mod = 998244353;
        int m2 = (mod + 1) / 2;
        long[] b = new long[n + 5];  // b[i] = 2^i +5は適当に予備
        long[] bm = new long[n + 5]; // bm[i] = 2^iの逆元
        long[] t = new long[n + 5];  // t[i] = 10^i
        long[] tot = new long[n + 6]; // tの累積和
        b[0] = 1;
        bm[0] = 1;
        t[0] = 1;
        tot[1] = 1;
        for (int i = 1; i < t.length; i++) {
            b[i] = b[i - 1] * 2 % mod;
            bm[i] = bm[i - 1] * m2 % mod;
            t[i] = t[i - 1] * 10 % mod;
            tot[i + 1] = (tot[i] + t[i]) % mod;
        }

        long[] t2 = new long[n + 5]; // t[i]に2^(n+4-i)の重みを付けたもの
        long[] tot2 = new long[n + 6]; // t2の累積和
        int n4 = n + 4;
        for (int i = 0; i < t2.length; i++) {
            t2[i] = t[i] * b[n4 - i] % mod;
            tot2[i + 1] = (tot2[i] + t2[i]) % mod;
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            int c = s[i] - '0';
            int ni = n - i;
            long v1 = c;    // s[i]の値
            long v2 = b[i]; // 左側
            long v3 = 0;    // 右側
            int x1 = ni - 2;
            if (x1 > 0) {
                int x2 = n4 - x1;
                long x3 = bm[x2]; // t2の重みの帳尻合わせ
                long v31 = tot2[x1] * x3 % mod;
                long v32 = (tot[ni] - tot[x1] + mod) % mod;
                v3 = (v31 + v32) % mod;
            } else {
                v3 = tot[ni];
            }
            long val = v1 * v2 % mod * v3 % mod;
            ans += val;
        }
        ans %= mod;
        System.out.println(ans);
    }
}

ここまで90分44秒+0ペナ。238位。


Gは10分では無理。


終結果:ABCDEFの6完2000点、90分44秒、246位、パフォーマンス2092相当
レート変動:2038(Unrated)


結果がまずまずなのはEが上手いことすぐ解けただけで、Fももっとすんなり解けないと駄目なんだろうなという感じ。