AtCoder Beginner Contest 221(Rated範囲外)

A - Seismic magnitude scales
- 思考過程
B - typo
- 思考過程
C - Select Mul
- 思考過程
D - Online games
- 思考過程
E - LEQ
- 思考過程
F - Diameter set
- 思考過程

コンテスト前のレート：2005
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：339位（1500点、35分59秒）

A - Seismic magnitude scales

思考過程

$A-B$ 回 $32$ 倍する。
$6$ 回 $32$ 倍したときにintの範囲を超えないか考え、 $4 \times 6 \lt 31$ だが念のためlong型にしておいた。

import java.util.Scanner;

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

        long ans = 1;
        for (int i = b; i < a; i++) {
            ans *= 32;
        }
        System.out.println(ans);
    }
}

ここまで1分12秒＋0ペナ。485位。

B - typo

問題
Bとしては結構大変だった。というか大変にしてしまったかも。

思考過程

とりあえず最初から一致している場合は"Yes"。残りは $1$ 回入れ替えるケースだけ考える。
$1$ 回だけ入れ替えて一致するためには、まず連続する $2$ 文字 $1$ 箇所だけが不一致である必要がある。
$S_i \ne T_i$ である $i$ をリスト化する。
リストの要素数が $2$ でない場合は"No"。
リストの $2$ 要素の差が $1$ でない場合は"No"。
あとは入れ替えて一致するかどうかを判定する。

import java.util.ArrayList;
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);
        String s = sc.next();
        String t = sc.next();
        sc.close();

        // 1
        if (s.equals(t)) {
            System.out.println("Yes");
        } else {
            // 3
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) != t.charAt(i)) {
                    list.add(i);
                }
            }
            // 4
            if (list.size() != 2) {
                System.out.println("No");
                return;
            }
            // 5
            int a = list.get(0);
            int b = list.get(1);
            if (a + 1 != b) {
                System.out.println("No");
                return;
            }
            // 6
            if (s.charAt(a) == t.charAt(b) && s.charAt(b) == t.charAt(a)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}

ここまで4分55秒＋0ペナ。666位。

C - Select Mul

問題

思考過程

$N$ の各桁を $2$ グループに分けた後は、グループ内で降順に並べ替えるのが最適。
グループの分け方は全通り試しても、 $2^{10}$ 通り以下には収まるので全探索する。

解説を見て、先に降順ソートしてからグループ分けすれば余計なコードがだいぶ減ったと気付いた。

import java.util.ArrayList;
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);
        char[] s = sc.next().toCharArray();
        sc.close();

        int n = s.length;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = s[i] - '0';
        }

        long ans = 0;
        int end = 1 << n;
        for (int i = 0; i < end; i++) {
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) {
                    list1.add(a[j]);
                } else {
                    list2.add(a[j]);
                }
            }
            // 各グループを降順に並べ替え
            Collections.sort(list1, Collections.reverseOrder());
            Collections.sort(list2, Collections.reverseOrder());
            // 空または0のみの場合はスキップ
            if (list1.isEmpty() || list2.isEmpty()
                    || list1.get(0) == 0 || list2.get(0) == 0) {
                continue;
            }

            int v1 = 0;
            for (int j = 0; j < list1.size(); j++) {
                v1 *= 10;
                v1 += list1.get(j);
            }
            int v2 = 0;
            for (int j = 0; j < list2.size(); j++) {
                v2 *= 10;
                v2 += list2.get(j);
            }
            long val = (long) v1 * v2;
            ans = Math.max(ans, val);
        }
        System.out.println(ans);
    }
}

ここまで9分18秒＋0ペナ。199位。

D - Online games

問題

思考過程

各日の人数をいもす法で求めたいが、 $A, B$ の制約が大きくて配列では駄目なので、マップ＜ $K$ 日目以降、 $V$ 人＞上で行う。
$i$ 日目の人数を $V_i$ とすると、日数分ループして $D_{V_i}$ をインクリメントしていきたいところだが、 $1$ ずつ加算する代わりにマップのキー間の差を加算する。

import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = a + b;
            map.put(a, map.getOrDefault(a, 0) + 1);
            map.put(c, map.getOrDefault(c, 0) - 1);
        }
        sc.close();

        // いもす法
        Integer[] arr = map.keySet().toArray(new Integer[0]);
        int val = 0;
        for (Integer key : arr) {
            val += map.get(key);
            map.put(key, val);
        }

        int[] d = new int[n + 1];
        for (int i = 1; i < arr.length; i++) {
            // e日間の間v人が続いている
            int e = arr[i] - arr[i - 1];
            int v = map.get(arr[i - 1]);
            d[v] += e;
        }

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

ここまで18分28秒＋0ペナ。236位。

E - LEQ

問題
過去問で一度同じようなことをやったことがある覚えはあるのだが、どの問題かはすぐに出てこない。

思考過程

$A'_1$ と $A'_k$ の組み合わせを数えることを考える。
BITを使い、前から順に位置 $A_i$ に $+1$ していくと、 $A_i$ について求める際、 $A_{i-1}$ までの情報がBITに入っているので、 $A_i$ 以下の値の数を取得することで、 $A_i$ とペアにできる数がわかる。
ただし、 $A_i$ の制約が大きいので、あらかじめ座標圧縮をしておく。
　
基本的な構造はこれでよさそうだが、とペアになる各について、間の要素を含めるかどうかを自由に決められるので、倍しなければならない。仮に単調増加列であれば、
- $A'_k = A_2$ の場合について $1$ 通り
- $A'_k = A_3$ の場合について $2+1$ 通り
- $A'_k = A_4$ の場合について $4+2+1$ 通り
  　 $\cdots$
  　
この重み付けを実現するためには、BITに追加する際 $+1$ するのではなく、 $+2^{N-1-i}$ する形にしておき、取得した合計を $2^{N-i}$ で割って帳尻を合わせるようにする。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        int mod = 998244353;
        int m2 = (mod + 1) / 2;  // 2の逆元
        int[] p = new int[n];    // 2のi乗
        long[] pi = new long[n]; // 2のi乗の逆元
        p[0] = 1;
        pi[0] = 1;
        for (int i = 1; i < p.length; i++) {
            p[i] = p[i - 1] * 2 % mod;
            pi[i] = pi[i - 1] * m2 % mod;
        }

        int[] b = zaatu(a);
        BIT bit = new BIT(n);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                long v1 = bit.sum(b[i]) % mod;
                long v2 = pi[n - i];
                ans += v1 * v2 % mod;
            }
            bit.add(b[i], p[n - 1 - i]);
        }
        ans %= mod;
        System.out.println(ans);
    }

    // 以下ライブラリ

    static int[] zaatu(long[] a) {
        TreeMap<Long, Integer> map = new TreeMap<>();
        for (int i = 0; i < a.length; i++) {
            map.put(a[i], null);
        }
        Long[] arr = map.keySet().toArray(new Long[0]);
        int cnt = 0;
        for (Long i : arr) {
            cnt++;
            map.put(i, cnt);
        }
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[i] = map.get(a[i]);
        }
        return b;
    }

    static class BIT {
        int n;
        long[] arr;

        public BIT(int n) {
            this.n = n;
            arr = new long[n + 1];
        }

        void add(int idx, long val) {
            for (int i = idx; i <= n; i += i & -i) {
                arr[i] += val;
            }
        }

        long sum(int idx) {
            long sum = 0;
            for (int i = idx; i > 0; i -= i & -i) {
                sum += arr[i];
            }
            return sum;
        }
    }
}

ここまで34分28秒＋0ペナ。158位。

F - Diameter set

問題
公式解説に書かれているレベルの解法は合っていたのに、手抜きした結果、多分木の中心または中心を含む辺を正しく求められていなくて通らず。

思考過程

直径が偶数（中心が頂点）の場合と、奇数（中心が辺の中央）の場合に分けて考える。
　
偶数の場合
1. 例２を見て、中心から距離が $\frac{D}{2}$ である点の数を $X$ 個とすると、 $X$ 個の中から $2$ 個以上を選ぶ通り数を求めればよい？
2. それだと、中心以外で枝分かれしている場合がおかしい。
3. 中心の隣を根とした部分木ごとに分け、各部分木で根から距離が $\frac{D}{2}-1$ である点の数を $Y$ 個とすると、部分木 $i$ では $Y_i$ 個の中から $1$ 個以下を選び、 $1$ 個選ぶ部分木が $2$ 個以上という条件に合致する通り数を求めることになる。
  　
奇数の場合
1. 中心となる辺で切った $2$ つの部分木（切った辺の両端がそれぞれの根）について、根から距離が $\lfloor \frac{D}{2} \rfloor$ である点の数をそれぞれ $Y_1, Y_2$ 個とする。
2. 両方から $1$ つずつ選ぶ必要があるので、 $Y_1 \times Y_2$ 通り。