モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238）(Rated範囲外)

A - Exponential or Quadratic
- 思考過程
B - Pizza
- 思考過程
C - digitnum
- 思考過程
D - AND and SUM
- 思考過程
E - Range Sums
- 思考過程

コンテスト前のレート：2074
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：306位（2000点、95分33秒）

A - Exponential or Quadratic

思考過程

$n$ が十分大きければ $2^n \gt n^2$ だが、小さい時は微妙なので、 $n \le 6$ の時の値を全部書き出してみる。
以下より、 $n=1$ と $n \ge 5$ の場合条件を満たすことがわかる。

     2^n  n^2
n=1    2    1
n=2    4    4
n=3    8    9
n=4   16   16
n=5   32   25
n=6   64   36

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

        if (n == 1 || n >= 5) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで2分14秒＋0ペナ。1032位。

B - Pizza

問題

思考過程

少し見方を変えれば、長さ $360$ の円環に距離 $A_i$ ごとに切れ込みを入れる操作を行っているとみなすことができる。
切れ込みが入っているかどうかを長さ $360$ のboolean型配列で持ってもよいが、切れ込みの位置の集合を持っておいた方が、位置の差を計算しやすそう。

import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        TreeSet<Integer> set = new TreeSet<>();
        int x = 0;
        set.add(0);
        set.add(360);
        for (int i = 0; i < n; i++) {
            x += a[i];
            x %= 360;
            set.add(x);
        }

        Integer[] arr = set.toArray(new Integer[0]);
        int ans = 0;
        for (int i = 1; i < arr.length; i++) {
            ans = Math.max(ans, arr[i] - arr[i - 1]);
        }
        System.out.println(ans);
    }
}

ここまで6分32秒＋0ペナ。369位。

C - digitnum

問題

思考過程

$1$ 桁の数は $9$ 個、 $2$ 桁の数は $90$ 個、 $\cdots$ のように $1$ 桁増えるごとに個数は $10$ 倍になっていく。
$N$ から $9$ を引いて答えに $1$ ～ $9$ の和を加算する。
$N$ から $90$ を引いて答えに $1$ ～ $90$ の和を加算する。
$\cdots$
のような繰り返し処理ができる。
ただし、 $i$ 回目の操作で $9 \times 10^{i-1}$ を下回った場合は $1$ ～ $N$ の和を求めて終了する。

import java.util.Scanner;

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

        int mod = 998244353;
        long a = 9;
        long ans = 0;
        while (n > 0) {
            if (n <= a) {
                ans += n % mod * (n % mod + 1) / 2;
                ans %= mod;
                break;
            }
            ans += a % mod * (a % mod + 1) / 2;
            ans %= mod;
            n -= a;
            a *= 10;
        }
        System.out.println(ans);
    }
}

ここまで15分00秒＋0ペナ。280位。

D - AND and SUM

問題

思考過程

$x, y$ は、 $a$ を $2$ 進数で表した時に $1$ となる桁は共に $1$ であり、 $0$ となる桁は両方 $0$ か片方のみ $1$ である必要がある。
その高々一方が $1$ となる部分を単一の数 $c$ で表すとすると、 $x = a + c$ 、 $y = a$ より、 $s = 2a + c$ となり、 $c = s - 2a$ となる。
$c$ と $a$ で $1$ となる桁が重複していなければ"Yes"。
$2$ 数の $1$ である桁が重複していないかは、ANDを取って $0$ かどうかで判定できる。

import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        PrintWriter pw = new PrintWriter(System.out);
        for (int z = 0; z < t; z++) {
            long a = sc.nextLong();
            long s = sc.nextLong();

            long b = a * 2;
            long c = s - b;
            if (c >= 0 && (a & c) == 0) {
                pw.println("Yes");
            } else {
                pw.println("No");
            }
        }
        pw.flush();
        sc.close();
    }
}

ここまで21分05秒＋0ペナ。206位。

E - Range Sums

問題

思考過程

なんとなくUnionFindっぽさを感じて仕方がない。
ただし例３のようにたった $1$ つの情報で"Yes"となることもあり得るので、全体が連結になる必要があるわけではない。
$0$ ～ $N$ の $N+1$ 個の点を持ち、 $(l_i, r_i)$ では $l_i-1$ と $r_i$ を連結することにし、最終的に $0$ と $N$ が同一連結成分になっていれば"Yes"となりそう。
例えば $0-7$ 間と $0-3$ 間の値がわかれば、 $3-7$ 間の値も求められるようになることから、確かに $0-3-7$ の任意の $2$ 点間の値を求められるようになっている。

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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int q = Integer.parseInt(sa[1]);

        UnionFind uf = new UnionFind(n + 1);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int l = Integer.parseInt(sa[0]) - 1;
            int r = Integer.parseInt(sa[1]);
            uf.union(l, r);
        }
        br.close();

        if (uf.same(0, n)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    // 以下ライブラリ

    static class UnionFind {
        int[] parent, size;
        int num = 0; // 連結成分の数

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            num = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        void union(int x, int y) {
            int px = find(x);
            int py = find(y);
            if (px != py) {
                parent[px] = py;
                size[py] += size[px];
                num--;
            }
        }

        int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            parent[x] = find(parent[x]);
            return parent[x];
        }

        /**
         * xとyが同一連結成分か
         */
        boolean same(int x, int y) {
            return find(x) == find(y);
        }

        /**
         * xを含む連結成分のサイズ
         */
        int size(int x) {
            return size[find(x)];
        }
    }
}