AtCoder Beginner Contest 254

コンテスト前のレート：1991
レート通りのパフォーマンスが得られる順位：336位（2000点、68分55秒）

A - Last Two Digits

問題

思考過程

1. で割った余りを取るだけ？　と思ったら例２を見たら先頭のも出力しなければならない。
2. が必ず桁という制約なので、入力を文字列で受け取って先頭の文字だけ除いて出力すればよい。

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

        System.out.println(s.substring(1));
    }
}

ここまで0分53秒＋0ペナ。539位。

B - Practical Computing

問題

思考過程

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

        long[][] pas = new long[n + 1][n + 1];
        pas[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                pas[i + 1][j] += pas[i][j];
                pas[i + 1][j + 1] += pas[i][j];
            }
        }

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

ここまで2分56秒＋0ペナ。126位。

C - K Swap

問題

思考過程

1. 個置きの要素同士は自由に並べ替えられるという形をしている。
2. ごとにグループ分けしてそれぞれをソートしたものと、全体をソートしたものが一致すれば"Yes"。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
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[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int[] b = Arrays.copyOf(a, n);
        Arrays.sort(b);

        List<List<Integer>> list = new ArrayList<>(k);
        for (int i = 0; i < k; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            list.get(i % k).add(a[i]);
        }
        for (int i = 0; i < k; i++) {
            List<Integer> list2 = list.get(i);
            Collections.sort(list2);
            for (int j = 0; j < list2.size(); j++) {
                if (list2.get(j) != b[j * k + i]) {
                    System.out.println("No");
                    return;
                }
            }
        }
        System.out.println("Yes");
    }
}

ここまで7分38秒＋0ペナ。163位。

D - Together Square

問題

思考過程

1. とりあえず以下の平方数を全て求めてみる。の場合個ほど。
2. の各に対する最小のは、を素因数分解して指数が奇数である素因数の積を取ったものになる。
3. 各について、以下の平方数の数（これは上記1.で求めたリストを二分探索する）を答えに足していく。
4. 計算量がよくわからなかったが、を実行してみて全然大丈夫だったので提出する。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
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();
        sc.close();

        // 1
        List<Integer> sq = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            sq.add(i * i);
        }

        Eratosthenes era = new Eratosthenes(n);
        long ans = 0;
        label:
        for (int i = 1; i <= n; i++) {
            Map<Integer, Integer> map = era.bunkai(i);
            // 2
            long j = 1;
            for (int k : map.keySet()) {
                int v = map.get(k) % 2;
                if (v == 1) {
                    j *= k;
                    if (j > n) {
                        continue label;
                    }
                }
            }
            // 3
            int idx = binarySearch(sq, n / j);
            ans += idx + 1;
        }
        System.out.println(ans);
    }

    // sq内で値がval以下である最大のindex
    static int binarySearch(List<Integer> sq, long val) {
        int ng = sq.size();
        int ok = -1;
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (sq.get(mid) <= val) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok;
    }

    // 以下ライブラリ

    static class Eratosthenes {
        int[] div;

        public Eratosthenes(int n) {
            div = new int[n + 1];
            if (n < 2) return;
            div[0] = -1;
            div[1] = -1;
            int end = (int) Math.sqrt(n) + 1;
            for (int i = 2; i <= end; i++) {
                if (div[i] == 0) {
                    div[i] = i;
                    for (int j = i * i; j <= n; j+=i) {
                        if (div[j] == 0) div[j] = i;
                    }
                }
            }
            for (int i = end + 1; i <= n; i++) {
                if (div[i] == 0) div[i] = i;
            }
        }

        public Map<Integer, Integer> bunkai(int x) {
            Map<Integer, Integer> soinsu = new HashMap<>();
            while (x > 1) {
                Integer d = div[x];
                soinsu.put(d, soinsu.getOrDefault(d, 0) + 1);
                x /= d;
            }
            return soinsu;
        }

        public boolean isSosuu(int x) {
            return div[x] == x;
        }
    }
}

ここまで16分34秒＋0ペナ。165位。

E - Small d and k

問題

思考過程

1. 次数が以下なので、距離までBFSしてもそんなに多くの頂点にはたどり着かない。単純に回BFSするだけでよさそう。
2. ただし、訪問した頂点を管理するのに毎回の配列を生成しては駄目なので、Map＜頂点、距離＞で管理することにする。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
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 n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>(4));
        }
        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;
            list.get(a).add(b);
            list.get(b).add(a);
        }
        int q = Integer.parseInt(br.readLine());
        int[] x = new int[q];
        int[] k = new int[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            x[i] = Integer.parseInt(sa[0]) - 1;
            k[i] = Integer.parseInt(sa[1]);
        }
        br.close();

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            Queue<Integer> que = new ArrayDeque<>();
            que.add(x[i]);
            Map<Integer, Integer> map = new HashMap<>();
            map.put(x[i], 0);
            int ans = x[i] + 1;
            while (!que.isEmpty()) {
                int cur = que.poll();
                if (map.get(cur) == k[i]) {
                    break;
                }
                for (int next : list.get(cur)) {
                    if (!map.containsKey(next)) {
                        que.add(next);
                        ans += next + 1;
                        map.put(next, map.get(cur) + 1);
                    }
                }
            }
            pw.println(ans);
        }
        pw.flush();
    }
}

ここまで25分18秒＋0ペナ。141位。

F - Rectangle GCD

問題

思考過程

1. 実際にグリッドに値を書き込んでみてとの公約数がどうなっているかを調べてみると、値の差分はである。
2. よって、を差の数列に置き換えた上で、～および～に当たる部分の区間GCDととのGCDを求める。
3. 区間GCDって求められるんだっけ？と思ったが、普通にセグ木が使える。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.function.BinaryOperator;
import java.util.function.Predicate;

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

        Integer[] aa = new Integer[n];
        aa[0] = 0;
        for (int i = 1; i < n; i++) {
            aa[i] = Math.abs(a[i] - a[i - 1]);
        }
        SegTree<Integer> st1 = new SegTree<>(aa, 0, (v1, v2) -> gcd(v1, v2));

        Integer[] bb = new Integer[n];
        bb[0] = 0;
        for (int i = 1; i < n; i++) {
            bb[i] = Math.abs(b[i] - b[i - 1]);
        }
        SegTree<Integer> st2 = new SegTree<>(bb, 0, (v1, v2) -> gcd(v1, v2));

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int h1 = Integer.parseInt(sa[0]);
            int h2 = Integer.parseInt(sa[1]);
            int w1 = Integer.parseInt(sa[2]);
            int w2 = Integer.parseInt(sa[3]);

            int g1 = 0;
            if (h1 < h2) {
                g1 = st1.prod(h1, h2);
            }
            int g2 = 0;
            if (w1 < w2) {
                g2 = st2.prod(w1, w2);
            }
            int g = gcd(g1, g2);

            int ans = gcd(g, a[h1 - 1] + b[w1 - 1]);
            pw.println(ans);
        }
        pw.flush();
        br.close();
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

// 以下ACLを移植したSegTree

提出
ここまで42分40秒＋0ペナ。132位。

GよりExの方が正解者数が多かったので一応両方見たが、Gの方が解ける可能性がありそうに見えて残り時間はほぼGに集中。
エレベーター（の）とクエリ（の）をまとめてPriorityQueueに入れて、有効なエレベーターの集合を管理しながら階数の小さい順に見ていくとかでできないかと考えたが、ちんたら実装していたら時間切れ。
結局最初と最後に連絡通路を使う必要があるのかどうかとかで詰まりそうな気もしたが。

最終結果：ABCDEFの6完2000点、42分40秒、173位、パフォーマンス2245
レート変動：1991→2019（+28）

青→黄がこれで6回目。また無事黄色に復帰できた。

トライ木の問題をもう5回くらい落としている気がするので、いい加減使えるようになりたい。