AtCoder Beginner Contest 265

ABC

コンテスト前のレート：1970
レート通りのパフォーマンスが得られる順位：318位（1500点、46分40秒）

A - Apple

問題

思考過程
  1. Y円で3個買う方を何回するかを全探索してしまうことにする。
import java.util.Scanner;

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

        int ans = 1000000000;
        for (int i = 0; i < n; i++) {
            int a = n - 3 * i;
            if (a < 0) {
                break;
            }
            int v1 = x * a;
            int v2 = y * i;
            ans = Math.min(ans, v1 + v2);
        }
        System.out.println(ans);
    }
}

ここまで1分55秒＋0ペナ。690位。


B - Explore

問題
B問題でO(NM)が許されないことにちょっとびっくり。

思考過程
  1. 持ち時間の消費と増加をシミュレーションする。
  2. ボーナスに該当するかどうかを調べるのにO(M)かけられないので、「bonus[x] = y」の形で入力を受け取っておくことにする。
  3. 消費と増加の順序や添え字のズレなどに注意する。（サンプルが合わなかったので調整した）
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 m = Integer.parseInt(sa[1]);
        int t = Integer.parseInt(sa[2]);
        sa = br.readLine().split(" ");
        int[] a = new int[n - 1];
        for (int i = 0; i < a.length; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        // 2
        int[] b = new int[n];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int x = Integer.parseInt(sa[0]) - 2; // 3
            int y = Integer.parseInt(sa[1]);
            b[x] = y;
        }
        br.close();

        // 1
        long rem = t;
        for (int i = 0; i < n - 1; i++) {
            rem -= a[i];
            if (rem <= 0) {
                System.out.println("No");
                return;
            }
            rem += b[i];
        }
        System.out.println("Yes");
    }
}

ここまで6分43秒＋0ペナ。293位。


C - Belt Conveyor

問題

思考過程
  1. 現在位置の推移をシミュレーションする。
  2. 無限に移動し続ける場合は何度も同じ箇所を通ることになるので、一度通った箇所を記録しておき、もう一度通ったら-1とする。
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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        char[][] g = new char[h][w];
        for (int i = 0; i < h; i++) {
            g[i] = br.readLine().toCharArray();
        }
        br.close();

        boolean[][] b = new boolean[h][w];
        int i = 0;
        int j = 0;
        b[i][j] = true;
        while (true) {
            if (g[i][j] == 'U') {
                if (i == 0) {
                    System.out.println((i + 1) + " " + (j + 1));
                    return;
                }
                i--;

            } else if (g[i][j] == 'D') {
                if (i == h - 1) {
                    System.out.println((i + 1) + " " + (j + 1));
                    return;
                }
                i++;

            } else if (g[i][j] == 'L') {
                if (j == 0) {
                    System.out.println((i + 1) + " " + (j + 1));
                    return;
                }
                j--;

            } else if (g[i][j] == 'R') {
                if (j == w - 1) {
                    System.out.println((i + 1) + " " + (j + 1));
                    return;
                }
                j++;
            }
            if (b[i][j]) {
                System.out.println(-1);
                return;
            }
            b[i][j] = true;
        }
    }
}

ここまで10分38秒＋0ペナ。131位。


D - Iroha and Haiku (New ABC Edition)

問題
二分探索3回でよかったのに回りくどいことをした。

思考過程
  1. 合計がP+Q+Rとなる区間をしゃくとり法で探す。
  2. 区間の左端を起点に合計がPとなる位置を二分探索で探す。
  3. 事前に累積和を取っておかないと二分探索できないので取る。
  4. 上記2.が存在した場合、そこを起点に合計がQとなる位置を二分探索で探す。
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 p = Long.parseLong(sa[1]);
        long q = Long.parseLong(sa[2]);
        long r = Long.parseLong(sa[3]);
        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        // 3
        long[] b = new long[n + 1];
        for (int i = 0; i < n; i++) {
            b[i + 1] = b[i] + a[i];
        }

        long pqr = p + q + r;
        long sum = 0;
        int y = 0;
        for (int x = 0; x < n; x++) {
            // 1
            while (y < n && sum < pqr) {
                sum += a[y];
                y++;
            }
            if (sum == pqr) {
                // 2
                int i1 = binarySearch(b, b[x] + p);
                if (b[i1] == b[x] + p) {
                    // 4
                    int i2 = binarySearch(b, b[i1] + q);
                    if (b[i2] == b[i1] + q) {
                        System.out.println("Yes");
                        return;
                    }
                }
            }
            sum -= a[x];
        }
        System.out.println("No");
    }

    // val以上である最小indexを返す二分探索
    static int binarySearch(long[] array, long val) {
        int ok = array.length;
        int ng = -1;
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (array[mid] >= val) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok;
    }
}

おまけ：公式解説に書いてあったSet解法をやってみた。こっちの方が圧倒的に簡単。

import java.io.BufferedReader;
import java.io.InputStreamReader;
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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        long p = Long.parseLong(sa[1]);
        long q = Long.parseLong(sa[2]);
        long r = Long.parseLong(sa[3]);
        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        Set<Long> set = new HashSet<>();
        long s = 0;
        for (int i = 0; i < n; i++) {
            s += a[i];
            set.add(s);
        }

        s = 0;
        for (int i = 0; i < n; i++) {
            if (set.contains(s + p) &&
                    set.contains(s + p + q) &&
                    set.contains(s + p + q + r)) {
                System.out.println("Yes");
                return;
            }
            s += a[i];
        }
        System.out.println("No");
    }
}

ここまで17分23秒＋0ペナ。114位。


E - Warp

問題
ABC263に続きまたしてもEが解けず。

思考過程
  1. 3^Nから障害物の座標を通ってしまう経路数を引くことを考える。
  2. 3種類の移動をそれぞれi, j, k回行った結果NG座標に到達する場合、_{i+j+k}C_i \times _{j+k}C_j \times 3^{N-i-j-k}を引いていけばよさそうな気がするが、これだけでは重複がある。
  3. より小さいi, j, kの組で既に引いている場合はスキップするとかをしてみるが、7ケースWA。
    　
  4. 解説を見たら、シンプルな「DP[i][j][k]:=3種類の移動をそれぞれi, j, k回行った時の経路数」でNG座標に来た時に0にすればいいだけだった。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

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]);
        sa = br.readLine().split(" ");
        long[] a = new long[6];
        for (int i = 0; i < 6; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        Map<Long, Set<Long>> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            long x = Integer.parseInt(sa[0]);
            long y = Integer.parseInt(sa[1]);
            Set<Long> set = map.get(x);
            if (set == null) {
                set = new HashSet<>();
                map.put(x, set);
            }
            set.add(y);
        }
        br.close();

        int mod = 998244353;
        long[][][] dp = new long[n + 2][n + 2][n + 2];
        dp[0][0][0] = 1;
        for (int i = 0; i <= n; i++) {
            long x1 = a[0] * i;
            long y1 = a[1] * i;
            for (int j = 0; j <= n - i; j++) {
                long x2 = a[2] * j;
                long y2 = a[3] * j;
                for (int k = 0; k <= n - i - j; k++) {
                    dp[i][j][k] %= mod;
                    long x3 = a[4] * k;
                    long y3 = a[5] * k;
                    Set<Long> set = map.get(x1 + x2 + x3);
                    if (set != null && set.contains(y1 + y2 + y3)) {
                        dp[i][j][k] = 0;
                    } else {
                        dp[i + 1][j][k] += dp[i][j][k];
                        dp[i][j + 1][k] += dp[i][j][k];
                        dp[i][j][k + 1] += dp[i][j][k];
                    }
                }
            }
        }

        long ans = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n - i; j++) {
                int k = n - i - j;
                ans += dp[i][j][k];
            }
        }
        ans %= mod;
        System.out.println(ans);
    }
}

　

あまりにEが解けず、残り30分くらいでFやGをちょくちょく見始めるが、どちらも全然解ける気がせず。
FでDP、Gで遅延セグ木が思い浮かんではいたので、そこまでの勘だけは当たっていたのだが、その先は何も。



最終結果：ABCDの4完1000点、17分23秒、986位、パフォーマンス1458
レート変動：1970→1928（-42）


このEが解けなかったのはかなりショックだった。
直近3回のAGC、ARC、ABCで全部-40前後で、黄色到達以降の最低レート1961を更新するどころの話ではなくなった。
下手すると二度と黄色に戻れないのでは・・・。
そうなったらヒューリスティック1本でやっていこうかな。

去年春に黄色になって以降、とりわけ今年に入ってからは特に、コンテストに参加する以外何もしていないので落ちていって当然ではあるが、絶対的な実力はそんなに落ちるものではないと思うのだが・・・。
1年も経てば周りが成長するのかな。

あと、こんなブログを書いている時間で黄diff埋めるなり青diff復習するなりした方がいいのではという気もしてきているので、これまで2年以上にわたってAHC以外欠かさずに書いてきているが、そろそろやめる可能性もあるかもしれない。