AtCoder Beginner Contest 182

コンテスト前のレート:1642
レート通りのパフォーマンスが得られる順位:679位(1500点、46分58秒)

A - twiblr

問題

思考過程
  1. 2 \times A + 100からBを引く。
  2. 答えがマイナスにならないかと思ったが、制約でそれはないことを確認。
import java.util.Scanner;

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

        int m = 2 * a + 100;
        System.out.println(m - b);
    }
}

ここまで0分44秒+0ペナ。69位。


B - Almost GCD

問題

思考過程
  1. k \gt A_iとなるkでは割り切れないので、2 \leq k \leq 1000を全部試したい。
  2. kで毎回N個調べてカウントしていても、ループ回数は全体で10^5程度なので間に合う。
  3. 毎回答えとカウント結果のmaxを取れば・・・と思ったら、出力は最大のGCD度ではなくそれを満たす値だったので、max関数ではなく、maxとansを持ちつつif文で処理する。
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 = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int max = 0;
        int ans = 0;
        for (int k = 2; k <= 1000; k++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (a[j] % k == 0) {
                    cnt++;
                }
            }
            if (cnt > max) {
                max = cnt;
                ans = k;
            }
        }
        System.out.println(ans);
    }
}

ここまで3分19秒+0ペナ。151位。


C - To 3

問題
※入力をSSの桁数をNとして記述。

思考過程
  1. N \leq 19ということは、O(2^NN)で間に合いそうなので、bit全探索を行う。
  2. 残す桁の各桁の和が3の倍数の場合のみ、残す桁数のminを取っていく。
import java.util.Scanner;

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

        int n = s.length();
        int n2 = 1 << n;
        int ans = 20;
        for (int i = 1; i < n2; i++) {
            int sum = 0;
            int cnt = n; // 消す桁数
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) { // 残す桁の場合
                    int d = s.charAt(j) - '0';
                    sum += d;
                    cnt--;
                }
            }
            if (sum % 3 == 0) {
                if (cnt < ans) {
                    ans = cnt;
                }
            }
        }
        if (ans == 20) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
}

ここまで8分15秒+0ペナ。162位。


D - Wandering

問題

思考過程
  1. とりあえず累積和を計算する。(B_i=A_1A_iの和)
  2. 現在地にB_iを足して答えとのmaxを取って・・・の繰り返しかと思いきや、例1を見たら、B_iの中のA_1A_i全ての時点がmaxを取る対象だった。
  3. これは、累積和の累積max(C_i=B_1B_iのmax)を求めればよさそう。
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));
        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]);
        }
        br.close();

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

        long ans = 0;
        long now = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, now + c[i]);
            now += b[i];
        }
        System.out.println(ans);
    }
}

ここまで13分36秒+0ペナ。124位。


E - Akari

問題
思考過程の前半を完全に捨ててやり直したことによる時間ロスが痛かった。

思考過程
  1. 各電球から愚直に4方向調べるのは間に合わないので、調べるところを減らしたい。
  2. 最初にN個全てをキューに入れてBFSを行い、壁マスだけでなく、既に光が届くとわかっているマスに到達した場合も打ち切る?
  3. 例3が23になってしまい、1足りない。
  4. (5, 5)の電球に対して、途中で打ち切っているせいで(5, 2)をカウントできていなかった。
     
  5. 電球を中心とした探索ではなく、各マスについて、そのマスを照らせる電球が存在するかという判定を行うことを考える。
  6. TreeMap<座標、電球か壁か>を、各行と各列分用意しておく。
  7. 各マスの座標に対応するTreeMapから、その座標に最も近いキーを取得し、それが電球だったら照らせるマス。
  8. 計算量はO(HWlog(N+M))のつもり。2500ms制限のところ2279msでぎりぎりだった。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

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]);
        int m = Integer.parseInt(sa[3]);
        List<TreeMap<Integer, Integer>> list1 = new ArrayList<>();
        for (int i = 0; i < h; i++) {
            list1.add(new TreeMap<>());
        }
        List<TreeMap<Integer, Integer>> list2 = new ArrayList<>();
        for (int i = 0; i < w; i++) {
            list2.add(new TreeMap<>());
        }
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            int x = Integer.parseInt(sa[0]) - 1;
            int y = Integer.parseInt(sa[1]) - 1;
            list1.get(x).put(y, 1);
            list2.get(y).put(x, 1);
        }
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int x = Integer.parseInt(sa[0]) - 1;
            int y = Integer.parseInt(sa[1]) - 1;
            list1.get(x).put(y, -1);
            list2.get(y).put(x, -1);
        }
        br.close();

        int ans = 0;
        for (int i = 0; i < h; i++) {
            TreeMap<Integer, Integer> map1 = list1.get(i);
            for (int j = 0; j < w; j++) {
                // 左
                TreeMap<Integer, Integer> map2 = list2.get(j);
                Integer key = map1.floorKey(j);
                if (key != null && map1.get(key) == 1) {
                    ans++;
                    continue;
                }
                // 右
                key = map1.ceilingKey(j);
                if (key != null && map1.get(key) == 1) {
                    ans++;
                    continue;
                }
                // 上
                key = map2.floorKey(i);
                if (key != null && map2.get(key) == 1) {
                    ans++;
                    continue;
                }
                // 下
                key = map2.ceilingKey(i);
                if (key != null && map2.get(key) == 1) {
                    ans++;
                    continue;
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで32分14秒+0ペナ。271位。


F - Valid payments

問題
解けず。
解説や人のツイートを見た感じだと、考察が半分できていたかどうかといったところ。
思考過程3(エスパー狙い)に時間を費やしすぎで、4に進んだ頃にはもう残り10分とかだった。

思考過程
  1. まずy=Xは条件を満たす。
  2. y=X(X+10000)くらいを全部試す愚直を作ってみて、法則をつかもうとする。
  3. X1円玉を使わない場合、1円玉を使うyが条件を満たすことはなかったり、Xより大きいA_iを使う場合において規則性が感じられたりなどはしたが、決定的なことはわからず。
     
  4. 愚直実装では、とりあえずA_i円玉を使うかどうかだけを視覚化していたが、何個払う/もらうかを調べてみると、各A_iについて2通りか3通りしかない。
  5. 具体的には、B_i=X円ちょうどを払うのに使うA_iの枚数、C_i=\frac{A_{i+1}}{A_i}とすると、
    • B_i=0の場合、払う場合1、お釣りでもらう場合C_i-1、使わない場合03通り。
    • B_i \neq 0の場合、払う場合B_i、お釣りでもらう場合C_i-B_i2通り。
  6. これを全部試すとO(3^N)となるがどうしよう。

あとはDPをすればO(N)になるようだが、時間内にそこまで詰め切れず。



終結果:ABCDEの5完、32分14秒、393位、パフォーマンス1891
レート変動:1642→1670(+28)


30くらい上がると結構上がった気分にはなるが、むしろパフォーマンスたった1900弱でこんなに上がっていることに違和感を感じたくらいだった。
(Highestの1820だったら+7とかだと思うので)
それだけレートが下がっているという現実・・・。

F問題が決して全く何もできない難易度ではないはずだが、日々の精進で10分で解説を見る諦め癖が付きすぎているのが悪いのかもしれない。
知見を得る目的だけで言えば、さっさと見た方が効率は良いが。

新しい問題ですぐ解説を見てしまう分、くじかつなどでちゃんと一度通した問題ができなくなっていないか再確認するべきだと思っているところ。