AtCoder Beginner Contest 233(Rated範囲外)

コンテスト前のレート:2051
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:287位(2000点、99分14秒)

A - 10yen Stamp

問題

思考過程
  1. \frac{Y-X}{10}の切り上げを求める。
  2. それだけではX \gt Yの場合にマイナスになってしまうため、その場合0になるようmaxを取る。
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();
        sc.close();

        int ans = Math.max((y - x + 9) / 10, 0);
        System.out.println(ans);
    }
}

ここまで1分04秒+0ペナ。164位。


B - A Reverse

問題

思考過程
  1. L文字目より前、L文字目からR文字目まで、R文字目より後の3つに分ける。
  2. 上記の2番目を反転させる。
  3. 連結し直して出力する。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt() - 1;
        int r = sc.nextInt();
        String s = sc.next();
        sc.close();

        String s1 = s.substring(0, l);
        String s2 = s.substring(l, r);
        String s3 = s.substring(r);

        StringBuilder sb = new StringBuilder(s2);
        sb.reverse();
        s2 = sb.toString();
        System.out.println(s1 + s2 + s3);
    }
}

ここまで3分31秒+0ペナ。506位。


C - Product

問題

思考過程
  1. dp[i][k]:=iまで見て値がkになる通り数」をしたい。
  2. これを配列ではなく、登場したkをキー、対応する通り数を値としたMapで保持する。
  3. そうすると計算量はkの種類数くらいになり、種類数の最大値は各袋のボールの個数の総積であり、10^5以下という制約になっているので間に合う。
  4. なお、単純に掛け算するとlongでも余裕でオーバーフローするので、掛け算をした結果がXを超える場合は処理しないという対策をする。(その判定を割り算で行う)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

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

        Map<Long, Integer> map = new HashMap<>();
        map.put(1L, 1);
        for (int i = 0; i < n; i++) {
            Long[] arr = map.keySet().toArray(new Long[0]);
            Map<Long, Integer> wk = new HashMap<>();
            for (long key : arr) {
                for (int j = 0; j < l[i]; j++) {
                    if (x / key >= a[i][j]) { // 4
                        long v = key * a[i][j];
                        wk.put(v, wk.getOrDefault(v, 0) + map.get(key));
                    }
                }
            }
            map = wk;
        }
        System.out.println(map.getOrDefault(x, 0));
    }
}

ここまで10分31秒+0ペナ。375位。


D - Count Interval

問題

思考過程
  1. 連続部分列の和が関わるのでとりあえず累積和Bを求める。
  2. lに対して、B_r=B_l+Kを満たすrの個数を求めたい。
  3. B_rとして登場した値と回数をMapで管理しながら後ろから見ていけば、上記2.は各lについてO(1)B_l+Kの個数が取得できる。

逆に前から見ていってMapからB_r-Kの値を取り出すでも同じだった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

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

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

        long ans = 0;
        Map<Long, Integer> map = new HashMap<>();
        for (int i = n; i >= 0; i--) {
            ans += map.getOrDefault(b[i] + k, 0);
            map.put(b[i], map.getOrDefault(b[i], 0) + 1); // b[i]の回数を+1
        }
        System.out.println(ans);
    }
}

ここまで17分00秒+0ペナ。358位。


E - Σ[k=0..10^100]floor(X/10^k)

問題
回りくどいことをした。

思考過程
  1. 筆算の形に書き出したものを斜めに見てみると、例1の場合は1111+222+22+5という計算で求めることもできる。
  2. Xで下からi桁目の値は、答えでは下から1i桁目に足されることになる。
  3. 連続する桁に同じ値を足すので、いもす法をすればまずは繰り上がりを考慮しない状態で答えの各桁の値を求められる。
    (こんなことしなくても、桁和を求めてから1桁ずつ引いていくだけでよい)
  4. あとは下の桁から順に繰り上がりの処理を行っていく。10で割った商を上の桁に足し、余りを当該桁に設定する。
  5. 配列の長さは、Xの桁数ではなく答えの桁数以上が必要だが、最大どれだけ繰り上がるのか、一瞬では確実な判断はできない。例2からせいぜい1, 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));
        char[] x = br.readLine().toCharArray();
        br.close();

        int n = x.length;
        int n2 = n * 2;
        int[] a = new int[n2]; // 5
        for (int i = 0; i < n; i++) {
            int d = x[n - 1 - i] - '0';
            a[0] += d;
            a[i + 1] -= d;
        }
        for (int i = 1; i < n2; i++) {
            a[i] += a[i - 1];
        }

        // 繰り上がりの処理
        for (int i = 1; i < n2; i++) {
            a[i] += a[i - 1] / 10;
            a[i - 1] %= 10;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n2; i++) {
            sb.append(a[i]);
        }
        // 不要な0を削除
        while (sb.charAt(sb.length() - 1) == '0') {
            sb.deleteCharAt(sb.length() - 1);
        }
        sb.reverse(); // 下の桁から連結しているので反転
        System.out.println(sb.toString());
    }
}

ここまで30分22秒+0ペナ。376位。



GやExも問題は読んだが、残り時間のほとんどはFに使った。

Fは連結成分内のiP_iの集合が一致していれば可能なことまではすぐにわかったが、構築が上手いことできず。
各連結成分で、iの小さい順に毎回BFSしてP_iからiまで最短距離で移動させるということを、連結成分内の全要素が目的地に移動するまで繰り返すという方法で、2WA・5TLEだった。
提出デバッグをして、2WAは50万回を超えていたためであることまでは把握していた。



終結果:ABCDEの5完1500点、30分22秒、516位、パフォーマンス1788相当
レート変動:2051(Unrated)


前回のABCは後にHまで全部解説ACしたが、今回も解説見る気も起きないほどの問題はなかったと思うので後で全部埋めておく。

Fは木にして葉から揃えられる方法をもう少しちゃんと考えるべきであった。
一般の無向グラフだから葉なんてないで思考停止していた。適当な全域木を取るだけなのに。