AtCoder Beginner Contest 250

ABC

コンテスト前のレート：1995
レート通りのパフォーマンスが得られる順位：273位（2000点、91分19秒）

A - Adjacent Squares

問題
一瞬慌てて1行かどうかとかで場合分けしそうになったが、冷静に考え直す。

思考過程
  1. 上下左右それぞれの方向を確認し、端でなければ答えを+1する。
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 r = sc.nextInt();
        int c = sc.nextInt();
        sc.close();

        int ans = 0;
        if (1 < r) ans++;
        if (r < h) ans++;
        if (1 < c) ans++;
        if (c < w) ans++;
        System.out.println(ans);
    }
}

ここまで2分21秒＋0ペナ。428位。


B - Enlarged Checker Board

問題

思考過程
  1. とりあえず縦A \times N、横B \times Nのループを回してみる。
  2. ループカウンタをAやBで割ることで、上からおよび左から何枚目のタイルかがわかる。
  3. 2つのループカウンタの合計の偶奇で市松模様に分けられることをイメージすると、上記2.の結果に対して同様のことを行うとよさそう。
  4. サンプルが問題ないことを確かめる。
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 a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();

        int an = a * n;
        int bn = b * n;
        char[][] s = new char[an][bn];
        for (int i = 0; i < an; i++) {
            for (int j = 0; j < bn; j++) {
                int x = i / a;
                int y = j / b;
                if ((x + y) % 2 == 0) {
                    s[i][j] = '.';
                } else {
                    s[i][j] = '#';
                }
            }
        }
        for (int i = 0; i < an; i++) {
            System.out.println(s[i]);
        }
    }
}

ここまで6分00秒＋0ペナ。210位。


C - Adjacent Swaps

問題

思考過程
  1. 値がx_iである位置を探すのにO(N)かけては駄目なので、位置も管理してO(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();
        int q = sc.nextInt();
        int[] x = new int[q];
        for (int i = 0; i < q; i++) {
            x[i] = sc.nextInt() - 1;
        }
        sc.close();

        int[] a = new int[n]; // i番目の値
        int[] p = new int[n]; // 値iの位置
        for (int i = 0; i < n; i++) {
            a[i] = i;
            p[i] = i;
        }

        for (int i = 0; i < q; i++) {
            int cp = p[x[i]]; // 入れ替え元の位置
            int np = cp + 1;  // 入れ替え先の位置
            if (cp == n - 1) {
                np = cp - 1;
            }
            int nx = a[np]; // 入れ替え先の値
            a[np] = a[cp];
            a[cp] = nx;
            p[x[i]] = np;
            p[nx] = cp;
        }

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

ここまで10分42秒＋0ペナ。137位。


D - 250-like Number

問題

思考過程
  1. q \leq 10^6のため、とりあえずqを全探索することを考える。
  2. 素数だけが対象だったので、素数判定にエラトステネスの篩を使う。
  3. 計算量が心配だが、とりあえず各qに対して2 \leq p \lt qとなるpを素数のみ全探索してみる。
  4. 例３ではTLEにはならなそうだったが、念のためN=10^{18}を試してみたら10秒近くかかった。
  5. pを全部試すのではなく二分探索に変更。せっかくなので上記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);
        long n = sc.nextLong();
        sc.close();

        int m = 1000000;
        Eratosthenes era = new Eratosthenes(m);
        List<Long> sosuu = new ArrayList<>(); // q未満の素数格納用
        sosuu.add(2L);
        int ans = 0;
        for (int q = 3; q <= m; q++) {
            if (!era.isSosuu(q)) {
                continue;
            }
            long q3 = (long) q * q * q;
            if (q3 < n) {
                int idx = binarySearch(sosuu, n / q3);
                ans += idx + 1;
                sosuu.add((long) q);
            }
        }
        System.out.println(ans);
    }

    // 値がval以下である最大のindexを取得
    static int binarySearch(List<Long> list, long val) {
        int ok = -1;
        int ng = list.size();
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (list.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;
        }
    }
}

ここまで24分38秒＋0ペナ。359位。


E - Prefix Equality

問題

思考過程
  1. クエリを都合の良い順番に並び替えることも検討したが、各xに対して条件を満たすyの範囲を前計算しておけそう。
  2. 具体的には、例１であれば以下のような情報を求めておく。
    • 1\cdots1～1
    • 2\cdots2～3
    • 3\cdotsNG
    • 4\cdots5～5
    • 5\cdotsNG
  3. あとは、AやBの既出値を管理するSet、AやBの一方のみ既出である値を管理するSetを用意して頑張る。（ソース内コメント参照）
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

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

        int[] l = new int[n]; // 条件を満たすyの下限
        int[] r = new int[n]; // 条件を満たすyの上限
        Arrays.fill(l, -1);
        Arrays.fill(r, -1);
        Set<Integer> seta = new HashSet<>(); // aで既出
        Set<Integer> setb = new HashSet<>(); // bで既出
        Set<Integer> wka = new HashSet<>();  // aのみで既出
        Set<Integer> wkb = new HashSet<>();  // bのみで既出
        int j = 0; // bのindex
        for (int i = 0; i < n; i++) {
            if (seta.contains(a[i])) {
                l[i] = l[i - 1];
                r[i] = r[i - 1];
            } else {
                // a[i]を追加
                seta.add(a[i]);
                // bのみ既出の集合から除外
                // bで出てきていないならばaのみ既出に追加
                if (!wkb.remove(a[i]) && !setb.contains(a[i])) {
                    wka.add(a[i]);
                }

                // a[i]と同じ値が出てくるまでb側を進める
                while (!setb.contains(a[i]) && j < n) {
                    setb.add(b[j]);
                    if (!wka.remove(b[j]) && !seta.contains(b[j])) {
                        wkb.add(b[j]);
                    }
                    j++;
                }
                // b側に最後までa[i]が出てこなければ以降条件を満たすことはない
                if (!setb.contains(a[i])) {
                    break;
                }

                // 一方でのみ既出な値がなく、既出値の数が同じであれば条件を満たしている
                if (wka.isEmpty() && wkb.isEmpty() && seta.size() == setb.size()) {
                    l[i] = j - 1;
                    // bの既出値の集合が変わらない間は条件を満たし続ける
                    while (j < n && setb.contains(b[j])) {
                        j++;
                    }
                    r[i] = j - 1;
                }
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            if (l[x[i]] != -1 && l[x[i]] <= y[i] && y[i] <= r[x[i]]) {
                pw.println("Yes");
            } else {
                pw.println("No");
            }
        }
        pw.flush();
    }
}

ここまで55分12秒＋1ペナ。428位。



残り時間のほとんどはG問題を考えていたが解けず。



最終結果：ABCDEの5完1500点、60分12秒、565位、パフォーマンス1698
レート変動：1995→1969（-26）


だいたい最近のABCの平均くらいの結果ではあったが、本当に何でABCはこんなに上手くいかないんだろう・・・。
なんとか昨日のAGCと合わせてわずかにプラス。

ノルマ達成に関わる1問が解けていなかったり、1問手前まで解けるのが遅かったりするから結果があまり良くないのだが、前者は解けないものはどうしようもないので、やっぱり解ける問題を素早く解くことが平均的に傷を浅くすることに繋がりそう。