AtCoder Beginner Contest 241(Rated範囲外)

ABC

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

A - Digit Machine

問題

思考過程
  1. a_xをxに代入する処理を3回行う。
import java.util.Scanner;

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

        int x = 0;
        x = a[x];
        x = a[x];
        x = a[x];
        System.out.println(x);
    }
}

ここまで1分09秒＋0ペナ。261位。


B - Pasta

問題

思考過程
  1. A_iを全部MultiSet（自作）に突っ込み、そこからB_iを取り除く操作に一度も失敗しなければ"Yes"。
import java.util.HashMap;
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();
        int m = sc.nextInt();
        MultiSet<Integer> set = new MultiSet<>();
        for (int i = 0; i < n; i++) {
            set.add(sc.nextInt());
        }
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }
        sc.close();

        for (int i = 0; i < m; i++) {
            if (!set.contains(b[i])) {
                System.out.println("No");
                return;
            }
            set.remove(b[i]);
        }
        System.out.println("Yes");
    }

    // 以下ライブラリ

    static class MultiSet<T> {
        Map<T, Integer> map = new HashMap<>();
        int size = 0;

        void add(T e) {
            map.put(e, map.getOrDefault(e, 0) + 1);
            size++;
        }

        void remove(T e) {
            if (e != null && map.containsKey(e)) {
                int val = map.get(e);
                if (val == 1) {
                    map.remove(e);
                } else {
                    map.put(e, val - 1);
                }
                size--;
            }
        }

        boolean contains(T e) {
            return map.containsKey(e);
        }
    }
}

ここまで3分34秒＋0ペナ。358位。


C - Connect 6

問題
直す内に一方向調べる処理が長くなっていき、メソッド化すればよかったと思った。
3回目のWAは、めんどくさくなって提出したらサンプルも通っていなかった。さすがにひどい。

思考過程
  1. 始点を全マス試し、始点から縦（下方向）、横（右方向）、斜め（右下方向）を6マス調べ、はみ出すか'#'でないマスが2個以下であればOK。　→WA
  2. 斜め左下方向も調べる必要があった。　→WA
  3. はみ出すマスは1個もあっては駄目だった。　→実装ミスでWAの後AC
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();
        char[][] s = new char[n][n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 下
                int ng = 0;
                int ng2 = 0;
                for (int k = 0; k < 6; k++) {
                    if (i + k >= n) {
                        ng++;
                    } else if (s[i + k][j] != '#') {
                        ng2++;
                    }
                }
                if (ng == 0 && ng2 <= 2) {
                    System.out.println("Yes");
                    return;
                }

                // 右
                ng = 0;
                ng2 = 0;
                for (int k = 0; k < 6; k++) {
                    if (j + k >= n) {
                        ng++;
                    } else if (s[i][j + k] != '#') {
                        ng2++;
                    }
                }
                if (ng == 0 && ng2 <= 2) {
                    System.out.println("Yes");
                    return;
                }

                // 右下
                ng = 0;
                ng2 = 0;
                for (int k = 0; k < 6; k++) {
                    if (i + k >= n || j + k >= n) {
                        ng++;
                    } else if (s[i + k][j + k] != '#') {
                        ng2++;
                    }
                }
                if (ng == 0 && ng2 <= 2) {
                    System.out.println("Yes");
                    return;
                }

                // 左下
                ng = 0;
                ng2 = 0;
                for (int k = 0; k < 6; k++) {
                    if (i + k >= n || j - k < 0) {
                        ng++;
                    } else if (s[i + k][j - k] != '#') {
                        ng2++;
                    }
                }
                if (ng == 0 && ng2 <= 2) {
                    System.out.println("Yes");
                    return;
                }
            }
        }
        System.out.println("No");
    }
}

ここまで19分53秒＋3ペナ。957位。


D - Sequence Query

問題
D問題で座圧BIT 二分探索なんてことまで求められる？それにしては正解者数多すぎない？とか思いながらも他に思い付かなかったので粛々と実装する。

思考過程
  1. TreeSetを使えばx以下の最大の要素は取得できるが、そこからk-1個前というインデックスを指定して要素を取得することはできない。（後から思えば、floorをk回繰り返すようなことをすればできなくはなかった）
  2. あらかじめクエリ1の全てを追加したListをソートしておき、二分探索してそこからk-1個前を探すことを考えるが、クエリ1で追加済みかどうかを1つ1つ調べていたらO(k)ではなくO(Q)になってしまう。
    　
  3. xを座標圧縮した上でFenwickTreeを使い、クエリ2については「(x以下の個数)-(ans以下の個数)=k-1となるans」を二分探索で求めることを考える。
  4. クエリ3も逆のことをやるだけで概ね同様だが、境界値で混乱しつつ、実行したら1要素ずれている感じだったのでokではなくngを出力してみた。（てきとう）
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine());
        int[] t = new int[q];
        long[] x = new long[q];
        int[] k = new int[q];
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            t[i] = Integer.parseInt(sa[0]);
            x[i] = Long.parseLong(sa[1]);
            if (t[i] != 1) {
                k[i] = Integer.parseInt(sa[2]);
            }
        }
        br.close();

        // 座標圧縮
        TreeMap<Long, Integer> map = new TreeMap<>();
        for (int i = 0; i < x.length; i++) {
            map.put(x[i], null);
        }
        Long[] arr = map.keySet().toArray(new Long[0]);
        int cnt = 0;
        for (Long i : arr) {
            map.put(i, cnt);
            cnt++;
        }
        int[] b = new int[x.length];
        for (int i = 0; i < x.length; i++) {
            b[i] = map.get(x[i]);
        }

        // 座標圧縮復元用
        TreeMap<Integer, Long> rmap = new TreeMap<>();
        for (Long key : map.keySet()) {
            rmap.put(map.get(key), key);
        }

        FenwickTree ft = new FenwickTree(q);
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            if (t[i] == 1) {
                ft.add(b[i], 1);

            } else if (t[i] == 2) {
                long a = ft.sum(b[i] + 1);
                if (a < k[i]) {
                    pw.println(-1);
                    continue;
                }
                int ok = 0;
                int ng = q + 1;
                while (Math.abs(ok - ng) > 1) {
                    int mid = (ok + ng) / 2;
                    if (a - ft.sum(mid) >= k[i]) {
                        ok = mid;
                    } else {
                        ng = mid;
                    }
                }
                pw.println(rmap.get(ok));

            } else {
                long all = ft.sum(q);
                long a = ft.sum(b[i]);
                if (all - a < k[i]) {
                    pw.println(-1);
                    continue;
                }
                int ok = q;
                int ng = b[i];
                while (Math.abs(ok - ng) > 1) {
                    int mid = (ok + ng) / 2;
                    if (ft.sum(mid) - a >= k[i]) {
                        ok = mid;
                    } else {
                        ng = mid;
                    }
                }
                pw.println(rmap.get(ng)); // 4
            }
        }
        pw.flush();
    }
}

// 以下ACLを移植したFenwickTree

ここまで46分52秒＋3ペナ。845位。


E - Putting Candies

問題
サンプルを見ないとなかなか問題が頭に入ってこない。

思考過程
  1. 次に見るXを得られればいいだけだったらダブリングやるだけだが、答えはNで割った余りではないので、得られるアメの合計についても別途配列を用意して同様に処理する。
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]);
        long k = Long.parseLong(sa[1]);
        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        int[][] dp = new int[40][n]; // 遷移先
        long[][] dp2 = new long[40][n]; // 個数
        for (int i = 0; i < n; i++) {
            dp[0][i] = (i + a[i]) % n;
            dp2[0][i] = a[i];
        }
        for (int i = 1; i < 40; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = dp[i - 1][dp[i - 1][j]];
                dp2[i][j] = dp2[i - 1][j] + dp2[i - 1][dp[i - 1][j]];
            }
        }

        long ans = 0;
        int x = 0;
        for (int i = 0; i < 40; i++) {
            if ((k >> i & 1) == 1) {
                ans += dp2[i][x];
                x = dp[i][x];
            }
        }
        System.out.println(ans);
    }
}

ここまで58分31秒＋3ペナ。516位。


F - Skate

問題

思考過程
  1. 遷移を書くのがめんどくさいが、ただBFSをするだけ。
  2. 止まれる場所が障害物の上下左右しかないので、頂点数はN \times 4個程度には収まる。
  3. 障害物が存在する行、列ごとにTreeSetで障害物の座標を持っておけば、lower+1、higher-1といった操作で遷移先を取得できる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.TreeSet;

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

        Map<Integer, TreeSet<Integer>> mapx = new HashMap<>();
        Map<Integer, TreeSet<Integer>> mapy = new HashMap<>();
        for (int i = 0; i < n; i++) {
            TreeSet<Integer> setx = mapx.get(x[i]);
            if (setx == null) {
                setx = new TreeSet<>();
                mapx.put(x[i], setx);
            }
            setx.add(y[i]);

            TreeSet<Integer> sety = mapy.get(y[i]);
            if (sety == null) {
                sety = new TreeSet<>();
                mapy.put(y[i], sety);
            }
            sety.add(x[i]);
        }

        long m = 1000000000;
        Queue<Long> que = new ArrayDeque<>();
        que.add(sx * m + sy);
        Map<Long, Integer> map = new HashMap<>();
        map.put(sx * m + sy, 0);
        while (!que.isEmpty()) {
            long cur = que.poll();
            int cx = (int) (cur / m);
            int cy = (int) (cur % m);

            TreeSet<Integer> set = mapx.get(cx);
            if (set != null) {
                // 左
                Integer ny = set.lower(cy);
                if (ny != null) {
                    long next = cx * m + ny + 1;
                    if (!map.containsKey(next)) {
                        map.put(next, map.get(cur) + 1);
                        que.add(next);
                    }
                }
                // 右
                ny = set.higher(cy);
                if (ny != null) {
                    long next = cx * m + ny - 1;
                    if (!map.containsKey(next)) {
                        map.put(next, map.get(cur) + 1);
                        que.add(next);
                    }
                }
            }

            set = mapy.get(cy);
            if (set != null) {
                // 上
                Integer nx = set.lower(cx);
                if (nx != null) {
                    long next = (nx + 1) * m + cy;
                    if (!map.containsKey(next)) {
                        map.put(next, map.get(cur) + 1);
                        que.add(next);
                    }
                }
                // 下
                nx = set.higher(cx);
                if (nx != null) {
                    long next = (nx - 1) * m + cy;
                    if (!map.containsKey(next)) {
                        map.put(next, map.get(cur) + 1);
                        que.add(next);
                    }
                }
            }
        }
        long goal = gx * m + gy;
        System.out.println(map.getOrDefault(goal, -1));
    }
}

ここまで73分25秒＋3ペナ。204位。



G問題はフローっぽさを感じてはいたが、何分か考えてグラフを構築できず、正解者数もあまり多くなかったので解けなくてもいいやと80分過ぎの時点で撤退。



最終結果：ABCDEFの6完2000点、88分25秒、274位、パフォーマンス2030相当
レート変動：2060（Unrated）


今週もAHCの影響で気力が乏しく、CやDでハマったもののEやFで考える要素が少なかったので、なんとか解けるべきところまでは解けたという感じ。

明日のARCはさすがにちゃんと参加したいので今夜はゆっくり休む。
でもこの後AHCの記事も書く予定・・。